激！GSS系列

 #include <cstdio>

 const int sizeOfNumber=;

 const int sizeOfSeg=;

 inline int max(int, int);

 inline int getint();

 inline void putint(int);

 struct node

 {

     int lmax, rmax, smax, ssum;

     inline node(int=);

 };

 inline node merge(node, node);

 struct seg

 {

     node data;

     seg * l, * r;

     inline void maintain();

 };

 seg memory[sizeOfSeg], * port=memory;

 inline seg * newseg();

 seg * build(int, int);

 node query(seg * , int, int, int, int);

 int n, m;

 int a[sizeOfNumber];

 seg * t;

 int main()

 {

     n=getint();

     for (int i=;i<=n;i++)

         a[i]=getint();

     t=build(, n);

     m=getint();

     for (int i=;i<=m;i++)

     {

         int x=getint(), y=getint();

         putint(query(t, , n, x, y).smax);

     }

     return ;

 }

 inline int max(int x, int y)

 {

     return x>y?x:y;

 }

 inline int getint()

 {

     register int num=;

     register char ch=, last;

     do last=ch, ch=getchar(); while (ch<'' || ch>'');

     do num=num*+ch-'', ch=getchar(); while (ch>='' && ch<='');

     if (last=='-') num=-num;

     return num;

 }

 inline void putint(int num)

 {

     char stack[];

     register int top=;

     if (num==) stack[top=]='';

     if (num<) putchar('-'), num=-num;

     for ( ;num;num/=) stack[++top]=num%+'';

     for ( ;top;top--) putchar(stack[top]);

     putchar('\n');

 }

 inline node::node(int x)

 {

     lmax=rmax=smax=ssum=x;

 }

 inline node merge(node a, node b)

 {

     node c;

     c.ssum=a.ssum+b.ssum;

     c.lmax=max(a.lmax, a.ssum+b.lmax);

     c.rmax=max(a.rmax+b.ssum, b.rmax);

     c.smax=max(a.smax, b.smax);

     c.smax=max(c.smax, a.rmax+b.lmax);

     return c;

 }

 inline seg * newseg()

 {

     seg * ret=port++;

     return ret;

 }

 inline void seg::maintain()

 {

     this->data=merge(this->l->data, this->r->data);

 }

 inline seg * build(int l, int r)

 {

     seg * t=newseg();

     int m=(l+r)>>;

     if (l==r)

         t->data=node(a[m]);

     else

     {

         t->l=build(l, m);

         t->r=build(m+, r);

         t->maintain();

     }

     return t;

 }

 node query(seg * t, int l, int r, int ql, int qr)

 {

     node ret;

     int m=(l+r)>>;

     if (l==ql && r==qr) ret=t->data;

     else

     {

         if (qr<=m) ret=query(t->l, l, m, ql, qr);

         else if (ql>m) ret=query(t->r, m+, r, ql, qr);

         else ret=merge(query(t->l, l, m, ql, m), query(t->r, m+, r, m+, qr));

     }

     return ret;

 }

