[NOI2005]维修数列

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<queue>
  4 using namespace std;
  5 
  6 const int INF=1e9;
  7 const int MAXN=1000005;
  8 
  9 int n,m,rt,cnt;
 10 int a[MAXN],id[MAXN],father[MAXN],tree[MAXN][2];
 11 int sum[MAXN],size[MAXN],val[MAXN],mx[MAXN],lx[MAXN],rx[MAXN];
 12 bool tag[MAXN],rev[MAXN];
 13 queue<int> q;
 14 
 15 void update(int x)
 16 {
 17     int l=tree[x][0],r=tree[x][1];
 18     sum[x]=sum[l]+sum[r]+val[x];
 19     size[x]=size[l]+size[r]+1;
 20     mx[x]=max(mx[l],mx[r]);
 21     mx[x]=max(mx[x],rx[l]+val[x]+lx[r]);
 22     lx[x]=max(lx[l],sum[l]+val[x]+lx[r]);
 23     rx[x]=max(rx[r],sum[r]+val[x]+rx[l]);
 24 }
 25 
 26 void pushdown(int x)
 27 {
 28     int l=tree[x][0],r=tree[x][1];
 29     if(tag[x])
 30     {
 31         rev[x]=tag[x]=0;
 32         if(l){tag[l]=1;val[l]=val[x];sum[l]=val[x]*size[l];}
 33         if(r){tag[r]=1;val[r]=val[x];sum[r]=val[x]*size[r];}
 34         if(val[x]>=0)
 35         {
 36             if(l) lx[l]=rx[l]=mx[l]=sum[l];
 37             if(r) lx[r]=rx[r]=mx[r]=sum[r];
 38         }else
 39         {
 40             if(l) lx[l]=rx[l]=0,mx[l]=val[x];
 41             if(r) lx[r]=rx[r]=0,mx[r]=val[x];
 42         }
 43     }
 44     if(rev[x])
 45     {
 46         rev[x]^=1;rev[l]^=1;rev[r]^=1;
 47         swap(lx[l],rx[l]);swap(lx[r],rx[r]);
 48         swap(tree[l][0],tree[l][1]);swap(tree[r][0],tree[r][1]);
 49     }
 50 }
 51 
 52 void rotate(int x,int &k)
 53 {
 54     int y=father[x],z=father[y],l=(tree[y][1]==x),r=l^1;
 55     if(y==k) k=x;
 56     else tree[z][tree[z][1]==y]=x;
 57     father[tree[x][r]]=y;father[y]=x;father[x]=z;
 58     tree[y][l]=tree[x][r];tree[x][r]=y;
 59     update(y);update(x);
 60 }
 61 
 62 void splay(int x,int &k)
 63 {
 64     while(x!=k)
 65     {
 66         int y=father[x],z=father[y];
 67         if(y!=k)
 68         {
 69             if((tree[y][0]==x)^(tree[z][0]==y)) rotate(x,k);
 70             else rotate(y,k);
 71         }
 72         rotate(x,k);
 73     }
 74 }
 75 
 76 int find(int x,int rk)
 77 {
 78     pushdown(x);
 79     int l=tree[x][0],r=tree[x][1];
 80     if(size[l]+1==rk) return x;
 81     if(size[l]>=rk) return find(l,rk);
 82     return find(r,rk-size[l]-1);
 83 }
 84 
 85 void rec(int x)
 86 {
 87     if(!x) return;
 88     int l=tree[x][0],r=tree[x][1];
 89     rec(l);rec(r);q.push(x);
 90     tag[x]=rev[x]=father[x]=tree[x][0]=tree[x][1]=0;
 91 }
 92 
 93 int split(int k,int tot)
 94 {
 95     int x=find(rt,k),y=find(rt,k+tot+1);
 96     splay(x,rt);splay(y,tree[x][1]);
 97     return tree[y][0];
 98 }
 99 
100 void query(int k,int tot)
101 {
102     int x=split(k,tot);
103     printf("%d\n",sum[x]);
104 }
105 
106 void modify(int k,int tot,int v)
107 {
108     int x=split(k,tot),y=father[x];
109     val[x]=v;tag[x]=1;sum[x]=size[x]*v;
110     if(v>=0) lx[x]=rx[x]=mx[x]=sum[x];
111     else lx[x]=rx[x]=0,mx[x]=v;
112     update(y);update(father[y]);
113 }
114 
115 void rever(int k,int tot)
116 {
117     int x=split(k,tot),y=father[x];
118     if(!tag[x])
119     {
120         rev[x]^=1;
121         swap(tree[x][0],tree[x][1]);
122         swap(lx[x],rx[x]);
123         update(y);update(father[y]);
124     }
125 }
126 
127 void erase(int k,int tot)
128 {
129     int x=split(k,tot),y=father[x];
130     rec(x);tree[y][0]=0;
131     update(y);update(father[y]);
132 }
133 
134 void build(int l,int r,int f)
135 {
136     if(l>r) return;
137     int mid=(l+r)>>1,now=id[mid],last=id[f];
138     if(l==r)
139     {
140         sum[now]=a[l];size[now]=1;
141         tag[now]=rev[now]=0;
142         if(a[l]>=0) lx[now]=rx[now]=mx[now]=a[l];
143         else lx[now]=rx[now]=0,mx[now]=a[l];
144     }else build(l,mid-1,mid),build(mid+1,r,mid);
145     val[now]=a[mid];father[now]=last;update(now);
146     tree[last][mid>=f]=now;
147 }
148 
149 void insert(int k,int tot)
150 {
151     for(int i=1;i<=tot;i++) scanf("%d",&a[i]);
152     for(int i=1;i<=tot;i++)
153         if(!q.empty()) id[i]=q.front(),q.pop();
154         else id[i]=++cnt;
155     build(1,tot,0);
156     int x=find(rt,k+1),y=find(rt,k+2),z=id[(1+tot)>>1];
157     splay(x,rt);splay(y,tree[x][1]);
158     father[z]=y;tree[y][0]=z;
159     update(y);update(x);
160 }
161 
162 int main()
163 {
164     scanf("%d%d",&n,&m);
165     mx[0]=a[1]=a[n+2]=-INF;
166     for(int i=1;i<=n;i++) scanf("%d",&a[i+1]);
167     for(int i=1;i<=n+2;i++) id[i]=i;
168     build(1,n+2,0);
169     rt=(n+3)>>1;cnt=n+2;
170     int k,tot,v;
171     char ch[10];
172     while(m--)
173     {
174         scanf("%s",ch);
175         if(ch[0]!=‘M‘||ch[2]!=‘X‘) scanf("%d%d",&k,&tot);
176         if(ch[0]==‘I‘)insert(k,tot);
177         if(ch[0]==‘D‘)erase(k,tot);
178         if(ch[0]==‘M‘)
179         {
180             if(ch[2]==‘X‘)printf("%d\n",mx[rt]);
181             else scanf("%d",&v),modify(k,tot,v);
182         }
183         if(ch[0]==‘R‘)rever(k,tot);
184         if(ch[0]==‘G‘)query(k,tot);
185     }
186     return 0;
187 }