HDU 6315.Naive Operations-线段树(两棵树合并)(区间单点更新、区间最值、区间求和)+思维 (2018 Multi-University Training Contest 2 1007)

  1 //1007-6315-线段树-其实是两个线段树，合到一起
  2 #include<iostream>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<cmath>
  7 typedef long long ll;
  8 using namespace std;
  9 const int maxn=1e5+500;
 10 const int inf=0x3f3f3f3f;
 11 #define lson l,m,rt<<1
 12 #define rson m+1,r,rt<<1|1
 13 
 14 int tree[maxn<<2],cnt[maxn<<2],col[maxn<<2],b[maxn],n,m;//tree建树求和,col延时标记,cnt暂时标记增加的数量
 15 
 16 void pushup(int rt)
 17 {
 18     cnt[rt]=min(cnt[rt<<1],cnt[rt<<1|1]);
 19     tree[rt]=tree[rt<<1]+tree[rt<<1|1];
 20 }
 21 
 22 void pushdown(int rt)
 23 {
 24     if(col[rt]){
 25         cnt[rt<<1]-=col[rt];
 26         cnt[rt<<1|1]-=col[rt];
 27         col[rt<<1]+=col[rt];
 28         col[rt<<1|1]+=col[rt];
 29         col[rt]=0;
 30     }
 31 }
 32 
 33 void build(int l,int r,int rt)
 34 {
 35     if (l==r){
 36         cnt[rt]=b[l];
 37         tree[rt]=col[rt]=0;
 38         return;
 39     }
 40 
 41     int m=(l+r)>>1;
 42     build(lson);
 43     build(rson);
 44     pushup(rt);
 45 }
 46 
 47 void update(int L,int R,int temp,int l,int r,int rt)
 48 {
 49     if(temp==1){
 50         if(l==r){
 51             cnt[rt]=b[l];
 52             tree[rt]+=1;
 53             return ;
 54         }
 55 
 56         pushdown(rt);
 57         int m=(l+r)>>1;
 58         if (L<=m) update(L,R,cnt[rt<<1]==1,lson);
 59         if (R> m) update(L,R,cnt[rt<<1|1]==1,rson);
 60     }
 61     else{
 62         if(L<=l&&r<=R){
 63             cnt[rt]-=1;
 64             col[rt]+=1;
 65             return ;
 66         }
 67 
 68         pushdown(rt);
 69         int m=(l+r)>>1;
 70         if (L<=m) update(L,R,0,lson);
 71         if (R> m) update(L,R,0,rson);
 72     }
 73     pushup(rt);
 74 }
 75 
 76 int query(int L,int R,int l,int r,int rt)
 77 {
 78     if(L<=l&&r<=R){
 79         return tree[rt];
 80     }
 81 
 82     pushdown(rt);
 83     int m=(l+r)>>1;
 84     int ret=0;
 85     if(L<=m) ret+=query(L,R,lson);
 86     if(R> m) ret+=query(L,R,rson);
 87     return ret;
 88 }
 89 
 90 int main()
 91 {
 92     while(~scanf("%d%d",&n,&m)){
 93         memset(cnt,inf,sizeof(cnt));
 94         memset(tree,0,sizeof(tree));
 95         memset(col,0,sizeof(col));
 96         for(int i=1;i<=n;i++)
 97             scanf("%d",&b[i]);
 98         build(1,n,1);
 99         char s[10];int l,r;
100         for(int i=0;i<m;i++){
101             scanf("%s%d%d",s,&l,&r);
102             if(s[0]=='a'){
103                 update(l,r,cnt[1]==1,1,n,1);
104             }
105             else{
106                 printf("%d
",query(l,r,1,n,1));
107             }
108         }
109     }
110     return 0;
111 }