GSS1

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 const int sizeOfNumber=;

 const int sizeOfQuestion=;

 const int sizeOfSeg=;

 inline int max(int, int);

 inline int getint();

 inline void putint(int);

 struct seg

 {

     int ssum, lmax;

     int flag, maxflag;

     seg * l, * r;

     inline void pushdown();

     inline void maintain();

 };

 seg memory[sizeOfSeg], * port=memory;

 inline seg * newseg();

 seg * build(int, int);

 void update(seg * , int, int, int, int, int);

 int query(seg * , int, int, int, int);

 int n, q;

 int a[sizeOfNumber], p[sizeOfNumber];

 int d[sizeOfQuestion], l[sizeOfQuestion], r[sizeOfQuestion];

 int ans[sizeOfQuestion];

 seg * t;

 inline bool cmpForQuestion(int, int);

 inline bool cmpForDiscrete(int, int);

 inline void prepare();

 int main()

 {

     n=getint();

     for (int i=;i<=n;i++)

         a[i]=getint();

     prepare();

     t=build(, n);

     q=getint();

     for (int i=;i<=q;i++)

         l[i]=getint(), r[i]=getint();

     for (int i=;i<=q;i++)

         d[i]=i;

     std::sort(d+, d+q+, cmpForQuestion);

     int j=;

     for (int i=;i<=n;i++)

     {

         update(t, , n, p[i]+, i, a[i]);

         for ( ;j<=q && r[d[j]]==i;j++)

             ans[d[j]]=query(t, , n, l[d[j]], r[d[j]]);

     }

     for (int i=;i<=q;i++)

         putint(ans[i]);

     return ;

 }

 inline int max(int x, int y)

 {

     return x>y?x:y;

 }

 inline int getint()

 {

     register int num=;

     register char ch=, last;

     do last=ch, ch=getchar(); while (ch<'' || ch>'');

     do num=num*+ch-'', ch=getchar(); while (ch>='' && ch<='');

     if (last=='-') num=-num;

     return num;

 }

 inline void putint(int num)

 {

     char stack[];

     register int top=;

     if (num==) stack[top=]='';

     if (num<) putchar('-'), num=-num;

     for ( ;num;num/=) stack[++top]=num%+'';

     for ( ;top;top--) putchar(stack[top]);

     putchar('\n');

 }

 inline void seg::pushdown()

 {

     this->l->maxflag=max(this->l->maxflag, this->l->flag+this->maxflag);

     this->r->maxflag=max(this->r->maxflag, this->r->flag+this->maxflag);

     this->l->flag+=this->flag;

     this->r->flag+=this->flag;

     this->l->lmax=max(this->l->lmax, this->l->ssum+this->maxflag);

     this->r->lmax=max(this->r->lmax, this->r->ssum+this->maxflag);

     this->l->ssum+=this->flag;

     this->r->ssum+=this->flag;

     this->flag=;

     this->maxflag=;

 }

 inline void seg::maintain()

 {

     this->ssum=max(this->l->ssum, this->r->ssum);

     this->lmax=max(this->l->lmax, this->r->lmax);

 }

 inline seg * newseg()

 {

     seg * ret=port++;

     return ret;

 }

 seg * build(int l, int r)

 {

     seg * t=newseg();

     int m=(l+r)>>;

     if (l==r) return t;

     t->l=build(l, m);

     t->r=build(m+, r);

     return t;

 }

 void update(seg * t, int l, int r, int ql, int qr, int v)

 {

     if (l==ql && r==qr)

     {

         t->ssum+=v;

         t->lmax=max(t->lmax, t->ssum);

         t->flag+=v;

         t->maxflag=max(t->maxflag, t->flag);

     }

     else

     {

         int m=(l+r)>>;

         t->pushdown();

         if (qr<=m) update(t->l, l, m, ql, qr, v);

         else if (ql>m) update(t->r, m+, r, ql, qr, v);

         else update(t->l, l, m, ql, m, v), update(t->r, m+, r, m+, qr, v);

         t->maintain();

     }

 }

 int query(seg * t, int l, int r, int ql, int qr)

 {

     int ret=;

     if (l==ql && r==qr)

         ret=t->lmax;

     else

     {

         int m=(l+r)>>;

         t->pushdown();

         if (qr<=m) ret=query(t->l, l, m, ql, qr);

         else if (ql>m) ret=query(t->r, m+, r, ql, qr);

         else ret=max(query(t->l, l, m, ql, m), query(t->r, m+, r, m+, qr));

         t->maintain();

     }

     return ret;

 }

 inline bool cmpForQuestion(int i, int j)

 {

     return r[i]<r[j];

 }

 inline bool cmpForDiscrete(int i, int j)

 {

     return a[i]<a[j];

 }

 inline void prepare()

 {

     static int d[sizeOfNumber], l[sizeOfNumber];

     int m, t;

     for (int i=;i<=n;i++)

         l[i]=i;

     std::sort(l+, l+n+, cmpForDiscrete);

     m=, t=a[l[m]];

     d[l[]]=;

     for (int i=;i<=n;i++)

     {

         if (a[l[i]]>t)

             ++m, t=a[l[i]];

         d[l[i]]=m;

     }

     memset(l, , sizeof(l));

     for (int i=;i<=n;i++)

     {

         p[i]=l[d[i]];

         l[d[i]]=i;

     }

 }

