NOI2005维修数列

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