[kuangbin带你飞]专题七 线段树

https://vjudge.net/contest/66989

A、敌兵布阵

单点修改、区间查询、维护区间和

  1 //CSDN:https://blog.csdn.net/qq_40889820
  2 #include<iostream>
  3 #include<sstream>
  4 #include<fstream>
  5 #include<algorithm>
  6 #include<cstring>
  7 #include<iomanip>
  8 #include<cstdlib>
  9 #include<cctype>
 10 #include<vector>
 11 #include<string>
 12 #include<cmath>
 13 #include<ctime>
 14 #include<stack>
 15 #include<queue>
 16 #include<map>
 17 #include<set>
 18 #define mem(a,b) memset(a,b,sizeof(a))
 19 #define random(a,b) (rand()%(b-a+1)+a)
 20 #define ll long long
 21 #define ull unsigned long long
 22 #define e 2.71828182
 23 #define Pi acos(-1.0)
 24 #define ls(rt) (rt<<1)
 25 #define rs(rt) (rt<<1|1)
 26 #define lowbit(x) (x&(-x))
 27 using namespace std;
 28 const int MAXN=5e4+5;
 29 int a[MAXN];
 30 struct node
 31 {
 32     int sum;
 33 }T[MAXN<<2];
 34 int read()
 35 {
 36     int s=1,x=0;
 37     char ch=getchar();
 38     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
 39     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
 40     return x*s;
 41 }
 42 void push_up(int p,int l,int r)
 43 {
 44     T[p].sum=T[ls(p)].sum+T[rs(p)].sum;
 45 }
 46 void build(int p,int l,int r)
 47 {
 48     if(l==r)
 49     {
 50         T[p].sum=a[l];
 51         return;
 52     }
 53     int mid=(l+r)>>1;
 54     build(ls(p),l,mid);
 55     build(rs(p),mid+1,r);
 56     push_up(p,l,r);
 57 }
 58 void update(int p,int l,int r,int lr,int k)
 59 {
 60     if(l==r)
 61     {
 62         T[p].sum+=k;
 63         return;
 64     }
 65     int mid=(l+r)>>1;
 66     if(lr<=mid) update(ls(p),l,mid,lr,k);
 67     else update(rs(p),mid+1,r,lr,k);
 68     push_up(p,l,r);
 69 }
 70 int query(int p,int l,int r,int nl,int nr)
 71 {
 72     if(nl<=l&&nr>=r)  return T[p].sum;
 73     int mid=(l+r)>>1,ans=0;
 74     if(nl<=mid) ans+=query(ls(p),l,mid,nl,nr);
 75     if(nr>mid) ans+=query(rs(p),mid+1,r,nl,nr);
 76     return ans;
 77 }
 78 int main()
 79 {
 80     int t=read(),nl,nr,n;
 81     string ord;
 82     for(int cas=1;cas<=t;++cas)
 83     {
 84         cout<<"Case "<<cas<<":
";
 85         n=read();
 86         for(int i=1;i<=n;++i)
 87         a[i]=read();
 88         build(1,1,n);
 89         while(true)
 90         {
 91             cin>>ord;
 92             if(ord=="End") break;
 93             else if(ord=="Query")
 94             {
 95                 nl=read(),nr=read();
 96                 cout<<query(1,1,n,nl,nr)<<endl;    
 97             }    
 98             else if(ord=="Add")
 99             {
100                 nl=read(),nr=read();
101                 update(1,1,n,nl,nr);
102             }
103             else 
104             {
105                 nl=read(),nr=read();
106                 update(1,1,n,nl,-nr);
107             }
108         } 
109     }
110     return 0;
111 }
View Code

B、I Hate It

单点修改、区间查询、维护区间最大值

 1 //CSDN:https://blog.csdn.net/qq_40889820
 2 #include<iostream>
 3 #include<sstream>
 4 #include<fstream>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<iomanip>
 8 #include<cstdlib>
 9 #include<cctype>
10 #include<vector>
11 #include<string>
12 #include<cmath>
13 #include<ctime>
14 #include<stack>
15 #include<queue>
16 #include<map>
17 #include<set>
18 #define mem(a,b) memset(a,b,sizeof(a))
19 #define random(a,b) (rand()%(b-a+1)+a)
20 #define ll long long
21 #define ull unsigned long long
22 #define e 2.71828182
23 #define Pi acos(-1.0)
24 #define ls(rt) (rt<<1)
25 #define rs(rt) (rt<<1|1)
26 #define lowbit(x) (x&(-x))
27 using namespace std;
28 const int MAXN=2e5+5;
29 int a[MAXN];
30 struct node
31 {
32     int maxx;
33 }T[MAXN<<2];
34 int read()
35 {
36     int s=1,x=0;
37     char ch=getchar();
38     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
39     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
40     return x*s;
41 }
42 void push_up(int p,int l,int r)
43 {
44     T[p].maxx=max(T[ls(p)].maxx,T[rs(p)].maxx);
45 }
46 void build(int p,int l,int r)
47 {
48     if(l==r)
49     {
50         T[p].maxx=a[l];
51         return;
52     }
53     int mid=(l+r)>>1;
54     build(ls(p),l,mid);
55     build(rs(p),mid+1,r);
56     push_up(p,l,r);
57 }
58 void update(int p,int l,int r,int lr,int k)
59 {
60     if(l==r)
61     {
62         T[p].maxx=k;
63         return;
64     }
65     int mid=(l+r)>>1;
66     if(lr<=mid) update(ls(p),l,mid,lr,k);
67     else update(rs(p),mid+1,r,lr,k);
68     push_up(p,l,r);
69 }
70 int query(int p,int l,int r,int nl,int nr)
71 {
72     if(nl<=l&&nr>=r)  return T[p].maxx;
73     int mid=(l+r)>>1,ans=0;
74     if(nl<=mid) ans=max(query(ls(p),l,mid,nl,nr),ans);
75     if(nr>mid) ans=max(query(rs(p),mid+1,r,nl,nr),ans);
76     return ans;
77 }
78 int main()
79 {
80     int n,m;
81     while(~scanf("%d%d",&n,&m))
82     {
83         for(int i=1;i<=n;++i)
84         a[i]=read();
85         build(1,1,n);
86         char ord;
87         int A,B;
88         while(m--)
89         {
90             cin>>ord;
91             A=read(),B=read();
92             if(ord=='Q')
93             cout<<query(1,1,n,A,B)<<endl;
94             else 
95             update(1,1,n,A,B);
96         }
97     }
98     return 0;
99 }
View Code