GSS2

 #include <cstdio>

 const int sizeOfNumber=;

 const int sizeOfSeg=;

 inline int max(int, int);

 inline int getint();

 inline void putint(int);

 struct node

 {

     int lmax, rmax, smax, ssum;

     inline node(int=);

 };

 inline node merge(node, node);

 struct seg

 {

     node data;

     seg * l, * r;

     inline void maintain();

 };

 seg memory[sizeOfSeg], * port=memory;

 inline seg * newseg();

 seg * build(int, int);

 void update(seg * , int, int, int);

 node query(seg * , int, int, int, int);

 int n, m;

 int a[sizeOfNumber];

 seg * t;

 int main()

 {

     n=getint();

     for (int i=;i<=n;i++)

         a[i]=getint();

     t=build(, n);

     m=getint();

     for (int i=;i<=m;i++)

     {

         int k=getint(), x=getint(), y=getint();

         if (k==)

             putint(query(t, , n, x, y).smax);

         else

         {

             a[x]=y;

             update(t, , n, x);

         }

     }

     return ;

 }

 inline int max(int x, int y)

 {

     return x>y?x:y;

 }

 inline int getint()

 {

     register int num=;

     register char ch=, last;

     do last=ch, ch=getchar(); while (ch<'' || ch>'');

     do num=num*+ch-'', ch=getchar(); while (ch>='' && ch<='');

     if (last=='-') num=-num;

     return num;

 }

 inline void putint(int num)

 {

     char stack[];

     register int top=;

     if (num==) stack[top=]='';

     if (num<) putchar('-'), num=-num;

     for ( ;num;num/=) stack[++top]=num%+'';

     for ( ;top;top--) putchar(stack[top]);

     putchar('\n');

 }

 inline node::node(int x)

 {

     lmax=rmax=smax=ssum=x;

 }

 inline node merge(node a, node b)

 {

     node c;

     c.ssum=a.ssum+b.ssum;

     c.lmax=max(a.lmax, a.ssum+b.lmax);

     c.rmax=max(a.rmax+b.ssum, b.rmax);

     c.smax=max(a.smax, b.smax);

     c.smax=max(c.smax, a.rmax+b.lmax);

     return c;

 }

 inline seg * newseg()

 {

     seg * ret=port++;

     return ret;

 }

 inline void seg::maintain()

 {

     this->data=merge(this->l->data, this->r->data);

 }

 inline seg * build(int l, int r)

 {

     seg * t=newseg();

     int m=(l+r)>>;

     if (l==r)

         t->data=node(a[m]);

     else

     {

         t->l=build(l, m);

         t->r=build(m+, r);

         t->maintain();

     }

     return t;

 }

 void update(seg * t, int l, int r, int k)

 {

     int m=(l+r)>>;

     if (l==r)

         t->data=node(a[m]);

     else

     {

         if (k<=m) update(t->l, l, m, k);

         else update(t->r, m+, r, k);

         t->maintain();

     }

 }

 node query(seg * t, int l, int r, int ql, int qr)

 {

     node ret;

     int m=(l+r)>>;

     if (l==ql && r==qr) ret=t->data;

     else

     {

         if (qr<=m) ret=query(t->l, l, m, ql, qr);

         else if (ql>m) ret=query(t->r, m+, r, ql, qr);

         else ret=merge(query(t->l, l, m, ql, m), query(t->r, m+, r, m+, qr));

     }

     return ret;

 }

GSS3

 #include <cstdio>

 #include <cmath>

 typedef long long LL;

 const int sizeOfNumber=;

 const int sizeOfSeg=;

 inline void swap(int & , int & );

 inline LL getint();

 inline void putint(LL);

 struct seg

 {

     LL sum;

     bool flag;

     seg * l, * r;

     inline void maintain();

 };

 seg memory[sizeOfSeg], * port=memory;

 inline seg * newseg();

 seg * build(int, int);

 void update(seg * , int, int, int, int);

 LL query(seg * , int, int, int, int);

 int n, m;

 LL a[sizeOfNumber];

 seg * t;

 int main()

 {

     int c=;

     while (scanf("%d", &n)!=EOF)

     {

         for (int i=;i<=n;i++)

             a[i]=getint();

         port=memory;

         t=build(, n);

         printf("Case #%d:\n", ++c);

         m=getint();

         for (int i=;i<=m;i++)

         {

             int k=getint(), x=getint(), y=getint();

             if (x>y) swap(x, y);

             if (k==) update(t, , n, x, y);

             else putint(query(t, , n, x, y));

         }

     }

     return ;

 }

 inline void swap(int & x, int & y)

 {

     int t=x; x=y; y=t;

 }

 inline LL getint()

 {

     register LL num=;

     register char ch;

     do ch=getchar(); while (ch<'' || ch>'');

     do num=num*+ch-'', ch=getchar(); while (ch>='' && ch<='');

     return num;

 }

 inline void putint(LL num)

 {

     char stack[];

     register int top=;

     if (num==) stack[top=]='';

     for ( ;num;num/=) stack[++top]=num%+'';

     for ( ;top;top--) putchar(stack[top]);

     putchar('\n');

 }

 inline void seg::maintain()

 {

     sum=l->sum+r->sum;

     flag=l->flag&r->flag;

 }

 inline seg * newseg()

 {

     return port++;

 }

 seg * build(int l, int r)

 {

     seg * t=newseg();

     int m=(l+r)>>;

     if (l==r)

     {

         t->sum=a[m];

         t->flag=t->sum<=;

     }

     else

     {

         t->l=build(l, m);

         t->r=build(m+, r);

         t->maintain();

     }

     return t;

 }

 void update(seg * t, int l, int r, int ql, int qr)

 {

     if (t->flag)

         return ;

     if (l==r && ql==qr)

     {

         t->sum=static_cast<int>(sqrt(t->sum));

         t->flag=t->sum<=;

         return ;

     }

     int m=(l+r)>>;

     if (qr<=m) update(t->l, l, m, ql, qr);

     else if (ql>m) update(t->r, m+, r, ql, qr);

     else update(t->l, l, m, ql, m), update(t->r, m+, r, m+, qr);

     t->maintain();

 }

 LL query(seg * t, int l, int r, int ql, int qr)

 {

     if (l==ql && r==qr)

         return t->sum;

     int m=(l+r)>>;

     if (qr<=m) return query(t->l, l, m, ql, qr);

     else if (ql>m) return query(t->r, m+, r, ql, qr);

     else return query(t->l, l, m, ql, m)+query(t->r, m+, r, m+, qr);

 }

