[是题解哦] 洛谷 P1531 I Hate It

题目链接

点这里点这里

题目背景

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。

题目描述

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩

输入输出格式

输入格式：

第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。学生ID编号分别从1编到N。第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。当C为'U'的时候，表示这是一条更新操作，如果当前A学生的成绩低于B，则把ID为A的学生的成绩更改为B，否则不改动。

输出格式：

对于每一次询问操作，在一行里面输出最高成绩

题解

根据题目要求我们可以发现，这道题要求我们维护一个数据结构，来支持单点修改和区间查询最值，于是我想到用线段树来实现。

我的线段树和其他题解中不太一样，是动态开点

对于题目中的要求

如果当前A学生的成绩低于B，则把ID为A的学生的成绩更改为B，否则不改动。

我们可以考虑在单点修改操作中用以下方式维护

 1 void Insert(int &now,int l,int r,int x,int k){
 2     if(now==0)
 3         now=++cnt;
 4     if(l==r){
 5         Seg[now].sum=max(Seg[now].sum,k);//按照题目要求维护线段树
 6         return;
 7     }
 8     int mid=(l+r)>>1;
 9     if(x<=mid)
10         Insert(Seg[now].L,l,mid,x,k);
11     else
12         Insert(Seg[now].R,mid+1,r,x,k);
13     Seg[now].sum=max(Seg[Seg[now].L].sum,Seg[Seg[now].R].sum);
14     //维护线段树，以使每个节点都等于它子节点的最大值
15 }

对于查询操作，我们可以考虑这样维护

int Query(int now,int l,int r,int x,int y){
    if(x<=l && r<=y)
        return Seg[now].sum;
    //如果要查询的区间比子节点代表的区间还小，直接返回子节点区间
    int mid=(l+r)>>1;
    int maxL=0,maxR=0;
    if(x<=mid)
        maxL=max(maxL,Query(Seg[now].L,l,mid,x,y));//维护查询最大值
    if(y>mid)
        maxR=max(maxR,Query(Seg[now].R,mid+1,r,x,y));//维护查询最大值
    return max(maxL,maxR);//维护查询最大值
}

以下是完整代码

 1 #include<iostream>//I Hate It!!!!
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 struct Tree{
 6     int L;
 7     int R;
 8     int sum;
 9 }Seg[800010];
10 int n,m,cnt,root;
11 int a[200010];
12 char C;
13 
14 void Build(int &now,int l,int r){//传址调用实现动态开点
15     if(now==0)
16         now=++cnt;//某种意义上是动态开点核心操作了
17     if(l==r){
18         Seg[now].sum=a[l];
19         return;
20     }
21     int mid=(l+r)>>1;
22     Build(Seg[now].L,l,mid);
23     Build(Seg[now].R,mid+1,r);
24     Seg[now].sum=max(Seg[Seg[now].L].sum,Seg[Seg[now].R].sum);
25     //在建树操作中维护最大值
26 }
27 
28 void Insert(int &now,int l,int r,int x,int k){
29     if(now==0)
30         now=++cnt;
31     if(l==r){
32         Seg[now].sum=max(Seg[now].sum,k);
33         return;
34     }
35     int mid=(l+r)>>1;
36     if(x<=mid)
37         Insert(Seg[now].L,l,mid,x,k);
38     else
39         Insert(Seg[now].R,mid+1,r,x,k);
40     Seg[now].sum=max(Seg[Seg[now].L].sum,Seg[Seg[now].R].sum);
41 }
42 
43 int Query(int now,int l,int r,int x,int y){
44     if(x<=l && r<=y)
45         return Seg[now].sum;
46     int mid=(l+r)>>1;
47     int maxL=0,maxR=0;
48     if(x<=mid)
49         maxL=max(maxL,Query(Seg[now].L,l,mid,x,y));
50     if(y>mid)
51         maxR=max(maxR,Query(Seg[now].R,mid+1,r,x,y));
52     return max(maxL,maxR);
53 }
54 
55 int main(){
56     //freopen("IHate.in","r",stdin);
57     //freopen("IHate.out","w",stdout);
58     scanf("%d%d",&n,&m);
59     for(int i=1;i<=n;i++)
60         scanf("%d",&a[i]);
61     Build(root,1,n);
62     for(int i=1;i<=m;i++){
63         cin>>C;
64         if(C=='Q'){
65             register int x,y;
66             scanf("%d%d",&x,&y);
67             printf("%d
",Query(root,1,n,x,y));
68         }
69         else{
70             register int x,k;
71             scanf("%d%d",&x,&k);
72             Insert(root,1,n,x,k);
73         }
74     }
75     return 0;
76 }

感觉动态开点非常好理解为什么没人用呢

友情链接：安利一只小姐姐的博客