C、A Simple Problem with Integers

区间修改、区间查询、维护区间和、延迟标记

  1 //CSDN:https://blog.csdn.net/qq_40889820
  2 #include<iostream>
  3 #include<sstream>
  4 #include<fstream>
  5 #include<algorithm>
  6 #include<cstring>
  7 #include<iomanip>
  8 #include<cstdlib>
  9 #include<cctype>
 10 #include<vector>
 11 #include<string>
 12 #include<cmath>
 13 #include<ctime>
 14 #include<stack>
 15 #include<queue>
 16 #include<map>
 17 #include<set>
 18 #define mem(a,b) memset(a,b,sizeof(a))
 19 #define random(a,b) (rand()%(b-a+1)+a)
 20 #define ll long long
 21 #define ull unsigned long long
 22 #define e 2.71828182
 23 #define Pi acos(-1.0)
 24 #define ls(rt) (rt<<1)
 25 #define rs(rt) (rt<<1|1)
 26 #define lowbit(x) (x&(-x))
 27 using namespace std;
 28 const int MAXN=1e5+5;
 29 ll a[MAXN];
 30 struct node
 31 {
 32     ll sum,tag;
 33 }T[MAXN<<2];
 34 ll read()
 35 {
 36     ll s=1,x=0;
 37     char ch=getchar();
 38     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
 39     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
 40     return x*s;
 41 }
 42 void push_up(int p,int l,int r)
 43 {
 44     T[p].sum=T[ls(p)].sum+T[rs(p)].sum;
 45 }
 46 void build(int p,int l,int r)
 47 {
 48     if(l==r)
 49     {
 50         T[p].sum=a[l];
 51         return;
 52     }
 53     T[p].tag=0;
 54     int mid=(l+r)>>1;
 55     build(ls(p),l,mid);
 56     build(rs(p),mid+1,r);
 57     push_up(p,l,r);
 58 }
 59 void push_down(int p,int l,int r)
 60 {
 61     if(!T[p].tag) return;
 62     T[ls(p)].tag+=T[p].tag,T[rs(p)].tag+=T[p].tag;
 63     int mid=(l+r)>>1;
 64     T[ls(p)].sum+=T[p].tag*(mid-l+1);
 65     T[rs(p)].sum+=T[p].tag*(r-mid);
 66     T[p].tag=0;
 67 }
 68 void update(int p,int l,int r,int nl,int nr,ll k)
 69 {
 70     if(nl<=l&&nr>=r) 
 71     {
 72         T[p].sum+=k*(r-l+1);
 73         T[p].tag+=k;
 74         return ;
 75     }
 76     push_down(p,l,r);
 77     int mid=(l+r)>>1;
 78     if(nl<=mid) update(ls(p),l,mid,nl,nr,k);
 79     if(nr>mid) update(rs(p),mid+1,r,nl,nr,k);
 80     push_up(p,l,r);
 81 }
 82 ll query(int p,int l,int r,int nl,int nr)
 83 {
 84     if(nl<=l&&nr>=r)  return T[p].sum;
 85     push_down(p,l,r);
 86     int mid=(l+r)>>1;
 87     ll ans=0;
 88     if(nl<=mid) ans+=query(ls(p),l,mid,nl,nr);
 89     if(nr>mid) ans+=query(rs(p),mid+1,r,nl,nr);
 90     return ans;
 91 }
 92 int main()
 93 {
 94     int n=read(),m=read();
 95     for(int i=1;i<=n;++i)
 96     a[i]=read();
 97     build(1,1,n);
 98     char ord;
 99     int A,B;
100     ll C;
101     while(m--)
102     {
103         cin>>ord;
104         A=read(),B=read();
105         if(ord=='Q')
106         cout<<query(1,1,n,A,B)<<endl;
107         else 
108         {
109             C=read();
110             update(1,1,n,A,B,C);
111         }    
112     }
113     return 0;
114 }
View Code

D、Mayor's posters

 

区间问题，后来的能把先来的覆盖，问最后有多少种。

区间修改、区间查询（一次）、维护区间最大值（最后查询只需查询叶子结点，这个有没有无所谓其实）