GSS4

 #include <cstdio>

 const int sizeOfNumber=;

 const int sizeOfSeg=;

 const int inf=0x3F3F3F3F;

 inline int max(int, int);

 inline int getint();

 inline void putint(int);

 struct node

 {

     int lmax, rmax, smax, ssum;

     inline node(int=);

 };

 inline node merge(node, node);

 struct seg

 {

     node data;

     seg * l, * r;

     inline void maintain();

 };

 seg memory[sizeOfSeg], * port=memory;

 inline seg * newseg();

 seg * build(int, int);

 node query(seg * , int, int, int, int);

 int c, n, m;

 int a[sizeOfNumber];

 seg * t;

 int main()

 {

     int ans;

     for (c=getint();c;c--)

     {

         n=getint();

         for (int i=;i<=n;i++)

             a[i]=getint();

         port=memory;

         t=build(, n);

         m=getint();

         for (int i=;i<=m;i++)

         {

             int x1=getint(), y1=getint(), x2=getint(), y2=getint();

             if (y1<x2)

                 ans=query(t, , n, x1, y1).rmax+query(t, , n, x2, y2).lmax+query(t, , n, y1+, x2-).ssum;

             else

             {

                 node l=query(t, , n, x1, x2-), m=query(t, , n, x2, y1), r=query(t, , n, y1+, y2);

                 ans=max(merge(l, m).rmax+r.lmax, l.rmax+merge(m, r).lmax);

                 ans=max(ans, l.rmax+m.ssum+r.lmax);

                 ans=max(ans, m.smax);

             }

             putint(ans);

         }

     }

     return ;

 }

 inline int max(int x, int y)

 {

     return x>y?x:y;

 }

 inline int getint()

 {

     register int num=;

     register char ch=, last;

     do last=ch, ch=getchar(); while (ch<'' || ch>'');

     do num=num*+ch-'', ch=getchar(); while (ch>='' && ch<='');

     if (last=='-') num=-num;

     return num;

 }

 inline void putint(int num)

 {

     char stack[];

     register int top=;

     if (num==) stack[top=]='';

     if (num<) putchar('-'), num=-num;

     for ( ;num;num/=) stack[++top]=num%+'';

     for ( ;top;top--) putchar(stack[top]);

     putchar('\n');

 }

 inline node::node(int x)

 {

     lmax=rmax=smax=ssum=x;

 }

 inline node merge(node a, node b)

 {

     node c;

     c.ssum=a.ssum+b.ssum;

     c.lmax=max(a.lmax, a.ssum+b.lmax);

     c.rmax=max(a.rmax+b.ssum, b.rmax);

     c.smax=max(a.smax, b.smax);

     c.smax=max(c.smax, a.rmax+b.lmax);

     return c;

 }

 inline seg * newseg()

 {

     seg * ret=port++;

     return ret;

 }

 inline void seg::maintain()

 {

     this->data=merge(this->l->data, this->r->data);

 }

 inline seg * build(int l, int r)

 {

     seg * t=newseg();

     int m=(l+r)>>;

     if (l==r)

         t->data=node(a[m]);

     else

     {

         t->l=build(l, m);

         t->r=build(m+, r);

         t->maintain();

     }

     return t;

 }

 node query(seg * t, int l, int r, int ql, int qr)

 {

     node ret();

     int m=(l+r)>>;

     if (ql>qr) return ret;

     if (l==ql && r==qr) ret=t->data;

     else

     {

         if (qr<=m) ret=query(t->l, l, m, ql, qr);

         else if (ql>m) ret=query(t->r, m+, r, ql, qr);

         else ret=merge(query(t->l, l, m, ql, m), query(t->r, m+, r, m+, qr));

     }

     return ret;

 }

