洛谷 P2042 维护数列

http://blog.csdn.net/drazxlnddt/article/details/51051598

flip为true表示以当前节点为根的子树需要交换。set为true表示以当前节点为根的子树（包括自身）需要全部设为setv。

有个大坑：所谓和最大的子列最少有一个元素。有些操作可能对空的序列操作。

错误记录：所有注释掉的（多余的）和在之后加了//的语句（少的）

30和31行是为了更新子节点维护的各个值到正确的值（其他情况在split和merge中都是已经完成了更新，但如果字节点有setv的话没有）

附：一般的线段树维护时候，lazytag都是表示当前节点已经完成某操作，其所有子节点需要进行此操作。

也就是说，按照正确方法访问到某节点（root，或是split或merge出的节点，或是父节点访问子节点等），那么其权值一定已经是对的了，不用额外的upd()。但是这里set的tag定义为当前节点未完成此操作，要对当前节点及所有子节点完成。flip的操作，对于自身节点是没有影响的，因此flip的tag无所谓。因此需要要30和31行。原因嘛。。不知道。

上面都是假的！！！记住了只要pushdown()会改变upd()用到的参数，都必须要加上这两行，即使没有，为了防止漏看什么的也可以加上

注意53-55

可喜可贺，成功用自己A不掉的程序拍爆了A掉的程序（就是以下程序）