用到了区间离散化，离散化的另一种形式（理解这个花了不少时间），这里特殊的是排序后距离大于1便增加一个点，详见代码

  1 #include<stdio.h>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<algorithm>
  5 #define ls(p) (p<<1)
  6 #define rs(p) (p<<1|1)
  7 using namespace std;
  8 const int MAXN=4e4+5;//原先是1e4，普通离散化后2倍，特殊后也要2倍以防万一 
  9 struct node
 10 {
 11     int big,tag;//最大序号即上层的post、懒标记同记录post编号 
 12 }T[MAXN<<2];
 13 int book[MAXN],Hash[MAXN];
 14 int L[MAXN],R[MAXN];
 15 void push_up(int p)
 16 {
 17     T[p].big=max(T[ls(p)].big,T[rs(p)].big);
 18 }
 19 void push_down(int p,int l,int r)
 20 {
 21     if(!T[p].tag) return;
 22     int mid=(l+r)>>1;
 23     T[ls(p)].tag=max(T[p].tag,T[ls(p)].tag);
 24     T[rs(p)].tag=max(T[p].tag,T[rs(p)].tag);
 25     T[ls(p)].big=max(T[p].tag,T[ls(p)].tag);
 26     T[rs(p)].big=max(T[p].tag,T[rs(p)].big);
 27     T[p].tag=0; 
 28 }
 29 void build(int p,int l,int r)
 30 {
 31     if(l==r)
 32     {
 33         T[p].big=0,T[p].tag=0;
 34         return ;
 35     }
 36     T[p].big=0,T[p].tag=0;
 37     int mid=(l+r)>>1;
 38     build(ls(p),l,mid);
 39     build(rs(p),mid+1,r);
 40     push_up(p);
 41 }
 42 void update(int p,int l,int r,int nl,int nr,int k)
 43 {
 44     if(nl<=l&&nr>=r)
 45     {
 46         T[p].big=max(T[p].big,k);//其实多此一举，反正更新的时候k从小到大
 47         T[p].tag=max(T[p].tag,k);//同上
 48         return; 
 49     }
 50     push_down(p,l,r);
 51     int mid=(l+r)>>1;
 52     if(nl<=mid) update(ls(p),l,mid,nl,nr,k);
 53     if(nr>mid) update(rs(p),mid+1,r,nl,nr,k);
 54     push_up(p);
 55 }
 56 int query(int p,int l,int r,int nl,int nr)
 57 {
 58     if(l==r)//统计叶子节点的 
 59     {
 60         if(T[p].big&&!book[T[p].big])
 61         {
 62             book[T[p].big]=1;
 63             return 1;
 64         }
 65         return 0;
 66     }
 67     int ans=0,mid=(l+r)>>1;
 68     push_down(p,l,r);
 69     if(nl<=mid) ans+=query(ls(p),l,mid,nl,nr);
 70     if(nr>mid) ans+=query(rs(p),mid+1,r,nl,nr);
 71     return ans;
 72 }
 73 int read()
 74 {
 75     int s=1,x=0;char ch=getchar();
 76     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
 77     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
 78     return s*x;
 79 }
 80 int main()
 81 {
 82     int test=read();
 83     while(test--)
 84     {
 85         int n=read();
 86         for(int i=1;i<=n;++i)
 87         {
 88             L[i]=read(),R[i]=read();
 89             Hash[(i<<1)-1]=L[i],Hash[i<<1]=R[i];
 90         }
 91         sort(Hash+1,Hash+2*n+1);
 92         
 93         int tot=unique(Hash+1,Hash+2*n+1)-Hash-1,tmp=tot;//去重 
 94         for(int i=2;i<=tot;++i)
 95         if(Hash[i]-Hash[i-1]>1) Hash[++tmp]=Hash[i-1]+1;//相邻两个点的距离大于1则新加一个点 
 96         tot=tmp;//离散化后最多tot个点 
 97         sort(Hash+1,Hash+tot+1);
 98         build(1,1,tot);memset(book,0,sizeof(book));
 99         for(int i=1;i<=n;++i)
100         {
101             int l=lower_bound(Hash+1,Hash+tot+1,L[i])-Hash;
102             int r=lower_bound(Hash+1,Hash+tot+1,R[i])-Hash;
103             update(1,1,tot,l,r,i);//i代表颜色编号 
104         }    
105         cout<<query(1,1,tot,1,tot)<<endl;
106     }
107 }
View Code

去除冗余操作后代码：

 1 #include<stdio.h>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define ls(p) (p<<1)
 6 #define rs(p) (p<<1|1)
 7 using namespace std;
 8 const int MAXN=4e4+5;//原先是1e4，普通离散化后2倍，特殊后也要2倍以防万一 
 9 struct node
10 {
11     int tag;
12 }T[MAXN<<2];
13 int book[MAXN],Hash[MAXN];
14 int L[MAXN],R[MAXN];
15 void push_down(int p,int l,int r)
16 {
17     if(!T[p].tag) return;
18     int mid=(l+r)>>1;
19     T[ls(p)].tag=T[p].tag; 
20     T[rs(p)].tag=T[p].tag;
21     T[p].tag=0; 
22 }
23 void update(int p,int l,int r,int nl,int nr,int k)
24 {
25     if(nl<=l&&nr>=r)
26     {
27         T[p].tag=k;//同上
28         return; 
29     }
30     push_down(p,l,r);
31     int mid=(l+r)>>1;
32     if(nl<=mid) update(ls(p),l,mid,nl,nr,k);
33     if(nr>mid) update(rs(p),mid+1,r,nl,nr,k);
34 }
35 int query(int p,int l,int r,int nl,int nr)
36 {
37     if(l==r)//统计叶子节点的 
38     {
39         if(T[p].tag&&!book[T[p].tag])
40         {
41             book[T[p].tag]=1;
42             return 1;
43         }
44         return 0;
45     }
46     int ans=0,mid=(l+r)>>1;
47     push_down(p,l,r);
48     if(nl<=mid) ans+=query(ls(p),l,mid,nl,nr);
49     if(nr>mid) ans+=query(rs(p),mid+1,r,nl,nr);
50     return ans;
51 }
52 int read()
53 {
54     int s=1,x=0;char ch=getchar();
55     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
56     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
57     return s*x;
58 }
59 int main()
60 {
61     int test=read();
62     while(test--)
63     {
64         int n=read();
65         for(int i=1;i<=n;++i)
66         {
67             L[i]=read(),R[i]=read();
68             Hash[(i<<1)-1]=L[i],Hash[i<<1]=R[i];
69         }
70         sort(Hash+1,Hash+2*n+1);
71         
72         int tot=unique(Hash+1,Hash+2*n+1)-Hash-1,tmp=tot;//去重 
73         for(int i=2;i<=tot;++i)
74         if(Hash[i]-Hash[i-1]>1) Hash[++tmp]=Hash[i-1]+1;//相邻两个点的距离大于1则新加一个点 
75         tot=tmp;//离散化后最多tot个点 
76         sort(Hash+1,Hash+tot+1);
77         memset(T,0,sizeof(T));memset(book,0,sizeof(book));
78         for(int i=1;i<=n;++i)
79         {
80             int l=lower_bound(Hash+1,Hash+tot+1,L[i])-Hash;
81             int r=lower_bound(Hash+1,Hash+tot+1,R[i])-Hash;
82             update(1,1,tot,l,r,i);//i代表颜色编号 
83         }    
84         cout<<query(1,1,tot,1,tot)<<endl;
85     }
86 }
View Code