GSS5

 #include <cstdio>

 #include <cstdlib>

 const int sizeOfNumber=;

 const int sizeOfTreap=;

 const int inf=0x3F3F3F3F;

 inline int max(int, int);

 inline char getch();

 inline int getint();

 inline void putint(int);

 struct treap

 {

     int key, sum;

     int lmax, rmax, smax;

     int size, weight;

     treap * l, * r;

     inline treap();

     inline void maintain();

 };

 treap * null=new treap();

 treap memory[sizeOfTreap], * port=memory;

 inline treap * newtreap(int);

 void split(treap * , int, treap *& , treap *& );

 treap * merge(treap * ,  treap * );

 int N, Q;

 treap * t;

 int main()

 {

     treap * l, * m, * r;

     char c;

     int x, y;

     N=getint();

     t=null;

     for (int i=;i<=N;i++)

     {

         x=getint();

         t=merge(t, newtreap(x));

     }

     Q=getint();

     for (int i=;i<=Q;i++)

     {

         c=getch(); x=getint();

         if (c=='I')

         {

             y=getint();

             split(t, x-, l, r);

             m=newtreap(y);

             l=merge(l, m);

             t=merge(l, r);

         }

         else if (c=='D')

         {

             split(t, x-, l, r);

             split(r, , m, r);

             t=merge(l, r);

         }

         else if (c=='R')

         {

             y=getint();

             split(t, x-, l, r);

             split(r, , m, r);

             m=newtreap(y);

             l=merge(l, m);

             t=merge(l, r);

         }

         else

         {

             y=getint();

             split(t, x-, l, r);

             split(r, y-x+, m, r);

             putint(m->smax);

             l=merge(l, m);

             t=merge(l, r);

         }

     }

     return ;

 }

 inline int max(int x, int y)

 {

     return x>y?x:y;

 }

 inline char getch()

 {

     register char ch;

     do ch=getchar(); while (ch!='I' && ch!='D' && ch!='R' && ch!='Q');

     return ch;

 }

 inline int getint()

 {

     register int num=;

     register char ch=, last;

     do last=ch, ch=getchar(); while (ch<'' || ch>'');

     do num=num*+ch-'', ch=getchar(); while (ch>='' && ch<='');

     if (last=='-') num=-num;

     return num;

 }

 inline void putint(int num)

 {

     char stack[];

     register int top=;

     if (num==) stack[top=]='';

     if (num<) putchar('-'), num=-num;

     for ( ;num;num/=) stack[++top]=num%+'';

     for ( ;top;top--) putchar(stack[top]);

     putchar('\n');

 }

 inline treap::treap()

 {

     this->key=; this->sum=;

     this->lmax=-inf; this->rmax=-inf; this->smax=-inf;

     this->size=; this->weight=;

     this->l=this->r=this;

 }

 inline void treap::maintain()

 {

     this->sum=this->l->sum+this->key+this->r->sum;

     this->lmax=max(this->l->lmax, this->l->sum+this->key); this->lmax=max(this->lmax, this->l->sum+this->key+this->r->lmax);

     this->rmax=max(this->r->rmax, this->key+this->r->sum); this->rmax=max(this->rmax, this->l->rmax+this->key+this->r->sum);

     this->smax=max(this->l->smax, this->r->smax); this->smax=max(this->smax, this->l->rmax+this->key+this->r->lmax);

     this->smax=max(this->smax, this->l->rmax+this->key); this->smax=max(this->smax, this->key+this->r->lmax);

     this->smax=max(this->smax, this->key);

     this->size=this->l->size++this->r->size;

 }

 inline treap * newtreap(int _key)

 {

     treap * ret=port++;

     ret->key=_key; ret->sum=_key;

     ret->lmax=ret->rmax=ret->smax=_key;

     ret->size=; ret->weight=rand();

     ret->l=ret->r=null;

     return ret;

 }

 void split(treap * t, int k, treap *& l, treap *& r)

 {

     if (t==null)

     {

         l=r=null;

         return ;

     }

     if (t->l->size+<=k)

     {

         l=t;

         split(t->r, k-t->l->size-, t->r, r);

         l->maintain();

     }

     else

     {

         r=t;

         split(t->l, k, l, t->l);

         r->maintain();

     }

 }

 treap * merge(treap * l, treap * r)

 {

     if (l==null) return r;

     if (r==null) return l;

     if (l->weight>r->weight)

     {

         l->r=merge(l->r, r);

         l->maintain();

         return l;

     }

     else

     {

         r->l=merge(l, r->l);

         r->maintain();

         return r;

     }

 }

