GSS1
线段树上维护以下 $4$ 个东西:
- 区间和
- 区间最大前缀和
- 区间最大后缀和
- 区间最大子段和
合并两个区间应该比较简单,这里不再赘述。
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=50000+10;
int n,Q,a[N];
struct node { int sum,lmax,rmax,ans; };
node operator +(node a,node b) {
node c;
c.sum=a.sum+b.sum;
c.lmax=max(a.lmax,a.sum+b.lmax);
c.rmax=max(b.rmax,b.sum+a.rmax);
c.ans=max(max(a.ans,b.ans),a.rmax+b.lmax);
return c;
}
#define ls (o<<1)
#define rs (o<<1|1)
node t[N<<2];
inline void build(int o,int l,int r) {
if (l==r) {
t[o].sum=t[o].lmax=t[o].rmax=t[o].ans=a[l];
return;
}
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
t[o]=t[ls]+t[rs];
}
inline node query(int o,int l,int r,int ql,int qr) {
if (ql<=l&&r<=qr) return t[o];
int mid=(l+r)>>1;
if (qr<=mid) return query(ls,l,mid,ql,qr);
else if (ql>mid) return query(rs,mid+1,r,ql,qr);
else return query(ls,l,mid,ql,mid)+query(rs,mid+1,r,mid+1,qr);
}
#undef ls
#undef rs
int main() {
n=read();
for (re int i=1;i<=n;++i) a[i]=read();
build(1,1,n);
Q=read();
while (Q--) {
int l=read(),r=read();
printf("%d\n",query(1,1,n,l,r).ans);
}
return 0;
}
GSS2
这题就很神仙了。
把所有询问离线并按右端点排序,然后从左往右扫。
对于线段树的每个叶子节点 $[i,i]$,假设当前扫到了 $p$ ,那么该节点存的是 $\displaystyle\sum_{j=i}^pa_j$ 。
设 $pre_i$ 表示上一个和 $a_i$ 相同的数,那么每次把 $[pre_i+1,i]$ 加上 $a+i$ 即可。
再额外维护一个历史最大值,这样子扫到 $r$ 时就只要询问 $[l,r]$ 的历史最大值的最大值就可以得到答案了。
那么线段树维护这些东西即可:
- 和
- 和的历史最大值
- 和的懒标记
- 和的历史最大值的懒标记
合并两个区间应该也比较简单,详见代码。
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=100000+10;
int n,Q,a[N];
#define ls (o<<1)
#define rs (o<<1|1)
int now_mx[N<<2],now_lz[N<<2],his_mx[N<<2],his_lz[N<<2];
inline void pushup(int o) {
now_mx[o]=max(now_mx[ls],now_mx[rs]);
his_mx[o]=max(his_mx[ls],his_mx[rs]);
}
inline void pushdown(int o) {
his_mx[ls]=max(his_mx[ls],now_mx[ls]+his_lz[o]);
his_lz[ls]=max(his_lz[ls],now_lz[ls]+his_lz[o]);
now_mx[ls]+=now_lz[o],now_lz[ls]+=now_lz[o];
his_mx[rs]=max(his_mx[rs],now_mx[rs]+his_lz[o]);
his_lz[rs]=max(his_lz[rs],now_lz[rs]+his_lz[o]);
now_mx[rs]+=now_lz[o],now_lz[rs]+=now_lz[o];
his_lz[o]=now_lz[o]=0;
}
inline void modify(int o,int l,int r,int ql,int qr,int w) {
if (ql<=l&&r<=qr) {
now_mx[o]+=w,now_lz[o]+=w;
his_mx[o]=max(his_mx[o],now_mx[o]);
his_lz[o]=max(his_lz[o],now_lz[o]);
return;
}
int mid=(l+r)>>1; pushdown(o);
if (ql<=mid) modify(ls,l,mid,ql,qr,w);
if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
pushup(o);
}
inline int query(int o,int l,int r,int ql,int qr) {
if (ql<=l&&r<=qr) return his_mx[o];
int mid=(l+r)>>1,res=0; pushdown(o);
if (ql<=mid) res=max(res,query(ls,l,mid,ql,qr));
if (qr>mid) res=max(res,query(rs,mid+1,r,ql,qr));
pushup(o); return res;
}
#undef ls
#undef rs
int pre[N],pos[N<<1],ans[N];
struct Query { int id,l,r; } q[N];
bool operator <(Query a,Query b) { return a.r<b.r; }
int main() {
n=read();
for (re int i=1;i<=n;++i) a[i]=read();
for (re int i=1;i<=n;++i) pre[i]=pos[a[i]+N],pos[a[i]+N]=i;
Q=read();
for (re int i=1;i<=Q;++i) q[i]=(Query){i,read(),read()};
sort(q+1,q+Q+1);
for (re int i=1,j=1;i<=n;++i) {
modify(1,1,n,pre[i]+1,i,a[i]);
while (q[j].r==i) ans[q[j].id]=query(1,1,n,q[j].l,i),++j;
}
for (re int i=1;i<=Q;++i) printf("%d\n",ans[i]);
return 0;
}
GSS3
就是 GSS1 加个修改操作,没什么好说的。
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=50000+10;
int n,Q,a[N];
struct node { int sum,lmax,rmax,ans; };
node operator +(node a,node b) {
node c;
c.sum=a.sum+b.sum;
c.lmax=max(a.lmax,a.sum+b.lmax);
c.rmax=max(b.rmax,b.sum+a.rmax);
c.ans=max(max(a.ans,b.ans),a.rmax+b.lmax);
return c;
}
#define ls (o<<1)
#define rs (o<<1|1)
node t[N<<2];
inline void build(int o,int l,int r) {
if (l==r) {
t[o].sum=t[o].lmax=t[o].rmax=t[o].ans=a[l];
return;
}
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
t[o]=t[ls]+t[rs];
}
inline void modify(int o,int l,int r,int p,int w) {
if (l==r) {
t[o].sum=t[o].lmax=t[o].rmax=t[o].ans=w;
return;
}
int mid=(l+r)>>1;
if (p<=mid) modify(ls,l,mid,p,w);
else modify(rs,mid+1,r,p,w);
t[o]=t[ls]+t[rs];
}
inline node query(int o,int l,int r,int ql,int qr) {
if (ql<=l&&r<=qr) return t[o];
int mid=(l+r)>>1;
if (qr<=mid) return query(ls,l,mid,ql,qr);
else if (ql>mid) return query(rs,mid+1,r,ql,qr);
else return query(ls,l,mid,ql,mid)+query(rs,mid+1,r,mid+1,qr);
}
#undef ls
#undef rs
int main() {
n=read();
for (re int i=1;i<=n;++i) a[i]=read();
build(1,1,n);
Q=read();
while (Q--) {
int op=read(),l=read(),r=read();
if (!op) modify(1,1,n,l,r);
else printf("%d\n",query(1,1,n,l,r).ans);
}
return 0;
}
事实上这题可以动态 DP ,点我。(当然 GSS1 也是可以动态 DP 的。)
GSS4
用线段树维护区间和。
注意到一个数开根号变成 $1$ 的次数不大,而变成 $1$ 后就不用修改了。
假设现在在修改一个区间:如果该区间内的所有数开根号都不会变了,那就不修改了;否则直接暴力修改到叶节点即可。
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=100000+10;
int n,Q;
#define ls (o<<1)
#define rs (o<<1|1)
int sum[N<<2],f[N<<2];
inline void pushup(int o) { sum[o]=sum[ls]+sum[rs],f[o]=f[ls]&f[rs]; }
inline void build(int o,int l,int r) {
if (l==r) { sum[o]=read(),f[o]=sum[o]<=1; return; }
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
pushup(o);
}
inline void modify(int o,int l,int r,int ql,int qr) {
if (f[o]) return;
if (l==r) {
sum[o]=floor(sqrt(sum[o]));
if (sum[o]<=1) f[o]=1;
return;
}
int mid=(l+r)>>1;
if (ql<=mid) modify(ls,l,mid,ql,qr);
if (qr>mid) modify(rs,mid+1,r,ql,qr);
pushup(o);
}
inline int query(int o,int l,int r,int ql,int qr) {
if (ql<=l&&r<=qr) return sum[o];
int mid=(l+r)>>1,res=0;
if (ql<=mid) res+=query(ls,l,mid,ql,qr);
if (qr>mid) res+=query(rs,mid+1,r,ql,qr);
return res;
}
#undef ls
#undef rs
signed main() {
int T=0;
while (scanf("%lld",&n)==1) {
build(1,1,n); Q=read();
printf("Case #%lld:\n",++T);
while (Q--) {
int op=read(),l=read(),r=read();
if (l>r) swap(l,r);
if (op) printf("%lld\n",query(1,1,n,l,r));
else modify(1,1,n,l,r);
}
puts("");
}
return 0;
}
GSS5
在 GSS1 的基础上大力讨论一下即可。
- 如果两区间没有交,答案就是 $[x_1,y_1]$ 的最大后缀和加 $(y_1,x_2)$ 的和加 $[x_2,y_2]$ 的最大前缀和。
- 如果两区间有交,答案为以下三者中的最大值:
- $[x_2,y_1]$ 的最大子段和。
- $[x_1,x_2)$ 的最大后缀和加 $[x_2,y_2]$ 的最大前缀和。
- $[x_1,y_1]$ 的最大后缀和加 $(y_1,y_2]$ 的最大后缀和。
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=10000+10;
int n,Q,a[N];
struct node { int sum,lmax,rmax,ans; };
node operator +(node a,node b) {
node c;
c.sum=a.sum+b.sum;
c.lmax=max(a.lmax,a.sum+b.lmax);
c.rmax=max(b.rmax,b.sum+a.rmax);
c.ans=max(max(a.ans,b.ans),a.rmax+b.lmax);
return c;
}
#define ls (o<<1)
#define rs (o<<1|1)
node t[N<<2];
inline void build(int o,int l,int r) {
if (l==r) {
t[o].sum=t[o].lmax=t[o].rmax=t[o].ans=a[l];
return;
}
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
t[o]=t[ls]+t[rs];
}
inline node query(int o,int l,int r,int ql,int qr) {
if (ql<=l&&r<=qr) return t[o];
int mid=(l+r)>>1;
if (qr<=mid) return query(ls,l,mid,ql,qr);
else if (ql>mid) return query(rs,mid+1,r,ql,qr);
else return query(ls,l,mid,ql,mid)+query(rs,mid+1,r,mid+1,qr);
}
#undef ls
#undef rs
inline int calc(int l1,int r1,int l2,int r2) {
int res;
if (r1<l2) {
res=query(1,1,n,l1,r1).rmax;
res+=query(1,1,n,l2,r2).lmax;
if (r1+1<l2)res+=query(1,1,n,r1+1,l2-1).sum;
} else {
res=query(1,1,n,l2,r1).ans;
res=max(res,query(1,1,n,l1,l2).rmax+query(1,1,n,l2,r2).lmax-a[l2]);
res=max(res,query(1,1,n,l1,r1).rmax+query(1,1,n,r1,r2).lmax-a[r1]);
}
return res;
}
int main() {
int T=read();
while (T--) {
n=read();
for (re int i=1;i<=n;++i) a[i]=read();
build(1,1,n);
Q=read();
while (Q--) {
int l1=read(),r1=read(),l2=read(),r2=read();
printf("%d\n",calc(l1,r1,l2,r2));
}
}
return 0;
}
GSS6
在 GSS1 的基础上把线段树改成平衡树即可。
插入、删除、修改、查询就是基础的平衡树操作。
然后 pushup 和线段树有些不同,但本质是一样的。
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=200000+10;
int n,Q,a[N];
// fhq treap
int root,tot=0;
int ch[N][2],val[N],rnd[N],sz[N];
struct node { int sum,lmax,rmax,ans; } t[N];
inline int new_node(int w) {
++tot;
sz[tot]=1,val[tot]=w,rnd[tot]=rand();
t[tot].lmax=t[tot].rmax=max(w,0);
t[tot].sum=t[tot].ans=w;
return tot;
}
inline void pushup(int x) {
int ls=ch[x][0],rs=ch[x][1];
sz[x]=sz[ls]+sz[rs]+1;
t[x].sum=t[ls].sum+val[x]+t[rs].sum;
t[x].lmax=max(t[ls].lmax,t[ls].sum+val[x]+t[rs].lmax);
t[x].rmax=max(t[rs].rmax,t[rs].sum+val[x]+t[ls].rmax);
t[x].ans=max(max(t[ls].ans,t[rs].ans),t[ls].rmax+val[x]+t[rs].lmax);
}
inline void split(int o,int k,int& x,int& y) {
if (!o) { x=y=0; return; }
if (k<=sz[ch[o][0]]) y=o,split(ch[o][0],k,x,ch[o][0]);
else x=o,split(ch[o][1],k-sz[ch[o][0]]-1,ch[o][1],y);
pushup(o);
}
inline int merge(int A,int B) {
if (!A||!B) return A+B;
if (rnd[A]<rnd[B]) { ch[A][1]=merge(ch[A][1],B),pushup(A); return A; }
else { ch[B][0]=merge(A,ch[B][0]),pushup(B); return B; }
}
int main() {
srand(19260817);
n=read(); t[0].ans=-2e9;
for (re int i=1;i<=n;++i) a[i]=read();
for (re int i=1;i<=n;++i) root=merge(root,new_node(a[i]));
Q=read();
while (Q--) {
char op[2]; scanf("%s",op);
int o,r,z;
if (op[0]=='I') {
int p=read(),x=read();
split(root,p-1,o,r);
root=merge(o,merge(new_node(x),r));
} else if (op[0]=='D') {
int p=read();
split(root,p-1,o,r),split(r,1,r,z);
root=merge(o,z);
} else if (op[0]=='R') {
int p=read(),x=read();
split(root,p-1,o,r),split(r,1,r,z);
val[r]=x,pushup(r);
root=merge(o,merge(r,z));
} else {
int L=read(),R=read();
split(root,R,r,z),split(r,L-1,o,r);
printf("%d\n",t[r].ans);
root=merge(o,merge(r,z));
}
}
return 0;
}
GSS7
在 GSS1 的基础上加个树链剖分即可。
首先解决区间修改的问题,每个节点维护一个区间赋值标记即可。
链修改比较简单,把所有重链都改一遍即可。
需要注意的是链查询。因为合并两个区间时左右顺序对结果是有影响的,所以不能直接合并过去。
一种方法是维护一个 $L$ 和一个 $R$ ,分别代表左右两条链合并的结果,最后再把 $L,R$ 并起来。
写代码的时候要考虑清楚左右顺序问题,我因为这个 WA 了几发。
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=100000+10;
int n,Q,a[N];
struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
static int cnt=0;
e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}
int fa[N],dep[N],sz[N],hson[N],top[N];
int dfn[N],id[N],tim;
inline void dfs1(int u,int f) {
fa[u]=f,dep[u]=dep[f]+1,sz[u]=1;
for (re int i=head[u];i;i=e[i].nxt) {
int v=e[i].v; if (v==f) continue;
dfs1(v,u),sz[u]+=sz[v];
if (sz[v]>sz[hson[u]]) hson[u]=v;
}
}
inline void dfs2(int u,int anc) {
top[u]=anc,dfn[u]=++tim,id[tim]=u;
if (hson[u]) dfs2(hson[u],anc);
for (re int i=head[u];i;i=e[i].nxt)
if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
}
#define ls (o<<1)
#define rs (o<<1|1)
struct node {
int sum,lmax,rmax,ans,flag,setv;
node() { sum=lmax=rmax=ans=flag=setv=0; }
} t[N<<2];
node operator +(node a,node b) {
node c;
c.sum=a.sum+b.sum;
c.lmax=max(a.lmax,a.sum+b.lmax);
c.rmax=max(b.rmax,b.sum+a.rmax);
c.ans=max(max(a.ans,b.ans),a.rmax+b.lmax);
c.flag=c.setv=0;
return c;
}
inline void update(int o,int l,int r,int w) {
t[o].sum=(r-l+1)*w;
t[o].lmax=t[o].rmax=t[o].ans=max(t[o].sum,0);
t[o].flag=1,t[o].setv=w;
}
inline void pushup(int o) { t[o]=t[ls]+t[rs]; }
inline void pushdown(int o,int l,int r) {
if (t[o].flag) {
int mid=(l+r)>>1;
update(ls,l,mid,t[o].setv);
update(rs,mid+1,r,t[o].setv);
t[o].flag=t[o].setv=0;
}
}
inline void build(int o,int l,int r) {
if (l==r) {
t[o].sum=a[id[l]];
t[o].lmax=t[o].rmax=t[o].ans=max(t[o].sum,0);
t[o].flag=t[o].setv=0;
return;
}
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
pushup(o);
}
inline void modify(int o,int l,int r,int ql,int qr,int w) {
if (ql<=l&&r<=qr) { update(o,l,r,w); return; }
int mid=(l+r)>>1; pushdown(o,l,r);
if (ql<=mid) modify(ls,l,mid,ql,qr,w);
if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
pushup(o);
}
inline node query(int o,int l,int r,int ql,int qr) {
if (ql<=l&&r<=qr) return t[o];
int mid=(l+r)>>1; node res; pushdown(o,l,r);
if (ql<=mid) res=res+query(ls,l,mid,ql,qr);
if (qr>mid) res=res+query(rs,mid+1,r,ql,qr);
pushup(o); return res;
}
#undef ls
#undef rs
inline void chain_modify(int u,int v,int w) {
int tu=top[u],tv=top[v];
while (tu!=tv) {
if (dep[tu]<dep[tv]) swap(u,v),swap(tu,tv);
modify(1,1,n,dfn[tu],dfn[u],w);
u=fa[tu],tu=top[u];
}
if (dep[u]<dep[v]) swap(u,v);
modify(1,1,n,dfn[v],dfn[u],w);
}
inline int chain_query(int u,int v) {
node L,R; int tu=top[u],tv=top[v];
while (tu!=tv) {
if (dep[tu]<dep[tv]) {
R=query(1,1,n,dfn[tv],dfn[v])+R;
v=fa[tv],tv=top[v];
} else {
L=query(1,1,n,dfn[tu],dfn[u])+L;
u=fa[tu],tu=top[u];
}
}
if (dep[u]<dep[v]) R=query(1,1,n,dfn[u],dfn[v])+R;
else L=query(1,1,n,dfn[v],dfn[u])+L;
swap(L.lmax,L.rmax); return (L+R).ans;
}
int main() {
n=read();
for (re int i=1;i<=n;++i) a[i]=read();
for (re int i=1;i<n;++i) {
int u=read(),v=read();
addEdge(u,v),addEdge(v,u);
}
dfs1(1,0),dfs2(1,1),build(1,1,n);
Q=read();
while (Q--) {
int op=read();
if (op==1) {
int u=read(),v=read();
printf("%d\n",chain_query(u,v));
} else {
int u=read(),v=read(),w=read();
chain_modify(u,v,w);
}
}
return 0;
}
GSS8
感觉还是有点难。
首先这个操作显然用平衡树维护。
注意到 $k$ 很小,考虑每个节点对于每个 $k$ 都维护一个 $ans$ 。
考虑怎么合并两个区间的信息:
$$
\begin{aligned}
\sum_{i=l}^ra_i(i-l+1)^k&=\left(\sum_{i=l}^{mid}a_i(i-l+1)^k\right)+\left(\sum_{i=mid+1}^ra_i(i-l+1)^k\right)\\
&=\left(\sum_{i=l}^{mid}a_i(i-l+1)^k\right)+\left(\sum_{i=mid+1}^ra_i\big((mid-l+1)-(i-mid)\big)^k\right)\\
&=\left(\sum_{i=l}^{mid}a_i(i-l+1)^k\right)+\left(\sum_{i=mid+1}^ra_i\sum_{j=0}^k{k\choose j}(mid-l+1)^{k-j}(i-mid)^{j}\right)\\
&=\left(\sum_{i=l}^{mid}a_i(i-l+1)^k\right)+\left(\sum_{j=0}^k{k\choose j}(mid-l+1)^{k-j}\sum_{i=mid+1}^ra_i(i-mid)^{j}\right)\\
&=lans_k+\left(\sum_{j=0}^k{k\choose j}(mid-l+1)^{k-j}rans_j\right)
\end{aligned}
$$
这样子就很好合并了。
然后因为是平衡树,所以直接把当前节点丢到左区间(或右区间)去,然后就是两个区间合并了。
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
#define int unsigned int
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=200000+10,K=10+10;
int n,Q;
int C[K][K];
inline void init() {
srand(19260817);
for (re int i=C[0][0]=1;i<=10;++i)
for (re int j=C[i][0]=1;j<=i;++j)
C[i][j]=C[i-1][j]+C[i-1][j-1];
}
// fhq treap
int root,tot=0;
int ch[N][2],sz[N],val[N],rnd[N];
int ans[N][K],pw[K];
inline int newnode(int w) {
++tot;
sz[tot]=1,val[tot]=w,rnd[tot]=rand();
for (re int i=0;i<=10;++i) ans[tot][i]=w;
return tot;
}
inline void pushup(int x) {
int ls=ch[x][0],rs=ch[x][1];
sz[x]=sz[ls]+sz[rs]+1;
for (re int i=pw[0]=1;i<=10;++i) pw[i]=pw[i-1]*(sz[ls]+1);
for (re int k=0;k<=10;++k) {
ans[x][k]=ans[ls][k]+val[x]*pw[k];
for (re int i=0;i<=k;++i) ans[x][k]+=C[k][i]*pw[k-i]*ans[rs][i];
}
}
inline void split(int o,int k,int& x,int& y) {
if (!o) { x=y=0; return; }
if (k<=sz[ch[o][0]]) y=o,split(ch[o][0],k,x,ch[o][0]);
else x=o,split(ch[o][1],k-sz[ch[o][0]]-1,ch[o][1],y);
pushup(o);
}
inline int merge(int A,int B) {
if (!A||!B) return A+B;
if (rnd[A]<rnd[B]) { ch[A][1]=merge(ch[A][1],B),pushup(A); return A; }
else { ch[B][0]=merge(A,ch[B][0]),pushup(B); return B; }
}
signed main() {
init();
n=read();
for (re int i=1;i<=n;++i) root=merge(root,newnode(read()));
Q=read();
while (Q--) {
char op[2]; scanf("%s",op);
int o,r,z;
if (op[0]=='I') {
int p=read()+1,w=read();
split(root,p-1,o,r);
root=merge(merge(o,newnode(w)),r);
} else if (op[0]=='D') {
int p=read()+1;
split(root,p-1,o,r),split(r,1,r,z);
root=merge(o,z);
} else if (op[0]=='R') {
int p=read()+1,w=read();
split(root,p-1,o,r),split(r,1,r,z);
val[r]=w,pushup(r);
root=merge(merge(o,r),z);
} else {
int L=read()+1,R=read()+1,k=read();
split(root,L-1,o,r),split(r,R-L+1,r,z);
printf("%u\n",ans[r][k]);
root=merge(merge(o,r),z);
}
}
return 0;
}
3 条评论
怎么这么快
感觉除了 GSS2 和 GSS8 都挺不要脑子的啊...
您好强啊qwq