E、Just a Hook

区间修改（改成特定的值）、区间查询（总区间、一次）

 1 #include<bits/stdc++.h>
 2 #define ls(rt) (rt<<1)
 3 #define rs(rt) (rt<<1|1)
 4 using namespace std;
 5 const int MAXN=1e5+5;
 6 struct node
 7 {
 8     int sum,tag;
 9 }T[MAXN<<2];
10 void push_up(int p)
11 {
12     T[p].sum=T[ls(p)].sum+T[rs(p)].sum;
13 }
14 void build(int p,int l,int r)
15 {
16     if(l==r)
17     {
18         T[p].tag=0;
19         T[p].sum=1;
20         return;
21     }
22     T[p].tag=0,T[p].sum=0;
23     int mid=(l+r)>>1;
24     build(ls(p),l,mid);
25     build(rs(p),mid+1,r);
26     push_up(p);
27 }
28 void push_down(int p,int l,int r)
29 {
30     if(!T[p].tag) return ;
31     T[ls(p)].tag=T[p].tag;
32     T[rs(p)].tag=T[p].tag;
33     int mid=(l+r)>>1;
34     T[ls(p)].sum=T[p].tag*(mid-l+1);
35     T[rs(p)].sum=T[p].tag*(r-mid);
36     T[p].tag=0;
37 }
38 void update(int p,int l,int r,int nl,int nr,int k)
39 {
40     if(nl<=l&&nr>=r)
41     {
42         T[p].tag=k;
43         T[p].sum=(r-l+1)*k;
44         return;
45     }
46     push_down(p,l,r);
47     int mid=(l+r)>>1;
48     if(nl<=mid) update(ls(p),l,mid,nl,nr,k);
49     if(nr>mid) update(rs(p),mid+1,r,nl,nr,k);
50     push_up(p);
51 }
52 int query(int p,int l,int r,int nl,int nr)
53 {
54     if(nl<=l&&nr<=r)  return T[p].sum;
55     int ans=0,mid=(l+r)>>1;
56     if(nl<=mid) ans+=query(ls(p),l,mid,nl,nr);
57     if(nr>mid) ans+=query(rs(p),mid+1,r,nl,nr);
58     return ans;
59 }
60 int read()
61 {
62     int s=1,x=0;char ch=getchar();
63     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
64     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
65     return s*x;
66 }
67 int main()
68 {
69     int test=read(),x,y,z;
70     for(int i=1;i<=test;++i)
71     {
72         int n=read();
73         build(1,1,n);
74         int q=read();
75         while(q--)
76         {
77             x=read(),y=read(),z=read();
78             update(1,1,n,x,y,z);
79         }
80         cout<<"Case "<<i<<": ";
81         cout<<"The total value of the hook is ";
82         cout<<query(1,1,n,1,n)<<".
";
83     }
84 }
View Code

F、Count the Colors

 区间修改（改成特定的值）、区间查询（总区间、一次）

这题特殊的是，在[a,b]区间内染色实际上是在第a+1、a+2、...、b个区间内染色，即线段树的第a个叶子结点维护的是[a,a+1]（即第a个）区间的染色情况。