GSS6

 #include <cstdio>

 #include <cstring>

 const int sizeOfNumber=;

 const int sizeOfEdge=;

 const int sizeOfSeg=;

 const int inf=0x7FFFFFFF;

 inline int lg(int);

 inline void swap(int & , int & );

 inline int max(int, int);

 inline int getint();

 inline void putint(int);

 struct edge

 {

     int point;

     edge * next;

 };

 edge memoryOfEdge[sizeOfEdge], * portOfEdge=memoryOfEdge;

 inline edge * newedge(int, edge * );

 inline void link(int, int);

 struct node

 {

     int lmax, rmax, smax, ssum;

     inline node(int=);

 };

 inline node merge(node, node);

 struct seg

 {

     node data;

     int flag, size;

     seg * l, * r;

     inline void pushdown();

     inline void maintain();

 };

 seg memoryOfSeg[sizeOfSeg], * portOfSeg=memoryOfSeg;

 inline seg * newseg();

 seg * build(int, int);

 void update(seg * , int, int, int, int, int);

 node query(seg * , int, int, int, int);

 int n, q;

 int x[sizeOfNumber];

 edge * e[sizeOfNumber];

 int a[][sizeOfNumber];

 int s[sizeOfNumber], d[sizeOfNumber], f[sizeOfNumber];

 int tmp, idx[sizeOfNumber], r_idx[sizeOfNumber], son[sizeOfNumber], top[sizeOfNumber];

 seg * t;

 inline void dfsTree();

 inline void dfsChain();

 inline int lca(int, int);

 inline int anc(int, int);

 inline void update(int, int, int);

 inline node query(int, int);

 int main()

 {

     n=getint();

     for (int i=;i<=n;i++)

         x[i]=getint();

     for (int i=;i<n;i++)

     {

         int u=getint(), v=getint();

         link(u, v);

     }

     dfsTree();

     dfsChain();

     t=build(, n);

     q=getint();

     for (int i=;i<=q;i++)

     {

         int k=getint(), x=getint(), y=getint();

         if (k==)

         {

             if (d[x]>d[y])

                 swap(x, y);

             if (x==y)

             {

                 putint(query(t, , n, idx[x], idx[x]).smax);

                 continue;

             }

             int a=lca(x, y), z=anc(y, d[y]-d[a]-);

             node l=query(y, z), r=query(x, a);

             swap(l.lmax, l.rmax);

             putint(merge(l, r).smax);

         }

         else

         {

             int z=getint();

             update(x, y, z);

         }

     }

     return ;

 }

 inline int lg(int x)

 {

     return x>?-__builtin_clz(x):;

 }

 inline void swap(int & x, int & y)

 {

     int z=x; x=y; y=z;

 }

 inline int max(int x, int y)

 {

     return x>y?x:y;

 }

 inline int getint()

 {

     register int num=;

     register char ch=, last;

     do last=ch, ch=getchar(); while (ch<'' || ch>'');

     do num=num*+ch-'', ch=getchar(); while (ch>='' && ch<='');

     if (last=='-') num=-num;

     return num;

 }

 inline void putint(int num)

 {

     char stack[];

     register int top=;

     if (num==) stack[top=]='';

     if (num<) putchar('-'), num=-num;

     for ( ;num;num/=) stack[++top]=num%+'';

     for ( ;top;top--) putchar(stack[top]);

     putchar('\n');

 }

 inline edge * newedge(int point, edge * next)

 {

     edge * ret=portOfEdge++;

     ret->point=point; ret->next=next;

     return ret;

 }

 inline void link(int u, int v)

 {

     e[u]=newedge(v, e[u]);

     e[v]=newedge(u, e[v]);

 }

 inline node::node(int x)

 {

     ssum=x;

     lmax=rmax=smax=max(x, );

 }

 inline node merge(node a, node b)

 {

     node c;

     c.ssum=a.ssum+b.ssum;

     c.lmax=max(a.lmax, a.ssum+b.lmax);

     c.rmax=max(a.rmax+b.ssum, b.rmax);

     c.smax=max(a.smax, b.smax);

     c.smax=max(c.smax, a.rmax+b.lmax);

     return c;

 }

 inline void seg::pushdown()

 {

     if (this->flag<inf)

     {

         this->l->data.ssum=this->l->size*this->flag;

         this->r->data.ssum=this->r->size*this->flag;

         this->l->data.lmax=this->l->data.rmax=this->l->data.smax=max(this->l->data.ssum, );

         this->r->data.lmax=this->r->data.rmax=this->r->data.smax=max(this->r->data.ssum, );

         this->l->flag=this->r->flag=this->flag;

         this->flag=inf;

     }

 }

 inline void seg::maintain()

 {

     this->data=merge(this->l->data, this->r->data);

     this->size=this->l->size+this->r->size;

 }

 inline seg * newseg()

 {

     seg * ret=portOfSeg++;

     ret->flag=inf;

     return ret;

 }

 seg * build(int l, int r)

 {

     seg * t=newseg();

     int m=(l+r)>>;

     if (l==r)

     {

         t->data=node(x[r_idx[m]]);

         t->size=;

     }

     else

     {

         t->l=build(l, m);

         t->r=build(m+, r);

         t->maintain();

     }

     return t;

 }

 void update (seg * t, int l, int r, int ql, int qr, int v)

 {

     if (l==ql && r==qr)

     {

         t->data.ssum=t->size*v;

         t->data.lmax=t->data.rmax=t->data.smax=max(t->data.ssum, );

         t->flag=v;

     }

     else

     {

         int m=(l+r)>>;

         t->pushdown();

         if (qr<=m) update(t->l, l, m, ql, qr, v);

         else if (ql>m) update(t->r, m+, r, ql, qr, v);

         else update(t->l, l, m, ql, m, v), update(t->r, m+, r, m+, qr, v);

         t->maintain();

     }

 }

 node query(seg * t, int l, int r, int ql, int qr)

 {

     node ret;

     if (l==ql && r==qr)

         ret=t->data;

     else

     {

         int m=(l+r)>>;

         t->pushdown();

         if (qr<=m) ret=query(t->l, l, m, ql, qr);

         else if (ql>m) ret=query(t->r, m+, r, ql, qr);

         else ret=merge(query(t->l, l, m, ql, m), query(t->r, m+, r, m+, qr));

         t->maintain();

     }

     return ret;

 }

 inline void dfsTree()

 {

     static edge * t[sizeOfNumber];

     memset(f, 0xFF, sizeof(f)); f[]=;

     memmove(t, e, sizeof(e));

     int lim;

     for (int u=;true; )

     {

         if (!s[u])

         {

             s[u]=; lim=lg(d[u]);

             a[][u]=f[u];

             for (int i=;i<=lim;i++)

                 a[i][u]=a[i-][a[i-][u]];

         }

         edge *& i=t[u];

         for ( ;i && f[i->point]>=;i=i->next);

         if (i)

         {

             f[i->point]=u;

             d[i->point]=d[u]+;

             u=i->point;

         }

         else

         {

             if (u==) break;

             s[f[u]]+=s[u];

             if (s[u]>s[son[f[u]]])

                 son[f[u]]=u;

             u=f[u];

         }

     }

 }

 inline void dfsChain()

 {

     static edge * t[sizeOfNumber];

     memmove(t, e, sizeof(e));

     top[]=;

     for (int u=;true; )

     {

         if (!idx[u])

         {

             idx[u]=++tmp;

             r_idx[tmp]=u;

         }

         if (son[u] && !idx[son[u]])

         {

             top[son[u]]=top[u];

             u=son[u];

             continue;

         }

         edge *& i=t[u];

         for ( ;i && idx[i->point];i=i->next);

         if (i)

         {

             top[i->point]=i->point;

             u=i->point;

         }

         else

         {

             if (u==)

                 break;

             u=f[u];

         }

     }

 }

 inline int lca(int u, int v)

 {

     if (d[u]<d[v]) swap(u, v);

     while (int dist=d[u]-d[v])

         u=a[__builtin_ctz(dist)][u];

     if (u==v) return u;

     for (int i=;i>=;i--)

         if (a[i][u]!=a[i][v])

             u=a[i][u],

             v=a[i][v];

     return a[][u];

 }

 inline int anc(int u, int d)

 {

     for (int i=;i>=;i--)

         if ((d>>i)&)

             u=a[i][u];

     return u;

 }

 inline void update(int u, int v, int c)

 {

     while (top[u]!=top[v])

     {

         if (d[top[u]]<d[top[v]]) swap(u, v);

         update(t, , n, idx[top[u]], idx[u], c);

         u=f[top[u]];

     }

     if (d[u]>d[v]) swap(u, v);

     update(t, , n, idx[u], idx[v], c);

 }

 inline node query(int u, int a)

 {

     node ret;

     while (top[u]!=top[a])

     {

         ret=merge(query(t, , n, idx[top[u]], idx[u]), ret);

         u=f[top[u]];

     }

     ret=merge(query(t, , n, idx[a], idx[u]), ret);

     return ret;

 }