5 3
7 -1 -4 2 10
DELETE 1 4
MAKE-SAME 1 1 8
MAX-SUM

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<ctime>
  4 using namespace std;
  5 template<typename T>
  6 class MyVec
  7 {
  8 private:
  9     static const int M_SIZE=500001;
 10     int rand1()
 11     {
 12         static int x=471;
 13         return x=(48271LL*x+1)%2147483647;
 14     }
 15 public:
 16     static const T zero=T();
 17     struct Node
 18     {
 19         Node(){}
 20         Node* ch[2];
 21         int r;
 22         bool flip,set;
 23         T v;
 24         T setv;
 25         int size;
 26         T sum;
 27         T max_sum[3];//0=>left,1=>right,2=>this
 28         void upd()
 29         {
 30             if(ch[0])   ch[0]->pushdown();//
 31             if(ch[1])   ch[1]->pushdown();//
 32             size=1+(ch[0]?ch[0]->size:0)+(ch[1]?ch[1]->size:0);
 33             sum=v+(ch[0]?ch[0]->sum:zero)+(ch[1]?ch[1]->sum:zero);
 34             max_sum[0]=max(ch[0]?ch[0]->max_sum[0]:zero,v+(ch[0]?ch[0]->sum:zero)+(ch[1]?ch[1]->max_sum[0]:zero));
 35             max_sum[1]=max(ch[1]?ch[1]->max_sum[1]:zero,v+(ch[1]?ch[1]->sum:zero)+(ch[0]?ch[0]->max_sum[1]:zero));
 36            // max_sum[2]=max(max(ch[0]?ch[0]->max_sum[2]:zero,ch[1]?ch[1]->max_sum[2]:zero),v+(ch[0]?ch[0]->max_sum[1]:zero)+(ch[1]?ch[1]->max_sum[0]:zero));
 37            max_sum[2]=v+(ch[0]?ch[0]->max_sum[1]:zero)+(ch[1]?ch[1]->max_sum[0]:zero);
 38            if(ch[0])    max_sum[2]=max(max_sum[2],ch[0]->max_sum[2]);
 39            if(ch[1])    max_sum[2]=max(max_sum[2],ch[1]->max_sum[2]);
 40         }
 41         void pushdown()
 42         {
 43             if(flip)
 44             {
 45                 swap(ch[0],ch[1]);
 46                 swap(max_sum[0],max_sum[1]);//
 47                 if(ch[0])    (ch[0]->flip)^=1;
 48                 if(ch[1])    (ch[1]->flip)^=1;
 49                 flip=0;
 50             }
 51             if(set)
 52             {
 53                 v=setv;//
 54                 sum=v*size;//
 55                 //max_sum[0]=max_sum[1]=max_sum[2]=v>0 ? v*size : 0;//
 56                 max_sum[0]=max_sum[1]=v>0 ? sum : 0;
 57                 max_sum[2]=v>0 ? sum : v;
 58                 if(ch[0])
 59                 {
 60                     //ch[0]->v=setv;
 61                     ch[0]->setv=setv;
 62                     ch[0]->set=1;
 63                 }
 64                 if(ch[1])
 65                 {
 66                     //ch[1]->v=setv;
 67                     ch[1]->setv=setv;
 68                     ch[1]->set=1;
 69                 }
 70                 set=0;
 71             }
 72         }
 73     }nodes[M_SIZE];
 74     Node* root;
 75     Node* que[M_SIZE];
 76     int que_top;
 77     Node* getnode()
 78     {
 79         return que[que_top--];
 80     }
 81     void delnode(Node* x)
 82     {
 83         que[++que_top]=x;
 84     }
 85     Node* merge(Node* a,Node* b)
 86     {
 87         if(a==NULL)    return b;
 88         if(b==NULL)    return a;
 89         if(a->r < b->r)
 90         {
 91             a->pushdown();a->ch[1]=merge(a->ch[1],b);a->upd();
 92             return a;
 93         }
 94         else
 95         {
 96             b->pushdown();b->ch[0]=merge(a,b->ch[0]);b->upd();
 97             return b;
 98         }
 99     }
100     //注意upd()
101     typedef pair<Node*,Node*> P;
102     P split(Node* a,int n)
103     {
104         if(a==NULL)    return P(NULL,NULL);
105         P y;
106         a->pushdown();int s=a->ch[0] ? a->ch[0]->size : 0;//
107         if(s>=n)
108         {
109             y=split(a->ch[0],n);
110             a->ch[0]=y.second;a->upd();
111             y.second=a;
112         }
113         else
114         {
115             y=split(a->ch[1],n-s-1);
116             a->ch[1]=y.first;a->upd();
117             y.first=a;
118         }
119         return y;
120     }
121     Node* kth(Node* o,int k)
122     {
123         if(o==NULL||k<=0||k > o->size)    return NULL;
124         P y=split(root,k-1);
125         P y2=split(y.second,1);
126         root=merge(merge(y.first,y2.first),y2.second);
127         return y2.first;
128     }
129     void erase(Node* &o,int k)
130     {
131         if(o==NULL||k<=0||k > o->size)    return;
132         P y=split(root,k-1);
133         P y2=split(y.second,1);
134         delnode(y2.first);
135         root=merge(y.first,y2.second);
136     }
137     void deltree(Node* o)
138     {
139         if(o->ch[0])    deltree(o->ch[0]);
140         if(o->ch[1])    deltree(o->ch[1]);
141         delnode(o);
142     }
143     T find_max_sum()
144     {
145         return root?root->max_sum[2]:zero;
146     }
147 public:
148     //在第k个之前插入
149     void insert(int k,const T& x)
150     {
151         Node* t=getnode();
152         t->ch[0]=t->ch[1]=NULL;t->r=rand1();t->v=x;t->flip=0;t->set=0;t->setv=zero;t->upd();
153         P y=split(root,k-1);
154         root=merge(merge(y.first,t),y.second);
155     }
156     void insert(int k,Node* x)
157     {
158         P y=split(root,k-1);
159         root=merge(merge(y.first,x),y.second);
160     }
161     MyVec()
162     {
163         que_top=M_SIZE-1;
164         for(int i=0;i<M_SIZE;i++)    que[i]=nodes+i;
165         root=NULL;
166     }
167     void push_back(const T& x)
168     {
169         insert(size()+1,x);
170     }
171     void pop_back()
172     {
173         erase(root,root->size);
174     }
175     void push_front(const T& x)
176     {
177         insert(1,x);
178     }
179     void pop_front()
180     {
181         erase(root,1);
182     }
183     Node* find_by_order(int k)
184     {
185         return kth(root,k);
186     }
187     T& operator[](int k)
188     {
189         return kth(root,k)->v;
190     }
191     void erase(int k)
192     {
193         erase(root,k);
194     }
195     //第k个开始删连续p个
196     void erase(int k,int p)
197     {
198         P y=split(root,k-1);
199         P y2=split(y.second,p);
200         root=merge(y.first,y2.second);
201         deltree(y2.first);
202     }
203     int size()
204     {
205         return root ? root->size : 0;
206     }
207     //翻转[l,r]
208     void reverse(int l,int r)
209     {
210         if(l>r) return;//
211         P y=split(root,l-1);
212         P y2=split(y.second,r-l+1);
213         //y2.first->pushdown();//
214         y2.first->flip^=1;
215         //y2.first->upd();
216         root=merge(merge(y.first,y2.first),y2.second);
217     }
218     Node* build(T *l,T *r)
219     {
220         if(l>r) return NULL;
221         if(l==r)
222         {
223             Node* t=getnode();
224             t->ch[0]=t->ch[1]=NULL;t->r=rand1();t->v=*l;t->flip=0;t->set=0;t->setv=zero;t->upd();
225             return t;
226         }
227         else
228         {
229             T* mid=l+(r-l)/2;
230             return merge(build(l,mid),build(mid+1,r));
231         }
232     }
233     T sum(int l,int r)
234     {
235         if(l>r) return zero;//
236         P y=split(root,l-1);
237         P y2=split(y.second,r-l+1);
238         //y2.first->upd();//
239         T ans=y2.first->sum;
240         root=merge(merge(y.first,y2.first),y2.second);
241         return ans;
242     }
243     void set(int l,int r,const T& x)
244     {
245         if(l>r) return;//
246         P y=split(root,l-1);
247         P y2=split(y.second,r-l+1);
248         //y2.first->pushdown();
249         y2.first->set=1;
250         y2.first->setv=x;
251         //y2.first->v=x;
252         //y2.first->upd();
253         root=merge(merge(y.first,y2.first),y2.second);
254     }
255 };
256 MyVec<int> x;
257 int n,m,l,r;
258 int a[4001000];
259 char ope[300];
260 int main()
261 {
262     //freopen("testdata.in","r",stdin);
263     //freopen("testdata.out","w",stdout);
264     int i,posi,tot,c;
265      MyVec<int>::Node* t;
266     scanf("%d%d",&n,&m);
267     for(i=1;i<=n;i++)
268         scanf("%d",&a[i]);
269     x.root=x.build(a+1,a+n);
270     while(m--)
271     {
272         scanf("%s",ope);
273         if(ope[2]=='S')
274         {
275             scanf("%d%d",&posi,&tot);
276             for(i=1;i<=tot;i++) scanf("%d",&a[i]);
277             t=x.build(a+1,a+tot);
278             x.insert(posi+1,t);
279         }
280         else if(ope[2]=='L')
281         {
282             scanf("%d%d",&posi,&tot);
283             x.erase(posi,tot);
284         }
285         else if(ope[2]=='K')
286         {
287             scanf("%d%d%d",&posi,&tot,&c);
288             x.set(posi,posi+tot-1,c);
289         }
290         else if(ope[2]=='V')
291         {
292             scanf("%d%d",&posi,&tot);
293             x.reverse(posi,posi+tot-1);
294         }
295         else if(ope[2]=='T')
296         {
297             scanf("%d%d",&posi,&tot);
298             printf("%d
",x.sum(posi,posi+tot-1));
299         }
300         else if(ope[2]=='X')
301         {
302             printf("%d
",x.find_max_sum());
303         }
304     //printf("%s %d %d %d
",ope,posi,m,a[1]);
305       //for(i=1;i<=x.size();i++)    printf("%d ",x[i]);puts("");
306     }
307     return 0;
308 }

  1 #pragma GCC optimize(2)
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<ctime>
  5 using namespace std;
  6 template<typename T>
  7 class MyVec
  8 {
  9 private:
 10     static const int M_SIZE=500001;
 11     int rand1()
 12     {
 13         static int x=471;
 14         return x=(48271LL*x+1)%2147483647;
 15     }
 16 public:
 17     static const T zero=T();
 18     struct Node
 19     {
 20         Node(){}
 21         Node* ch[2];
 22         int r;
 23         bool flip,set;
 24         T v;
 25         T setv;
 26         int size;
 27         T sum;
 28         T max_sum[3];
 29         void upd()
 30         {
 31             if(ch[0])   ch[0]->pushdown();
 32             if(ch[1])   ch[1]->pushdown();
 33             size=1+(ch[0]?ch[0]->size:0)+(ch[1]?ch[1]->size:0);
 34             sum=v+(ch[0]?ch[0]->sum:zero)+(ch[1]?ch[1]->sum:zero);
 35             max_sum[0]=max(ch[0]?ch[0]->max_sum[0]:zero,v+(ch[0]?ch[0]->sum:zero)+(ch[1]?ch[1]->max_sum[0]:zero));
 36             max_sum[1]=max(ch[1]?ch[1]->max_sum[1]:zero,v+(ch[1]?ch[1]->sum:zero)+(ch[0]?ch[0]->max_sum[1]:zero));
 37            max_sum[2]=v+(ch[0]?ch[0]->max_sum[1]:zero)+(ch[1]?ch[1]->max_sum[0]:zero);
 38            if(ch[0])    max_sum[2]=max(max_sum[2],ch[0]->max_sum[2]);
 39            if(ch[1])    max_sum[2]=max(max_sum[2],ch[1]->max_sum[2]);
 40         }
 41         void pushdown()
 42         {
 43             if(flip)
 44             {
 45                 swap(ch[0],ch[1]);
 46                 swap(max_sum[0],max_sum[1]);
 47                 if(ch[0])    (ch[0]->flip)^=1;
 48                 if(ch[1])    (ch[1]->flip)^=1;
 49                 flip=0;
 50             }
 51             if(set)
 52             {
 53                 v=setv;
 54                 sum=v*size;
 55                 max_sum[0]=max_sum[1]=v>0 ? sum : 0;
 56                 max_sum[2]=v>0 ? sum : v;
 57                 if(ch[0])
 58                 {
 59                     ch[0]->setv=setv;
 60                     ch[0]->set=1;
 61                 }
 62                 if(ch[1])
 63                 {
 64                     ch[1]->setv=setv;
 65                     ch[1]->set=1;
 66                 }
 67                 set=0;
 68             }
 69         }
 70     }nodes[M_SIZE];
 71     Node* root;
 72     Node* que[M_SIZE];
 73     int que_top;
 74     Node* getnode()
 75     {
 76         return que[que_top--];
 77     }
 78     void delnode(Node* x)
 79     {
 80         que[++que_top]=x;
 81     }
 82     Node* merge(Node* a,Node* b)
 83     {
 84         if(a==NULL)    return b;
 85         if(b==NULL)    return a;
 86         if(a->r < b->r)
 87         {
 88             a->pushdown();a->ch[1]=merge(a->ch[1],b);a->upd();
 89             return a;
 90         }
 91         else
 92         {
 93             b->pushdown();b->ch[0]=merge(a,b->ch[0]);b->upd();
 94             return b;
 95         }
 96     }
 97     typedef pair<Node*,Node*> P;
 98     P split(Node* a,int n)
 99     {
100         if(a==NULL)    return P(NULL,NULL);
101         P y;
102         a->pushdown();int s=a->ch[0] ? a->ch[0]->size : 0;//
103         if(s>=n)
104         {
105             y=split(a->ch[0],n);
106             a->ch[0]=y.second;a->upd();
107             y.second=a;
108         }
109         else
110         {
111             y=split(a->ch[1],n-s-1);
112             a->ch[1]=y.first;a->upd();
113             y.first=a;
114         }
115         return y;
116     }
117     Node* kth(Node* o,int k)
118     {
119         if(o==NULL||k<=0||k > o->size)    return NULL;
120         P y=split(root,k-1);
121         P y2=split(y.second,1);
122         root=merge(merge(y.first,y2.first),y2.second);
123         return y2.first;
124     }
125     void erase(Node* &o,int k)
126     {
127         if(o==NULL||k<=0||k > o->size)    return;
128         P y=split(root,k-1);
129         P y2=split(y.second,1);
130         delnode(y2.first);
131         root=merge(y.first,y2.second);
132     }
133     void deltree(Node* o)
134     {
135         if(o->ch[0])    deltree(o->ch[0]);
136         if(o->ch[1])    deltree(o->ch[1]);
137         delnode(o);
138     }
139     T find_max_sum()
140     {
141         return root?root->max_sum[2]:zero;
142     }
143 public:
144     void insert(int k,const T& x)
145     {
146         Node* t=getnode();t->ch[0]=t->ch[1]=NULL;t->r=rand1();t->v=x;t->flip=0;t->set=0;t->setv=zero;t->upd();
147         P y=split(root,k-1);
148         root=merge(merge(y.first,t),y.second);
149     }
150     void insert(int k,Node* x)
151     {
152         P y=split(root,k-1);
153         root=merge(merge(y.first,x),y.second);
154     }
155     MyVec()
156     {
157         que_top=M_SIZE-1;
158         for(int i=0;i<M_SIZE;i++)    que[i]=nodes+i;
159         root=NULL;
160     }
161     void erase(int k,int p)
162     {
163         P y=split(root,k-1);
164         P y2=split(y.second,p);
165         root=merge(y.first,y2.second);
166         deltree(y2.first);
167     }
168     void reverse(int l,int r)
169     {
170         if(l>r) return;
171         P y=split(root,l-1);
172         P y2=split(y.second,r-l+1);
173         y2.first->flip^=1;
174         root=merge(merge(y.first,y2.first),y2.second);
175     }
176     Node* build(T *l,T *r)
177     {
178         if(l>r) return NULL;
179         if(l==r)
180         {
181             Node* t=getnode();t->ch[0]=t->ch[1]=NULL;t->r=rand1();t->v=*l;t->flip=0;t->set=0;t->setv=zero;t->upd();
182             return t;
183         }
184         else
185         {
186             T* mid=l+(r-l)/2;
187             return merge(build(l,mid),build(mid+1,r));
188         }
189     }
190     T sum(int l,int r)
191     {
192         if(l>r) return zero;
193         P y=split(root,l-1);
194         P y2=split(y.second,r-l+1);
195         T ans=y2.first->sum;
196         root=merge(merge(y.first,y2.first),y2.second);
197         return ans;
198     }
199     void set(int l,int r,const T& x)
200     {
201         if(l>r) return;
202         P y=split(root,l-1);
203         P y2=split(y.second,r-l+1);
204         y2.first->set=1;
205         y2.first->setv=x;
206         root=merge(merge(y.first,y2.first),y2.second);
207     }
208 };
209 MyVec<int> x;
210 int n,m,l,r;
211 int a[4001000];
212 char ope[300];
213 int main()
214 {
215     int i,posi,tot,c;
216     MyVec<int>::Node* t;
217     scanf("%d%d",&n,&m);
218     for(i=1;i<=n;i++)scanf("%d",&a[i]);
219     x.root=x.build(a+1,a+n);
220     while(m--)
221     {
222         scanf("%s",ope);
223         if(ope[2]=='S') {scanf("%d%d",&posi,&tot);for(i=1;i<=tot;i++) scanf("%d",&a[i]);t=x.build(a+1,a+tot);x.insert(posi+1,t);}
224         else if(ope[2]=='L'){scanf("%d%d",&posi,&tot);x.erase(posi,tot);}
225         else if(ope[2]=='K'){scanf("%d%d%d",&posi,&tot,&c);x.set(posi,posi+tot-1,c);}
226         else if(ope[2]=='V'){scanf("%d%d",&posi,&tot);x.reverse(posi,posi+tot-1);}
227         else if(ope[2]=='T'){scanf("%d%d",&posi,&tot);printf("%d
",x.sum(posi,posi+tot-1));}
228         else if(ope[2]=='X'){printf("%d
",x.find_max_sum());}
229     }
230     return 0;
231 }

重写了

  1 #pragma GCC optimize(3)
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<vector>
  6 #include<queue>
  7 using namespace std;
  8 #define fi first
  9 #define se second
 10 #define mp make_pair
 11 #define pb push_back
 12 typedef long long ll;
 13 typedef unsigned long long ull;
 14 typedef pair<int,int> pii;
 15 namespace S
 16 {
 17 const int N=500100;
 18 struct I
 19 {
 20     bool ok;
 21     int l,r,a;
 22     int sz,sum;
 23 }emp;
 24 I operator+(const I &a,const I &b)
 25 {
 26     if(!a.ok)    return b;
 27     if(!b.ok)    return a;
 28     I c;c.ok=1;
 29     c.sz=a.sz+b.sz;
 30     c.sum=a.sum+b.sum;
 31     //c.maxn=max(a.maxn,b.maxn);
 32     c.l=max(a.l,a.sum+b.l);
 33     c.r=max(b.r,b.sum+a.r);
 34     c.a=max(max(a.a,b.a),max(max(c.l,c.r),a.r+b.l));
 35     return c;
 36 }
 37 struct Node
 38 {
 39     Node *ch[2];
 40     I all,self;int d,r;
 41     bool flip,set;int setv;
 42 }nds[N];
 43 I genself(Node *a)
 44 {
 45     I ans;ans.ok=1;
 46     ans.l=ans.r=ans.a=a->d;
 47     ans.sz=1;ans.sum=/*ans.maxn=*/a->d;
 48     return ans;
 49 }
 50 I genmore(const I &a,int b)
 51 {
 52     I ans=a;
 53     if(a.sum>=0)
 54     {
 55         ans.a=ans.a*b;
 56         ans.l=ans.l*b;
 57         ans.r=ans.r*b;
 58     }
 59     ans.sz*=b;ans.sum*=b;
 60     return ans;
 61 }
 62 const I &gall(Node *a)    {return a?a->all:emp;}
 63 void doset(Node *a,int b)
 64 {
 65     if(!a)    return;
 66     a->d=b;a->self=genself(a);
 67     a->all=genmore(a->self,a->all.sz);
 68     a->set=1;a->setv=b;
 69 }
 70 void doflip(Node *a)
 71 {
 72     if(!a)    return;
 73     swap(a->ch[0],a->ch[1]);
 74     swap(a->all.l,a->all.r);
 75     a->flip^=1;
 76 }
 77 void pd(Node *a)
 78 {//if(!a)    return;
 79     if(a->flip)
 80     {
 81         doflip(a->ch[0]);
 82         doflip(a->ch[1]);
 83         a->flip=0;
 84     }
 85     if(a->set)
 86     {
 87         doset(a->ch[0],a->setv);
 88         doset(a->ch[1],a->setv);
 89         a->set=0;
 90     }
 91 }
 92 void upd(Node *a)
 93 {//pd(a->ch[0]);pd(a->ch[1]);
 94     a->self=genself(a);
 95     a->all=gall(a->ch[0])+a->self+gall(a->ch[1]);
 96 }
 97 queue<Node*> q;
 98 void init()
 99 {
100     for(int i=0;i<N;i++)    q.push(nds+i);
101 }
102 int rand1()
103 {
104     static int x=233;
105     return x=(48271LL*x+1)%2147483647;
106 }
107 Node *getnode()
108 {
109     Node *t=q.front();q.pop();
110     t->ch[0]=t->ch[1]=0;t->d=0;t->r=rand1();
111     t->flip=t->set=0;t->setv=0;//t->all=t->rall=t->self=emp;
112     return t;
113 }
114 void delnode(Node *a)    {q.push(a);}
115 void deltree(Node *a)
116 {
117     if(!a)    return;
118     deltree(a->ch[0]);deltree(a->ch[1]);
119     delnode(a);
120 }
121 Node *merge(Node *a,Node *b)
122 {
123     if(!a)    return b;
124     if(!b)    return a;
125     if(a->r<b->r)
126     {
127         pd(a);a->ch[1]=merge(a->ch[1],b);upd(a);
128         return a;
129     }
130     else
131     {
132         pd(b);b->ch[0]=merge(a,b->ch[0]);upd(b);
133         return b;
134     }
135 }
136 typedef pair<Node*,Node*> pnn;
137 pnn split(Node *o,int k)
138 {
139     if(!o)    return pnn(0,0);
140     if(!k)    return pnn(0,o);
141     pd(o);int ls=gall(o->ch[0]).sz;pnn y;
142     if(k<=ls)
143     {
144         y=split(o->ch[0],k);
145         o->ch[0]=y.se;upd(o);
146         y.se=o;
147     }
148     else
149     {
150         y=split(o->ch[1],k-ls-1);
151         o->ch[1]=y.fi;upd(o);
152         y.fi=o;
153     }
154     return y;
155 }
156 Node *build(int *l,int *r)
157 {
158     if(l==r)
159     {
160         Node *t=getnode();t->d=*l;upd(t);
161         return t;
162     }
163     int *mid=l+((r-l)>>1);
164     return merge(build(l,mid),build(mid+1,r));
165 }
166 }
167 using S::Node;
168 using S::pnn;
169 using S::merge;
170 using S::split;
171 using S::build;
172 Node *rt;
173 int n,m,a[500100];
174 char tmp[10];
175 int main()
176 {
177     S::init();
178     int i,j,p,tot,x,ans;Node *t1;pnn ta,tb;
179     scanf("%d%d",&n,&m);
180     for(i=1;i<=n;i++)    scanf("%d",&a[i]);
181     rt=build(a+1,a+n);
182     for(i=1;i<=m;i++)
183     {
184         scanf("%s",tmp);
185         if(tmp[0]=='I')
186         {
187             scanf("%d%d",&p,&tot);
188             if(tot==0)    continue;
189             for(j=1;j<=tot;j++)    scanf("%d",&a[j]);
190             t1=build(a+1,a+tot);
191             ta=split(rt,p);
192             rt=merge(merge(ta.fi,t1),ta.se);
193         }
194         else if(tmp[0]=='D')
195         {
196             scanf("%d%d",&p,&tot);
197             if(tot==0)    continue;
198             ta=split(rt,p-1);tb=split(ta.se,tot);
199             S::deltree(tb.fi);
200             rt=merge(ta.fi,tb.se);
201         }
202         else if(tmp[0]=='M'&&tmp[2]=='K')
203         {
204             scanf("%d%d%d",&p,&tot,&x);
205             if(tot==0)    continue;
206             ta=split(rt,p-1);tb=split(ta.se,tot);
207             S::doset(tb.fi,x);
208             rt=merge(ta.fi,merge(tb.fi,tb.se));
209         }
210         else if(tmp[0]=='R')
211         {
212             scanf("%d%d",&p,&tot);
213             if(tot==0)    continue;
214             ta=split(rt,p-1);tb=split(ta.se,tot);
215             S::doflip(tb.fi);
216             rt=merge(ta.fi,merge(tb.fi,tb.se));
217         }
218         else if(tmp[0]=='G')
219         {
220             scanf("%d%d",&p,&tot);
221             if(tot==0)    {printf("0
");continue;}
222             ta=split(rt,p-1);tb=split(ta.se,tot);
223             ans=tb.fi->all.sum;
224             rt=merge(ta.fi,merge(tb.fi,tb.se));
225             printf("%d
",ans);
226         }
227         else
228         {
229             printf("%d
",rt->all.a);
230         }
231     }
232     return 0;
233 }

卡常后才能bzojA

  1 #pragma GCC optimize(3)
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<vector>
  6 #include<queue>
  7 using namespace std;
  8 #define fi first
  9 #define se second
 10 #define mp make_pair
 11 #define pb push_back
 12 typedef long long ll;
 13 typedef unsigned long long ull;
 14 typedef pair<int,int> pii;
 15 namespace S
 16 {
 17 const int N=500100;
 18 struct I
 19 {
 20     int l,r,a;
 21     int sum;
 22 };
 23 I operator+(const I &a,const I &b)
 24 {
 25     I c;
 26     c.sum=a.sum+b.sum;
 27     //c.maxn=max(a.maxn,b.maxn);
 28     c.l=max(a.l,a.sum+b.l);
 29     c.r=max(b.r,b.sum+a.r);
 30     c.a=max(max(a.a,b.a),max(max(c.l,c.r),a.r+b.l));
 31     return c;
 32 }
 33 struct Node
 34 {
 35     Node *ch[2];
 36     I all;int d,r,sz;
 37     bool flip,set;int setv;
 38 }nds[N];
 39 int gsz(Node *o)    {return o?o->sz:0;}
 40 void doset(Node *a,int b)
 41 {
 42     if(!a)    return;
 43     a->d=b;
 44     static I self;
 45     self.l=self.r=self.a=a->d;
 46     self.sum=/*self.maxn=*/a->d;
 47     int sz=a->sz;
 48     a->all=self;
 49     if(self.sum>=0)    a->all.a*=sz,a->all.l*=sz,a->all.r*=sz;
 50     a->all.sum*=sz;
 51     a->set=1;a->setv=b;
 52 }
 53 void doflip(Node *a)
 54 {
 55     if(!a)    return;
 56     swap(a->ch[0],a->ch[1]);
 57     swap(a->all.l,a->all.r);
 58     a->flip^=1;
 59 }
 60 void pd(Node *a)
 61 {//if(!a)    return;
 62     if(a->flip)
 63     {
 64         doflip(a->ch[0]);
 65         doflip(a->ch[1]);
 66         a->flip=0;
 67     }
 68     if(a->set)
 69     {
 70         doset(a->ch[0],a->setv);
 71         doset(a->ch[1],a->setv);
 72         a->set=0;
 73     }
 74 }
 75 void upd(Node *a)
 76 {//pd(a->ch[0]);pd(a->ch[1]);
 77     a->sz=gsz(a->ch[0])+1+gsz(a->ch[1]);
 78     static I self;
 79     self.l=self.r=self.a=a->d;
 80     self.sum=/*self.maxn=*/a->d;
 81     if(a->ch[0]&&a->ch[1])
 82         a->all=a->ch[0]->all+self+a->ch[1]->all;
 83     else if(a->ch[0])
 84         a->all=a->ch[0]->all+self;
 85     else if(a->ch[1])
 86         a->all=self+a->ch[1]->all;
 87     else
 88         a->all=self;
 89 }
 90 queue<Node*> q;
 91 void init()
 92 {
 93     for(int i=0;i<N;i++)    q.push(nds+i);
 94 }
 95 int rand1()
 96 {
 97     static int x=233;
 98     return x=(48271LL*x+1)%2147483647;
 99 }
100 Node *getnode()
101 {
102     Node *t=q.front();q.pop();
103     t->ch[0]=t->ch[1]=0;t->d=0;t->r=rand1();
104     t->flip=t->set=0;t->setv=0;//t->all=t->rall=t->self=emp;
105     return t;
106 }
107 void delnode(Node *a)    {q.push(a);}
108 void deltree(Node *a)
109 {
110     if(!a)    return;
111     deltree(a->ch[0]);deltree(a->ch[1]);
112     delnode(a);
113 }
114 Node *merge(Node *a,Node *b)
115 {
116     if(!a)    return b;
117     if(!b)    return a;
118     if(a->r<b->r)
119     {
120         pd(a);a->ch[1]=merge(a->ch[1],b);upd(a);
121         return a;
122     }
123     else
124     {
125         pd(b);b->ch[0]=merge(a,b->ch[0]);upd(b);
126         return b;
127     }
128 }
129 typedef pair<Node*,Node*> pnn;
130 pnn split(Node *o,int k)
131 {
132     if(!o)    return pnn(0,0);
133     if(!k)    return pnn(0,o);
134     pd(o);int ls=gsz(o->ch[0]);pnn y;
135     if(k<=ls)
136     {
137         y=split(o->ch[0],k);
138         o->ch[0]=y.se;upd(o);
139         y.se=o;
140     }
141     else
142     {
143         y=split(o->ch[1],k-ls-1);
144         o->ch[1]=y.fi;upd(o);
145         y.fi=o;
146     }
147     return y;
148 }
149 Node *build(int *l,int *r)
150 {
151     if(l==r)
152     {
153         Node *t=getnode();t->d=*l;upd(t);
154         return t;
155     }
156     int *mid=l+((r-l)>>1);
157     return merge(build(l,mid),build(mid+1,r));
158 }
159 }
160 using S::Node;
161 using S::pnn;
162 using S::merge;
163 using S::split;
164 using S::build;
165 Node *rt;
166 int n,m,a[500100];
167 char tmp[10];
168 int main()
169 {
170     srand(27);S::init();
171     int i,j,p,tot,x,ans;Node *t1;pnn ta,tb;
172     scanf("%d%d",&n,&m);
173     for(i=1;i<=n;i++)    scanf("%d",&a[i]);
174     rt=build(a+1,a+n);
175     for(i=1;i<=m;i++)
176     {
177         scanf("%s",tmp);
178         if(tmp[0]=='I')
179         {
180             scanf("%d%d",&p,&tot);
181             if(tot==0)    continue;
182             for(j=1;j<=tot;j++)    scanf("%d",&a[j]);
183             t1=build(a+1,a+tot);
184             ta=split(rt,p);
185             rt=merge(merge(ta.fi,t1),ta.se);
186         }
187         else if(tmp[0]=='D')
188         {
189             scanf("%d%d",&p,&tot);
190             if(tot==0)    continue;
191             ta=split(rt,p-1);tb=split(ta.se,tot);
192             S::deltree(tb.fi);
193             rt=merge(ta.fi,tb.se);
194         }
195         else if(tmp[0]=='M'&&tmp[2]=='K')
196         {
197             scanf("%d%d%d",&p,&tot,&x);
198             if(tot==0)    continue;
199             ta=split(rt,p-1);tb=split(ta.se,tot);
200             S::doset(tb.fi,x);
201             rt=merge(ta.fi,merge(tb.fi,tb.se));
202         }
203         else if(tmp[0]=='R')
204         {
205             scanf("%d%d",&p,&tot);
206             if(tot==0)    continue;
207             ta=split(rt,p-1);tb=split(ta.se,tot);
208             S::doflip(tb.fi);
209             rt=merge(ta.fi,merge(tb.fi,tb.se));
210         }
211         else if(tmp[0]=='G')
212         {
213             scanf("%d%d",&p,&tot);
214             if(tot==0)    {printf("0
");continue;}
215             ta=split(rt,p-1);tb=split(ta.se,tot);
216             ans=tb.fi->all.sum;
217             rt=merge(ta.fi,merge(tb.fi,tb.se));
218             printf("%d
",ans);
219         }
220         else
221         {
222             printf("%d
",rt->all.a);
223         }
224     }
225     return 0;
226 }