要从左往右遍历叶子结点，实际上和先序遍历得到的叶子结点顺序一样。

  1 #include<iostream>
  2 #include<sstream>
  3 #include<fstream>
  4 #include<algorithm>
  5 #include<cstring>
  6 #include<iomanip>
  7 #include<cstdlib>
  8 #include<cctype>
  9 #include<vector>
 10 #include<string>
 11 #include<cmath>
 12 #include<ctime>
 13 #include<stack>
 14 #include<queue>
 15 #include<map>
 16 #include<set>
 17 #define mem(a,b) memset(a,b,sizeof(a))
 18 #define random(a,b) (rand()%(b-a+1)+a)
 19 #define ll long long
 20 #define ull unsigned long long
 21 #define e 2.71828182
 22 #define Pi acos(-1.0)
 23 #define ls(rt) (rt<<1)
 24 #define rs(rt) (rt<<1|1)
 25 #define lowbit(x) (x&(-x))
 26 using namespace std;
 27 const int MAXN=8e3+5;
 28 int x1[MAXN],x2[MAXN],c[MAXN];
 29 int color[MAXN];
 30 struct node
 31 {
 32     int tag;    
 33 }T[MAXN<<2];
 34 int n;
 35 int read()
 36 {
 37     int s=1,x=0;
 38     char ch=getchar();
 39     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
 40     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
 41     return x*s;
 42 }
 43 void build(int p,int l,int r)
 44 {
 45     if(l==r)
 46     {
 47         T[p].tag=-1;
 48         return;
 49     }
 50     T[p].tag=-1;
 51     int mid=(l+r)>>1;
 52     build(ls(p),l,mid);
 53     build(rs(p),mid+1,r);
 54 }
 55 void push_down(int p,int l,int r)
 56 {
 57     if(T[p].tag==-1) return;
 58     T[ls(p)].tag=T[p].tag;
 59     T[rs(p)].tag=T[p].tag;
 60     T[p].tag=-1;
 61 }
 62 void update(int p,int l,int r,int nl,int nr,int k)
 63 {
 64     if(nl<=l&&nr>=r)
 65     {
 66         T[p].tag=k;
 67         return;
 68     }
 69     int mid=(l+r)>>1;
 70     push_down(p,l,r);
 71     if(nl<=mid) update(ls(p),l,mid,nl,nr,k);
 72     if(nr>mid) update(rs(p),mid+1,r,nl,nr,k);
 73     
 74 }
 75 vector<int> buf;
 76 void query(int p,int l,int r)
 77 {
 78     if(l==r)
 79     {
 80         buf.push_back(T[p].tag);
 81         return;
 82     }
 83     push_down(p,l,r);
 84     int mid=(l+r)>>1;
 85     query(ls(p),l,mid);
 86     query(rs(p),mid+1,r);
 87 }
 88 /*int last;
 89 void query(int p,int l,int r)
 90 {
 91     if(l==r)
 92     {
 93         if(T[p].tag!=-1&&T[p].tag!=last)
 94         {
 95             color[T[p].tag]++;
 96         }
 97         last=T[p].tag;
 98         return;
 99     }
100     push_down(p,l,r);
101     int mid=(l+r)>>1;
102     query(ls(p),l,mid);
103     query(rs(p),mid+1,r);
104 }*/
105 int main()
106 {
107     while(~scanf("%d",&n))
108     {
109         //last=-1;
110         int tot=-1,mxc=-1;
111         buf.clear();
112         mem(color,0);
113         for(int i=1;i<=n;++i)
114         x1[i]=read()+1,x2[i]=read(),c[i]=read(),
115         tot=max(tot,x2[i]),mxc=max(mxc,c[i]);
116         
117         build(1,1,tot);
118         
119         for(int i=1;i<=n;++i)
120         update(1,1,tot,x1[i],x2[i],c[i]);
121         
122         query(1,1,tot);
123         
124         if(buf[0]!=-1) color[buf[0]]++;
125         for(int i=1;i<tot;++i)
126         {
127             if(buf[i]==-1) continue;
128             if(buf[i]==buf[i-1]) continue;
129             else color[buf[i]]++;
130         }
131         //for(int i=0;i<tot;++i) cout<<buf[i]<<' ';cout<<endl;
132         
133         for(int i=0;i<=mxc;++i)
134         if(color[i]) cout<<i<<' '<<color[i]<<"
";
135         cout<<endl;
136     }
137     return 0;
138 }
View Code
  1 #include<iostream>
  2 #include<sstream>
  3 #include<fstream>
  4 #include<algorithm>
  5 #include<cstring>
  6 #include<iomanip>
  7 #include<cstdlib>
  8 #include<cctype>
  9 #include<vector>
 10 #include<string>
 11 #include<cmath>
 12 #include<ctime>
 13 #include<stack>
 14 #include<queue>
 15 #include<map>
 16 #include<set>
 17 #define mem(a,b) memset(a,b,sizeof(a))
 18 #define random(a,b) (rand()%(b-a+1)+a)
 19 #define ll long long
 20 #define ull unsigned long long
 21 #define e 2.71828182
 22 #define Pi acos(-1.0)
 23 #define ls(rt) (rt<<1)
 24 #define rs(rt) (rt<<1|1)
 25 #define lowbit(x) (x&(-x))
 26 using namespace std;
 27 const int MAXN=8e3+5;
 28 int x1[MAXN],x2[MAXN],c[MAXN];
 29 int color[MAXN];
 30 struct node
 31 {
 32     int tag;    
 33 }T[MAXN<<2];
 34 int n;
 35 int read()
 36 {
 37     int s=1,x=0;
 38     char ch=getchar();
 39     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
 40     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
 41     return x*s;
 42 }
 43 void build(int p,int l,int r)
 44 {
 45     if(l==r)
 46     {
 47         T[p].tag=-1;
 48         return;
 49     }
 50     T[p].tag=-1;
 51     int mid=(l+r)>>1;
 52     build(ls(p),l,mid);
 53     build(rs(p),mid+1,r);
 54 }
 55 void push_down(int p,int l,int r)
 56 {
 57     if(T[p].tag==-1) return;
 58     T[ls(p)].tag=T[p].tag;
 59     T[rs(p)].tag=T[p].tag;
 60     T[p].tag=-1;
 61 }
 62 void update(int p,int l,int r,int nl,int nr,int k)
 63 {
 64     if(nl<=l&&nr>=r)
 65     {
 66         T[p].tag=k;
 67         return;
 68     }
 69     int mid=(l+r)>>1;
 70     push_down(p,l,r);
 71     if(nl<=mid) update(ls(p),l,mid,nl,nr,k);
 72     if(nr>mid) update(rs(p),mid+1,r,nl,nr,k);
 73     
 74 }
 75 vector<int> buf;
 76 void query(int p,int l,int r,int nl,int nr)
 77 {
 78     if(l==r)
 79     {
 80         buf.push_back(T[p].tag);
 81         return;
 82     }
 83     push_down(p,l,r);
 84     int mid=(l+r)>>1;
 85     if(nl<=mid) query(ls(p),l,mid,nl,nr);
 86     if(nr>mid) query(rs(p),mid+1,r,nl,nr);
 87 }
 88 int main()
 89 {
 90     while(~scanf("%d",&n))
 91     {
 92         int tot=-1,mxc=-1;
 93         buf.clear();
 94         mem(color,0);
 95         for(int i=1;i<=n;++i)
 96         x1[i]=read()+1,x2[i]=read(),c[i]=read(),
 97         tot=max(tot,x2[i]),mxc=max(mxc,c[i]);
 98         
 99         build(1,1,tot);
100         
101         for(int i=1;i<=n;++i)
102         update(1,1,tot,x1[i],x2[i],c[i]);
103         
104         query(1,1,tot,1,tot);
105         
106         if(buf[0]!=-1) color[buf[0]]++;
107         for(int i=1;i<tot;++i)
108         {
109             if(buf[i]==-1) continue;
110             if(buf[i]==buf[i-1]) continue;
111             else color[buf[i]]++;
112         }
113         //for(int i=0;i<tot;++i) cout<<buf[i]<<' ';cout<<endl;
114         
115         for(int i=0;i<=mxc;++i)
116         if(color[i]) cout<<i<<' '<<color[i]<<"
";
117         cout<<endl;
118     }
119 }
View Code

G、Balanced Lineup

 区间查询最大最小值

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #define ls(p) (p<<1)
 5 #define rs(p) (p<<1|1)
 6 using namespace std;
 7 const int MAXN=5e4+5;
 8 int a[MAXN];
 9 struct node