GSS7

 #include <cstdio>

 #include <cstring>

 typedef long long llint;

 typedef unsigned int uint;

 namespace IO

 {

     const int sizeOfInput=;

     char inputBuffer[sizeOfInput], * port=inputBuffer;

     inline void assign();

     inline void close();

     inline char getch();

     inline uint getint();

     inline void putint(uint);

 };

 namespace random

 {

     llint num, seed, mod;

     inline void srand();

     inline int getrand();

 };

 namespace treap

 {

     const int sizeOfMemory=;

     uint C[][];

     uint P[sizeOfMemory][];

     struct node

     {

         uint c[];

         uint key, size;

         int weight;

         node * left, * right;

         inline node();

         inline void maintain();

     };

     node * null=new node();

     node memory[sizeOfMemory], * port=memory;

     inline void prepare();

     inline node * newnode(uint);

     inline void update(node * , uint);

     void split(node * , uint, node *& , node *& );

     node * merge(node * , node * );

 };

 int main()

 {

     using namespace treap;

     using namespace IO;

     node * root=null;

     node * L, * M, * R;

     int N, Q;

     int pos, val, l, r, k;

     char ch;

     assign();

     random::srand();

     prepare();

     N=getint();

     for (int i=;i<N;i++)

         root=merge(root, newnode(getint()));

     for (Q=getint();Q;Q--)

     {

         ch=getch();

         if (ch=='I')

         {

             pos=getint(), val=getint();

             M=treap::newnode(val);

             split(root, pos, L, R);

             L=merge(L, M);

             root=merge(L, R);

         }

         else if (ch=='D')

         {

             pos=getint();

             split(root, pos, L, R);

             split(R, , M, R);

             root=merge(L, R);

         }

         else if (ch=='R')

         {

             pos=getint(), val=getint();

             split(root, pos, L, R);

             split(R, , M, R);

             update(M, val);

             L=merge(L, M);

             root=merge(L, R);

         }

         else

         {

             l=getint(), r=getint(), k=getint();

             split(root, r+, L, R);

             split(L, l, L, M);

             putint(M->c[k]);

             L=merge(L, M);

             root=merge(L, R);

         }

     }

     return ;

 }

 namespace IO

 {

     inline void assign()

     {

         freopen("GSS8.in", "r", stdin);

         freopen("GSS8.out", "w", stdout);

         fread(inputBuffer, , , stdin);

     }

     inline void close()

     {

         fclose(stdin);

         fclose(stdout);

     }

     inline char getch()

     {

         register char ch;

         do ch=*(port++); while (ch<'A' || ch>'Z');

         return ch;

     }

     inline uint getint()

     {

         register uint num=;

         register char ch;

         do ch=*(port++); while (ch<'' || ch>'');

         do num=num*+ch-'', ch=*(port++); while (ch>='' && ch<='');

         return num;

     }

     inline void putint(uint num)

     {

         char stack[];

         register int top=;

         if (num==) stack[top=]='';

         for ( ;num;num/=) stack[++top]=num%+'';

         for ( ;top;top--) putchar(stack[top]);

         putchar('\n');

     }

 }

 namespace random

 {

     inline void srand()

     {

         num=, seed=, mod=;

         for (int i=;i<=;i++)

             getrand();

     }

     inline int getrand()

     {

         num=num*seed%mod;

         return num;

     }

 }

 namespace treap

 {

     inline node::node()

     {

         memset(c, , sizeof(c));

         key=size=;

         weight=;

         left=right=this;

     }

     inline void node::maintain()

     {

         int tmp=left->size+;

         size=left->size++right->size;

         for (int i=;i<=;i++) c[i]=left->c[i];

         for (int i=;i<=;i++) c[i]+=key*P[tmp][i];

         for (int i=;i<=;i++) for (int j=;j<=i;j++)

             c[i]+=C[i][j]*P[tmp][i-j]*right->c[j];

     }

     inline void prepare()

     {

         C[][]=;

         for (int i=;i<=;i++)

         {

             C[i][]=;

             for (int j=;j<i;j++)

                 C[i][j]=C[i-][j-]+C[i-][j];

             C[i][i]=;

         }

         for (int i=;i<sizeOfMemory;i++)

         {

             P[i][]=;

             for (int j=;j<=;j++)

                 P[i][j]=P[i][j-]*i;

         }

     }

     inline node * newnode(uint _key)

     {

         node * ret=port++;

         for (int i=;i<=;i++) ret->c[i]=_key;

         ret->key=_key, ret->size=;

         ret->weight=random::getrand();

         ret->left=ret->right=null;

         return ret;

     }

     inline void update(node * t, uint _key)

     {

         for (int i=;i<=;i++) t->c[i]=_key;

         t->key=_key;

     }

     void split(node * t, uint k, node *& l, node *& r)

     {

         if (t==null) l=r=null;

         else

         {

             if (t->left->size<k)

             {

                 l=t;

                 split(t->right, k-t->left->size-, t->right, r);

                 l->maintain();

             }

             else

             {

                 r=t;

                 split(t->left, k, l, t->left);

                 r->maintain();

             }

         }

     }

     node * merge(node * l, node * r)

     {

         if (l==null) return r->maintain(), r;

         if (r==null) return l->maintain(), l;

         if (l->weight>r->weight)

         {

             l->right=merge(l->right, r);

             l->maintain();

             return l;

         }

         else

         {

             r->left=merge(l, r->left);

             r->maintain();

             return r;

         }

     }

 }

GSS8