线段树模板（待补充）

下定决心要学线段树了，每种类型的线段树题都弄一个代码模板吧（直接拿模板题的代码），有遇到新的类型会补上去的。

一、区间求最值（单点修改）：

 1 #include<iostream>
 2 #define LC(a)  ((a<<1))
 3 #define RC(a)  ((a<<1)+1)
 4 #define MID(a,b) ((a+b)>>1)
 5 using namespace std;
 6 typedef long long ll;
 7 const int N=1e4*4;
 8 
 9 ll mmin,mmax;
10 
11 struct node{
12     ll l,r;
13     ll mmin,mmax;    
14 }tree[N];
15 
16 ll num[N];
17 
18 void pushup(ll p)  
19 {  
20     tree[p].mmin=min(tree[LC(p)].mmin, tree[RC(p)].mmin);
21     tree[p].mmax=max(tree[LC(p)].mmax,tree[RC(p)].mmax);
22 }
23 
24 void build(ll p,ll l,ll r){
25     tree[p].l=l;
26     tree[p].r=r;
27     tree[p].mmax=0;
28     tree[p].mmin=1e10;
29     if(l==r){
30         tree[p].mmax=tree[p].mmin=num[l];
31         return;
32     }
33     build(LC(p),l,MID(l,r));
34     build(RC(p),MID(l,r)+1,r);
35     pushup(p);//往上推 
36 }
37 
38 void update(ll p,ll l,ll r,ll num){
39     if(r<tree[p].l||l>tree[p].r)
40         return;
41     if(l<=tree[p].l&&r>=tree[p].r){    
42         tree[p].mmin=tree[p].mmax=num;
43         return;
44     }
45     update(LC(p),l,r,num);
46     update(RC(p),l,r,num);
47     pushup(p);
48 }
49 
50 void query(ll p,ll l,ll r){
51     if(r<tree[p].l||l>tree[p].r)
52         return;
53     if(l<=tree[p].l&&r>=tree[p].r){
54         mmin=min(tree[p].mmin,mmin);
55         mmax=max(tree[p].mmax,mmax);
56         return;
57     }
58     query(LC(p),l,r);
59     query(RC(p),l,r);
60 }
61 
62 int main(){
63     int t;
64     cin>>t;
65     while(t--){
66         int n,q;
67         cin>>n>>q;
68         for(int i=1;i<=n;i++){
69             cin>>num[i];
70         }
71         build(1,1,n);
72         for(int i=1;i<=q;i++){
73             int p;
74             cin>>p;
75             if(p==1){
76                 ll l,r;
77                 cin>>l>>r;
78                 mmin=1e10;
79                 mmax=0;
80                 query(1,l,r);
81                 cout<<mmax-mmin<<endl;
82             }
83             else{
84                 ll x,idx;    
85                 cin>>x>>idx;
86                 update(1,x,x,idx);
87             }
88         }
89     } 
90 }

View Code

此代码相关题目：NOJ1680，单点修改求区间最值，模板题

https://ac.2333.moe/Problem/view.xhtml?id=1680

二、区间求和（区间修改）：