10 {
11     int big,small;
12 }T[MAXN<<2];
13 void push_up(int p)
14 {
15     T[p].big=max(T[ls(p)].big,T[rs(p)].big);
16     T[p].small=min(T[ls(p)].small,T[rs(p)].small);
17 }
18 void build(int p,int l,int r)
19 {
20     if(l==r)
21     {
22         T[p].big=T[p].small=a[l];
23         return;
24     }
25     T[p].big=-1,T[p].small=0x7fffffff;
26     int mid=(l+r)>>1;
27     build(ls(p),l,mid);
28     build(rs(p),mid+1,r);
29     push_up(p);
30 }
31 int query_big(int p,int l,int r,int nl,int nr)
32 {
33     if(nl<=l&&nr>=r) return T[p].big;
34     int ans=-1,mid=(l+r)>>1;
35     if(nl<=mid) ans=max(ans,query_big(ls(p),l,mid,nl,nr));
36     if(nr>mid) ans=max(ans,query_big(rs(p),mid+1,r,nl,nr));
37     return ans;
38 }
39 int query_small(int p,int l,int r,int nl,int nr)
40 {
41     if(nl<=l&&nr>=r) return T[p].small;
42     int ans=0x7fffffff,mid=(l+r)>>1;
43     if(nl<=mid) ans=min(ans,query_small(ls(p),l,mid,nl,nr));
44     if(nr>mid) ans=min(ans,query_small(rs(p),mid+1,r,nl,nr));
45     return ans;
46 }
47 int read()
48 {
49     int x=0,s=1;char ch=getchar();
50     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
51     while(isdigit(ch))     {x=10*x+ch-'0';ch=getchar();}
52     return x*s;
53 }
54 int main()
55 {
56     int n=read(),q=read();
57     for(int i=1;i<=n;++i) a[i]=read();
58     build(1,1,n);
59     while(q--)
60     {
61         int L=read(),R=read();
62         cout<<query_big(1,1,n,L,R)-query_small(1,1,n,L,R)<<"
";
63     }
64     return 0;
65 }
View Code

H、Can you answer these queries?

区间修改是区间中的每个元素开平方，无法通过push_down操作，只能对叶子结点一个一个开平方，如果单单这样是会超时的，注意到开平方时数据大小衰减得很快，最少降到1，可以利用这一点进行剪枝。

还有个很坑的是，题中所给的x，y并未给定相对大小，注意一下

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<cmath>
 5 #define ls(p) (p<<1)
 6 #define rs(p) (p<<1|1)
 7 #define ll long long
 8 using namespace std;
 9 const int MAXN=1e5+5;
10 ll a[MAXN];
11 struct node
12 {
13     ll sum;
14 }T[MAXN<<2];
15 void push_up(int p)
16 {
17     T[p].sum=T[ls(p)].sum+T[rs(p)].sum;
18 }
19 void build(int p,int l,int r)
20 {
21     if(l==r)
22     {
23         T[p].sum=a[l];
24         return;
25     }
26     T[p].sum=0;
27     int mid=(l+r)>>1;
28     build(ls(p),l,mid);
29     build(rs(p),mid+1,r);
30     push_up(p);
31 }
32 void update(int p,int l,int r,int nl,int nr)
33 {
34     if(T[p].sum==(r-l+1)) return;
35     if(l==r)
36     {
37         T[p].sum=sqrt(T[p].sum);
38         return;
39     }
40     int mid=(l+r)>>1;
41     if(nl<=mid) update(ls(p),l,mid,nl,nr);
42     if(nr>mid) update(rs(p),mid+1,r,nl,nr);
43     push_up(p);
44 }
45 ll query(int p,int l,int r,int nl,int nr)
46 {
47     if(nl<=l&&nr>=r) return T[p].sum;
48     ll ans=0;int mid=(l+r)>>1;
49     if(nl<=mid) ans+=query(ls(p),l,mid,nl,nr);
50     if(nr>mid) ans+=query(rs(p),mid+1,r,nl,nr);
51     return ans;
52 }
53 ll read()
54 {
55     ll x=0,s=1;char ch=getchar();
56     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
57     while(isdigit(ch))     {x=10*x+ch-'0';ch=getchar();}
58     return x*s;
59 }
60 int main()
61 {
62     int n,q,t,x,y,cnt=0;
63     while(~scanf("%d",&n))
64     {
65         cout<<"Case #"<<++cnt<<":
";
66         for(int i=1;i<=n;++i) a[i]=read();
67         build(1,1,n);
68         q=read();
69         while(q--)
70         {
71             t=read(),x=read(),y=read();
72             if(x>y) swap(x,y);//这题这里恶心 
73             if(t) cout<<query(1,1,n,x,y)<<"
";
74             else update(1,1,n,x,y);
75         }
76         cout<<endl;
77     }
78     return 0;
79 }
View Code

I、Tunnel Warfare

 找最大连续区间

维护最长前缀、最长后缀、最长连续区间

HDU有毒吧，有两个输入输出方面的bug调了我一上午

一个是关了同步后，用C++的cout输出，一直是个Output Limit Exceeded

另一个是C的scanf读char，真的是，回车都读进去了，改成char型数组过了

对了，这题有两个思路：

