#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