这里由于是在区间上修改值，所以是要有lazy标记的，不可能每次都把每个点的值都改掉，这里的add就是lazy标记，用来延迟修改区间值，只有当访问到相应区间时才修改该区间的值，否则就把add值都存起来。

 1 #include<iostream>
 2 #define LC(a) ((a<<1))
 3 #define RC(a) ((a<<1)+1)
 4 #define MID(a,b)   ((a+b)>>1)
 5 using namespace std;
 6 typedef long long ll;
 7 const int N=5e5*4;
 8 
 9 struct node{
10     ll l,r;
11     ll sum,add;
12 }tree[N];
13 
14 ll ans=0;
15 //上推 
16 void pushup(ll p){
17     tree[p].sum=tree[LC(p)].sum+tree[RC(p)].sum;
18 }
19 //下推
20 void pushdown(ll p){
21     tree[LC(p)].add+=tree[p].add;
22     tree[RC(p)].add+=tree[p].add;
23     //**不要错写成tree[LC(p)].sum+=tree[LC(p)].add*(tree[LC(p)].r-tree[LC(p)].l+1); 
24     tree[LC(p)].sum+=tree[p].add*(tree[LC(p)].r-tree[LC(p)].l+1); 
25     tree[RC(p)].sum+=tree[p].add*(tree[RC(p)].r-tree[RC(p)].l+1);
26     tree[p].add=0;
27 } 
28 
29 void build(ll p,ll l,ll r){
30     tree[p].l=l;
31     tree[p].r=r;
32     tree[p].sum=tree[p].add=0;
33     if(l==r){
34         cin>>tree[p].sum;
35         return;
36     }
37     build(LC(p),l,MID(l,r));
38     build(RC(p),MID(l,r)+1,r);
39     pushup(p);
40 }
41 
42 void updata(ll p,ll l,ll r,ll num){
43     if(r<tree[p].l||l>tree[p].r)
44         return;
45     if(l<=tree[p].l&&r>=tree[p].r){
46         tree[p].add+=num;
47         //**千万不要错写成 tree[p].sum+=tree[p].add*(tree[p].r-tree[p].l+1);
48         tree[p].sum+=num*(tree[p].r-tree[p].l+1);
49         return;
50     }
51     //访问到该区间下面时，释放lazy标记 
52     if(tree[p].add)
53         pushdown(p);
54     updata(LC(p),l,r,num);
55     updata(RC(p),l,r,num);
56     pushup(p);
57 } 
58 
59 void query(ll p,ll l, ll r){
60     if(r<tree[p].l||l>tree[p].r)
61         return;
62     if(l<=tree[p].l&&r>=tree[p].r){
63         ans+=tree[p].sum;
64         return;
65     }
66     //访问到该区间下面时，释放lazy标记 
67     if(tree[p].add)
68         pushdown(p);
69     query(LC(p),l,r);
70     query(RC(p),l,r);
71 }
72 
73 int main(){
74     ios::sync_with_stdio(false);
75     ll n,q;
76     cin>>n>>q;
77     build(1,1,n);
78     while(q--){    
79         char p;
80         cin>>p;
81         if(p=='C'){
82             ll l,r,add;
83             cin>>l>>r>>add;
84             //给区间l~r加上add 
85             updata(1,l,r,add);
86         }
87         else{
88             ll l,r;
89             cin>>l>>r;
90             ans=0;
91             //查询区间l~r的和 
92             query(1,l,r);
93             cout<<ans<<endl; 
94         }
95     }
96 }

View Code

此代码相关题目：POJ3468 A Simple Problem with Integers,模板题

　　　　　http://poj.org/problem?id=3468

三、区间染色(区间修改)