一个是就如上所说，求最大连续区间。（就是这个，没用快读，找了一早上的bug）

  1 #include<bits/stdc++.h>
  2 #define ls(p) (p<<1)
  3 #define rs(p) (p<<1|1)
  4 using namespace std;
  5 const int MAXN=5e4+5;
  6 struct node
  7 {
  8     int pre,suf,maxlen;//左边连续最长、右边连续最长、最长 
  9 }T[MAXN<<2];
 10 void push_up(int p,int l,int r)
 11 {
 12     int mid=(l+r)>>1;
 13     T[p].pre= T[ls(p)].pre==mid-l+1? T[ls(p)].pre+T[rs(p)].pre : T[ls(p)].pre;
 14     T[p].suf= T[rs(p)].suf==r-mid? T[rs(p)].suf+T[ls(p)].suf : T[rs(p)].suf;
 15     T[p].maxlen= max( max(T[ls(p)].maxlen,T[rs(p)].maxlen), T[ls(p)].suf+T[rs(p)].pre );
 16 }
 17 void build(int p,int l,int r)
 18 {
 19     if(l==r)
 20     {
 21         T[p].maxlen=T[p].pre=T[p].suf=1;
 22         return;
 23     }
 24     int mid=(l+r)>>1;
 25     build(ls(p),l,mid);
 26     build(rs(p),mid+1,r);
 27     push_up(p,l,r);
 28 }
 29 void update(int p,int l,int r,int lr,int k)
 30 {
 31     if(l==r)
 32     {
 33         T[p].maxlen=T[p].pre=T[p].suf=k;
 34         return;
 35     }
 36     int mid=(l+r)>>1;
 37     if(lr<=mid) update(ls(p),l,mid,lr,k);
 38     else update(rs(p),mid+1,r,lr,k);
 39     push_up(p,l,r);
 40 }
 41 int query(int p,int l,int r,int lr)
 42 {
 43     if(l==r||T[p].maxlen==r-l+1||T[p].maxlen==0) return T[p].maxlen;
 44     int mid=(l+r)>>1;
 45     if(lr<=mid)
 46     {
 47         if(mid-lr+1<=T[ls(p)].suf) return query(ls(p),l,mid,lr)+T[rs(p)].pre;
 48         else return query(ls(p),l,mid,lr);    
 49     } 
 50     else
 51     {
 52         if(lr-mid<=T[rs(p)].pre) return T[ls(p)].suf+query(rs(p),mid+1,r,lr);
 53         else return query(rs(p),mid+1,r,lr);
 54     }
 55 }
 56 int main()
 57 {
 58     int n,m,x;
 59     char ord[10];
 60     stack<int> buf;
 61     while(~scanf("%d%d",&n,&m))
 62     {
 63         build(1,1,n);
 64         while(!buf.empty()) buf.pop();
 65         for(int i=1;i<=m;++i)
 66         {
 67             scanf("%s",ord);
 68             if(ord[0]=='D') 
 69             {
 70                 scanf("%d",&x);
 71                 buf.push(x);
 72                 update(1,1,n,x,0);
 73             }
 74             else if(ord[0]=='R')
 75             {
 76                 if(!buf.empty())
 77                 {
 78                     x=buf.top();
 79                     buf.pop();
 80                     update(1,1,n,x,1);
 81                 }
 82             }
 83             else if(ord[0]=='Q')
 84             {
 85                 scanf("%d",&x);
 86                 printf("%d
",query(1,1,n,x));
 87             }
 88         }
 89     }
 90     return 0;    
 91 } 
 92 /*
 93 7 9
 94 D 3
 95 D 6
 96 D 5
 97 Q 4
 98 Q 5
 99 R
100 Q 4
101 R
102 Q 4
103 */
View Code

另一个思路比较巧妙，找最大连续区间，就是找出左端最大的不满足的端点和右端最小的不满足的端点。

  1 #include<iostream>
  2 #include<sstream>
  3 #include<fstream>
  4 #include<algorithm>
  5 #include<cstring>
  6 #include<iomanip>
  7 #include<cstdlib>
  8 #include<cctype>
  9 #include<vector>
 10 #include<string>
 11 #include<cmath>
 12 #include<ctime>
 13 #include<stack>
 14 #include<queue>
 15 #include<map>
 16 #include<set>
 17 #define mem(a,b) memset(a,b,sizeof(a))
 18 #define random(a,b) (rand()%(b-a+1)+a)
 19 #define ll long long
 20 #define ull unsigned long long
 21 #define e 2.71828182
 22 #define Pi acos(-1.0)
 23 #define ls(rt) (rt<<1)
 24 #define rs(rt) (rt<<1|1)
 25 #define lowbit(x) (x&(-x))
 26 using namespace std;
 27 const int MAXN=5e4+5;
 28 //const int INF=0x7fffffff;
 29 struct node
 30 {
 31     int big,small;
 32 }T[MAXN<<2]; 
 33 stack<int> buf;
 34 int n,m,x;
 35 /*void push_up(int p)
 36 {
 37     T[p].big=max(T[ls(p)].big,T[rs(p)].big);
 38     T[p].small=min(T[ls(p)].small,T[rs(p)].small);
 39 }*/
 40 /*void show1(int p,int l,int r)
 41 {
 42     if(l==r)
 43     {
 44         cout<<T[p].big<<' ';
 45         return;
 46     }
 47     int mid=(l+r)>>1;
 48     show1(ls(p),l,mid);
 49     show1(rs(p),mid+1,r);
 50 }
 51 void show2(int p,int l,int r)
 52 {
 53     if(l==r)
 54     {
 55         cout<<T[p].small<<' ';
 56         return;
 57     }
 58     int mid=(l+r)>>1;
 59     show2(ls(p),l,mid);
 60     show2(rs(p),mid+1,r);
 61 }*/
 62 void build(int p,int l,int r)
 63 {
 64     if(l==r)
 65     {
 66         T[p].big=0,T[p].small=n+1;
 67         return;
 68     }
 69     T[p].big=0,T[p].small=n+1;
 70     int mid=(l+r)>>1;
 71     build(ls(p),l,mid);
 72     build(rs(p),mid+1,r);
 73 }
 74 void update_max(int p,int l,int r,int lr,int k)
 75 {
 76     if(l==r)
 77     {
 78         T[p].big=k;
 79         return;
 80     }
 81     int mid=(l+r)>>1;
 82     if(lr<=mid) update_max(ls(p),l,mid,lr,k);
 83     else update_max(rs(p),mid+1,r,lr,k);
 84     T[p].big=max(T[ls(p)].big,T[rs(p)].big);
 85 }
 86 void update_min(int p,int l,int r,int lr,int k)
 87 {
 88     if(l==r)
 89     {
 90         T[p].small=k;
 91         return;
 92     }
 93     int mid=(l+r)>>1;
 94     if(lr<=mid) update_min(ls(p),l,mid,lr,k);
 95     else update_min(rs(p),mid+1,r,lr,k);
 96     T[p].small=min(T[ls(p)].small,T[rs(p)].small);
 97 }
 98 int query_max(int p,int l,int r,int nl,int nr)
 99 {
100     if(nl<=l&&nr>=r) return T[p].big;
101     int mid=(l+r)>>1,ans=0;
102     if(nl<=mid) ans=max(ans,query_max(ls(p),l,mid,nl,nr));
103     if(nr>mid) ans=max(ans,query_max(rs(p),mid+1,r,nl,nr));
104     return ans;
105 }
106 int query_min(int p,int l,int r,int nl,int nr)
107 {
108     if(nl<=l&&nr>=r) return T[p].small;
109     int mid=(l+r)>>1,ans=n+1;
110     if(nl<=mid) ans=min(ans,query_min(ls(p),l,mid,nl,nr));
111     if(nr>mid) ans=min(ans,query_min(rs(p),mid+1,r,nl,nr));
112     return ans;
113 }
114 int read()
115 {
116     int s=1,x=0;
117     char ch=getchar();
118     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
119     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
120     return x*s;
121 }
122 int main()
123 {
124     while(~scanf("%d%d",&n,&m))
125     {
126         char ord;
127         build(1,1,n);
128         while(!buf.empty()) buf.pop();
129         while(m--)
130         {
131             cin>>ord;
132             if(ord=='D')
133             {
134                 x=read();
135                 buf.push(x);
136                 update_max(1,1,n,x,x);
137                 update_min(1,1,n,x,x);
138             }
139             else if(ord=='R')
140             {
141                 if(buf.empty()) exit(-1);
142                 x=buf.top();buf.pop();
143                 update_max(1,1,n,x,0);
144                 update_min(1,1,n,x,n+1);
145             }
146             else if(ord=='Q')
147             {
148                 x=read();
149                 int Lmax=query_max(1,1,n,1,x),Rmin=query_min(1,1,n,x,n);
150                 if(Lmax==Rmin) cout<<"0
";
151                 else  cout<<Rmin-Lmax-1<<"
";
152             }
153         }
154     }
155     return 0;
156 }
View Code

J、Assign the task

DFS序

  1 #include<bits/stdc++.h>
  2 #define ls(p) (p<<1)
  3 #define rs(p) (p<<1|1)
  4 using namespace std;
  5 const int MAXN=2e5+5;
  6 vector<int> G[MAXN];
  7 int l[MAXN],r[MAXN];
  8 int root[MAXN];
  9 int n,m,u,v;
 10 int cnt;
 11 struct node
 12 {
 13     int tag;
 14 }T[MAXN<<2];
 15 void build(int p,int l,int r)
 16 {
 17     T[p].tag=-1;
 18     if(l==r) return;
 19     int mid=(l+r)>>1;
 20     build(ls(p),l,mid);
 21     build(rs(p),mid+1,r);
 22 }
 23 void push_down(int p)
 24 {
 25     if(T[p].tag==-1) return;
 26     T[ls(p)].tag=T[p].tag;
 27     T[rs(p)].tag=T[p].tag;
 28     T[p].tag=-1;
 29 }
 30 void update(int p,int l,int r,int nl,int nr,int k)
 31 {
 32     if(nl<=l&&nr>=r)
 33     {
 34         T[p].tag=k;
 35         return;
 36     }
 37     int mid=(l+r)>>1;
 38     push_down(p);
 39     if(nl<=mid) update(ls(p),l,mid,nl,nr,k);
 40     if(nr>mid) update(rs(p),mid+1,r,nl,nr,k);
 41 }
 42 int query(int p,int l,int r,int lr)
 43 {
 44     if(l==r) return T[p].tag;
 45     int mid=(l+r)>>1;
 46     push_down(p);
 47     if(lr<=mid) return query(ls(p),l,mid,lr);
 48     else return query(rs(p),mid+1,r,lr);
 49 }
 50 int read()
 51 {
 52     int x=0,s=1;char ch=getchar();
 53     while(!isdigit(ch)){if(ch=='-') s=-1;ch=getchar();}
 54     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
 55     return x*s;
 56 }
 57 void dfs(int p)
 58 {
 59     l[p]=++cnt;
 60     for(int i=0;i<G[p].size();++i)
 61     dfs(G[p][i]);
 62     r[p]=cnt;
 63 }
 64 int main()
 65 {
 66     int cas=read(),x,y;
 67     char c[10];
 68     for(int j=1;j<=cas;++j)
 69     {
 70         cout<<"Case #"<<j<<":
";
 71         n=read();
 72         memset(root,0,sizeof(root));
 73         for(int i=1;i<=n-1;++i)
 74         {
 75             u=read(),v=read();
 76             G[v].push_back(u);
 77             root[u]=1;
 78         }
 79         cnt=0;
 80         for(int i=1;i<=n;++i)
 81         if(!root[i]) dfs(i);
 82         
 83         /*for(int i=1;i<=n;++i)
 84         cout<<l[i]<<' '<<r[i]<<endl;*/
 85         build(1,1,n);
 86         m=read();
 87         while(m--)
 88         {
 89             scanf("%s",c);
 90             if(c[0]=='C')
 91             {
 92                 x=read();
 93                 cout<<query(1,1,n,l[x])<<"
";
 94             }
 95             else if(c[0]=='T')
 96             {
 97                 x=read(),y=read();
 98                 update(1,1,n,l[x],r[x],y);
 99             }
100         }
101         
102         for(int i=1;i<=n;++i) G[i].clear();
103     }
104     return 0;
105 }
View Code

K、Transformation

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/wangzhebufangqi/p/11337102.html