由于是区间修改，同样需要lazy标记，这里用color=-1来表示该区间不是纯色。注意这里因题意颜色初始化为1,根据题意不同颜色初始化也不同：

 1 #include<cstring>
 2 #include<stdio.h>
 3 #define LC(a) ((a<<1))
 4 #define RC(a) ((a<<1)+1)
 5 #define MID(a,b) ((a+b)>>1) 
 6 typedef long long ll;
 7 const int N=1e5*4;
 8 
 9 struct node{
10     ll l,r;
11     ll color;//颜色为-1表示混合色 
12 }tree[N];
13 
14 ll ans[35]; 
15 //下推 
16 void pushdown(ll p){
17     tree[RC(p)].color=tree[LC(p)].color=tree[p].color;
18 }
19 //上推 
20 void pushup(ll p){
21     tree[p].color=(tree[LC(p)].color==tree[RC(p)].color?tree[LC(p)].color:-1);
22 }
23 
24 void build(ll p,ll l,ll r){
25     tree[p].l=l;
26     tree[p].r=r;
27     tree[p].color=1;//初始化颜色因题意而定 
28     if(l==r){
29         return;
30     }
31     build(LC(p),l,MID(l,r));
32     build(RC(p),MID(l,r)+1,r);
33 }
34 
35 void update(ll p,ll l,ll r,ll color){
36     if(r<tree[p].l||l>tree[p].r)
37         return;
38     if(l<=tree[p].l&&r>=tree[p].r){
39         tree[p].color=color;        
40         return;
41     }
42     //**释放lazy标记 
43     if(tree[p].color!=-1){
44         pushdown(p);
45     }
46     update(LC(p),l,r,color);
47     update(RC(p),l,r,color);
48     pushup(p);
49 }
50 
51 void query(ll p,ll l,ll r){
52     if(r<tree[p].l||l>tree[p].r)
53         return;
54     //纯色，不用再找下去 
55     if(tree[p].color!=-1){
56         ans[tree[p].color]=1;
57         return;
58     }        
59     query(LC(p),l,r);
60     query(RC(p),l,r);
61 }
62 
63 int main(){
64     ll L,t,o;
65     scanf("%I64d %I64d %I64d",&L,&t,&o);
66     build(1,1,L);
67     while(o--){
68         char p[15];
69         scanf("%s",p);
70         if(p[0]=='C'){
71             ll l,r,color;
72             scanf("%I64d %I64d %I64d",&l,&r,&color);
73             if(l>r)//l可能大于r 
74                 update(1,r,l,color);
75             else
76                 update(1,l,r,color);
77         }
78         else{
79             ll l,r;
80             scanf("%I64d %I64d",&l,&r);
81             memset(ans,0,sizeof(ans));
82             if(l>r)
83                 query(1,r,l);
84             else
85                 query(1,l,r);    
86             ll sum=0;
87             for(int i=1;i<=t;i++){
88                 if(ans[i])
89                     sum++;
90             }
91             printf("%I64d
",sum);
92         }
93     }
94 }

View Code

此代码相关题目：POJ 2777 Count Color，模板题

http://poj.org/problem?id=2777

四、区间合并（单点修改）

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #define LC(a) ((a<<1))
  5 #define RC(a)  ((a<<1)+1) 
  6 #define MID(a,b) ((a+b)>>1)
  7 using namespace std; 
  8 const int N=5e4+5;
  9 typedef long long ll;
 10 
 11 struct node{
 12     ll l,r;
 13     ll ls,rs,ms;//左端最大连续区间，右端最大连续区间，整个区间的最大连续区间 
 14 }tree[N*4];
 15 
 16 ll ans,cnt;//cnt记录被摧毁点的数量 
 17 ll last[N];//记录摧毁的点 
 18  
 19 //上推 
 20 void pushup(ll p){
 21     //左子树区间满了的话，父亲左区间要加上右子树的左区间 
 22     tree[p].ls=(tree[LC(p)].ls==tree[LC(p)].r-tree[LC(p)].l+1?tree[LC(p)].ls+tree[RC(p)].ls:tree[LC(p)].ls);
 23     //同理 
 24     tree[p].rs=(tree[RC(p)].rs==tree[RC(p)].r-tree[RC(p)].l+1?tree[RC(p)].rs+tree[LC(p)].rs:tree[RC(p)].rs);
 25     //父亲最大区间必定是，左子树最大区间，右子树最大区间，左右子树合并的中间区间，三者中的最大值   
 26     tree[p].ms=max(max(tree[LC(p)].ms,tree[RC(p)].ms),tree[LC(p)].rs+tree[RC(p)].ls);
 27 }
 28 
 29 void build(ll p,ll l,ll r){
 30     tree[p].l=l;
 31     tree[p].r=r;
 32     tree[p].ms=tree[p].ls=tree[p].rs=0;
 33     if(l==r){
 34         tree[p].ls=tree[p].ms=tree[p].rs=1;
 35         return;
 36     }
 37     build(LC(p),l,MID(l,r));
 38     build(RC(p),MID(l,r)+1,r);
 39     pushup(p);
 40 }
 41 
 42 void update(ll p,ll t,ll op){
 43     if(tree[p].l==tree[p].r){
 44         if(op==1)
 45             tree[p].ls=tree[p].ms=tree[p].rs=1;
 46         else
 47             tree[p].ls=tree[p].ms=tree[p].rs=0;
 48         return;
 49     }
 50     ll mid=MID(tree[p].l,tree[p].r);
 51     if(t<=mid)    
 52         update(LC(p),t,op); 
 53     else    
 54         update(RC(p),t,op);
 55     pushup(p);
 56 }
 57 
 58 void query(ll p,ll t){
 59     if(tree[p].ms==0||tree[p].ms==tree[p].r-tree[p].l+1){
 60         ans+=tree[p].ms;
 61         return;
 62     }
 63     ll mid=MID(tree[p].l,tree[p].r);
 64     if(t<=mid){
 65         //点t在左子树,判断t如果在左子树右边界内,直接加上左子树右区间以及右子树左区间的长度和 
 66         if(t>=tree[LC(p)].r-tree[LC(p)].rs+1){
 67             ans+=tree[LC(p)].rs+tree[RC(p)].ls; 
 68             return; 
 69         }
 70         else    
 71             query(LC(p),t);        
 72     }
 73     else{
 74         //同理
 75         if(t<=tree[RC(p)].l+tree[RC(p)].ls-1){
 76             ans+=tree[RC(p)].ls+tree[LC(p)].rs;
 77             return;
 78         }
 79         else
 80             query(RC(p),t);
 81     }
 82 }
 83 
 84 int main(){
 85     ios::sync_with_stdio(false);
 86     ll n,q;
 87     while(cin>>n>>q){
 88         cnt=0;     
 89         build(1,1,n);
 90         while(q--){
 91             char p;
 92             ll t;
 93             cin>>p;
 94             if(p=='D'){
 95                 cin>>t;
 96                 last[++cnt]=t;
 97                 update(1,t,0);
 98             }
 99             else if(p=='R'){
100                 //修复 
101                 if(cnt!=0){
102                     t=last[cnt--];
103                     update(1,t,1);
104                 }
105             }
106             else{
107                 cin>>t;    
108                 ans=0;
109                 query(1,t);
110                 cout<<ans<<endl;
111             }
112         }
113     }
114 }

View Code

此代码相关题目：HDU 1540 tunnel warfare，模板题

　　　　　　　　http://acm.hdu.edu.cn/showproblem.php?pid=1540

五、扫描线计算面积并

具体的解释可以看这里：focus_best，写的很清晰

大概说一下写法，先要把横坐标离散化建树因为有小数，把2*n条上下边从小到大排序，依次扫描，如果是矩形的下位边则覆盖范围cnt-1,若是上位边覆盖范围cnt+1，当cnt>0时把这段计算进去。下面代码中，我是当tree[p]下的区间cnt不是一样时，tree[p].cnt=-1，跟上面染色写法有点像。

代码：

  1 #include<cstdio>
  2 #include<cmath>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<vector>
  7 #include<queue>
  8 #include<set>
  9 #include<map>
 10 #include<stack>
 11 #include<string>
 12 #define LC(a) (a<<1)
 13 #define RC(a) (a<<1|1)
 14 #define MID(a,b) ((a+b)>>1)
 15 using namespace std;
 16 typedef long long LL;
 17 const int INF=0x3f3f3f3f;
 18 const int N=2e2+5;
 19 
 20 struct node{
 21     double x1,x2,h,flag;
 22 }a[N];
 23 
 24 struct node2{
 25     int l,r,cnt;//cnt=-1表示区间cnt不相等 
 26     double sum;
 27 }tree[N<<2];
 28 
 29 double X[N];
 30 
 31 void pushdown(int p){
 32     if(tree[p].cnt<=0){
 33         tree[LC(p)].cnt=tree[RC(p)].cnt=0;
 34         tree[LC(p)].sum=tree[RC(p)].sum=0;
 35     }
 36     else{
 37         tree[LC(p)].cnt=tree[RC(p)].cnt=tree[p].cnt;
 38         tree[LC(p)].sum=X[tree[LC(p)].r+1]-X[tree[LC(p)].l];
 39         tree[RC(p)].sum=X[tree[RC(p)].r+1]-X[tree[RC(p)].l];
 40     }
 41 }
 42 
 43 void pushup(int p){
 44     tree[p].cnt=(tree[LC(p)].cnt==tree[RC(p)].cnt?tree[LC(p)].cnt:-1);
 45     tree[p].sum=tree[LC(p)].sum+tree[RC(p)].sum;
 46 }
 47 
 48 void build(int p,int l,int r){
 49     tree[p].l=l;
 50     tree[p].r=r;
 51     tree[p].cnt=0;
 52     if(l==r){
 53         tree[p].sum=0;
 54         return;
 55     }
 56     build(LC(p),l,MID(l,r));
 57     build(RC(p),MID(l,r)+1,r);
 58     pushup(p);
 59 }
 60 
 61 void update(int p,int l,int r,int cnt){
 62     if(l>tree[p].r||r<tree[p].l)
 63         return;
 64     if(l<=tree[p].l&&r>=tree[p].r&&tree[p].cnt!=-1){
 65         tree[p].cnt+=cnt;
 66         if(tree[p].cnt)
 67             tree[p].sum=X[tree[p].r+1]-X[tree[p].l];
 68         else
 69             tree[p].sum=0;
 70         return;
 71     }
 72     if(tree[p].cnt!=-1)
 73         pushdown(p);
 74     update(LC(p),l,r,cnt);
 75     update(RC(p),l,r,cnt);
 76     pushup(p);
 77 }
 78 
 79 int bin_search(double num,int l,int r){
 80     while(l<=r){
 81         int mid=(l+r)/2;
 82         if(num==X[mid])
 83             return mid;
 84         else if(num<X[mid])
 85             r=mid-1;
 86         else
 87             l=mid+1;
 88     }
 89     return -1;
 90 }
 91 
 92 bool cmp(node a,node b){
 93     return a.h<b.h;
 94 }
 95 
 96 int main(){
 97     int n;
 98     int cas=0;
 99     while(~scanf("%d",&n)&&n){
100         printf("Test case #%d
",++cas);
101         int m1=0,m2=1;
102         for(int i=1;i<=n;i++){
103             double x1,x2,y1,y2;
104             scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
105             X[++m1]=x1;
106             a[m1].x1=x1,a[m1].x2=x2,a[m1].h=y1,a[m1].flag=1;
107             X[++m1]=x2;
108             a[m1].x1=x1,a[m1].x2=x2,a[m1].h=y2,a[m1].flag=-1;
109         }
110         sort(a+1,a+1+m1,cmp);
111         //去重，离散化 
112         sort(X+1,X+1+m1);
113         for(int i=2;i<=m1;i++){
114             if(X[i]!=X[i-1])
115                 X[++m2]=X[i];
116         }
117         
118         build(1,1,m2-1);
119         double ans=0;
120         //这里r-1,是因为原本的l,r是端点上的，而线段树是线段所以要转化一下
121         for(int i=1;i<=m1-1;i++){
122             int l=bin_search(a[i].x1,1,m2);
123             int r=bin_search(a[i].x2,1,m2)-1;
124             update(1,l,r,a[i].flag);
125             ans+=tree[1].sum*(a[i+1].h-a[i].h);
126         }
127         printf("Total explored area: %.2lf

",ans);
128     }
129     return 0;
130 }

View Code

此代码相关题目：HDU 1542 Atlantis，模板题

　　　　　　　　http://acm.hdu.edu.cn/showproblem.php?pid=1542