NKOJ2504 区间翻转问题 时间限制 : 10000 MS 空间限制 : 265000 KB
问题描述 给你一个长度为N的序列{ai}和M个操作 1.查询第k个数的值 2.将第k个数增加d 3.查询一段区间的和 4.查询一段区间的最大值 5.将一段区间镜面翻转（例如序列{1,2,3,4,5,6}，将从2到5的区间翻转后得到序列{1,5,4,3,2,6}） 对于除操作2,5以外的操作，输出相应的答案
输入格式 第一行两个正整数N,M 第二行N个整数，为初始的序列 第三行到底M+2行，每行若干个整数 ·如果第一个数为1，那么后面一个正整数k，表示查询第k个数的值 ·如果第一个数是2，那么后面两个正整数k,d，表示将ak增加d ·如果第一个数为3，那么后面两个正整数l,r，表示查询从al到ar的区间和 ·如果第一个数为4，那么后面两个正整数l,r，表示查询从al到ar的最大值 ·如果第一个数为5，那么后面两个正整数l,r，表示翻转从al到ar的这个区间
输出格式 除操作2,5外每个操作输出占一行，一个整数，为本次提问的答案
样例输入 6 8 1 2 3 4 5 6 1 4 3 2 5 4 2 2 5 2 5 3 1 3 5 2 5 2 5 1 4 1 6
样例输出 4 14 2 10 6
提示 2<=N<=100000 1<=M<=100000 原序列1<=ai<=1000 每次1<=k<=N，1<=l<=r<=N,1<=d<=1000
来源 感谢nodgd命题并提供数据
思路： 维护下标，将每个数的下标存入树中。 （1）、查询第k个数：直接找 （2）、第k个数增加d：直接加 （3）、维护区间和。操作时将x-1为根、y+1为右儿子，则y+1左儿子的sum即为所求 （4）、维护区间最大。操作同（3） （5）、lazy标记。操作同（3），再将y+1左儿子打标记
（3）、（4）、（5）注意覆盖1或n的情况特殊处理
#include<cstdio> #include<iostream> using namespace std; const int need=100005; int a[need]; //............................................. inline void in_(int &d) { char t=getchar();bool mark=0; while(t<'0'||t>'9') {if(t=='-') mark=1;t=getchar();} for(d=0;!(t<'0'||t>'9');t=getchar()) d=(d<<1)+(d<<3)+t-'0';if(mark) d=-d; } inline void out_(int x) { if(x<0) {x=-x;putchar('-');} if(x>=10) out_(x/10); putchar(x+'0'); } //............................................. int tot,root; int fa[need],ls[need],rs[need],si[need],num[need],sum[need],mm[need]; bool lazy[need]; inline void putdown(int x) { lazy[x]=0; swap(ls[x],rs[x]); if(ls[x]) lazy[ls[x]]^=1; if(rs[x]) lazy[rs[x]]^=1; } inline void NBHB(int x) { si[x]=si[ls[x]]+si[rs[x]]+1; sum[x]=sum[ls[x]]+sum[rs[x]]+a[num[x]]; mm[x]=max(a[num[x]],max(mm[ls[x]],mm[rs[x]])); } inline void sr(int x) { int y=fa[x],z=fa[y]; if(lazy[z]) putdown(z); if(lazy[y]) putdown(y); if(lazy[x]) putdown(x); ls[z]==y ? ls[z]=x :rs[z]=x; fa[x]=z; ls[y]=rs[x]; fa[rs[x]]=y; rs[x]=y; fa[y]=x; NBHB(y),NBHB(x); } inline void sl(int x) { int y=fa[x],z=fa[y]; if(lazy[z]) putdown(z); if(lazy[y]) putdown(y); if(lazy[x]) putdown(x); ls[z]==y ? ls[z]=x :rs[z]=x; fa[x]=z; rs[y]=ls[x]; fa[ls[x]]=y; ls[x]=y; fa[y]=x; NBHB(y),NBHB(x); } int top,s[need]; void splay(int x) { top=0;s[++top]=x; for(int i=x;fa[i];i=fa[i]) s[++top]=fa[i]; while(top) { if(lazy[s[top]]) putdown(s[top]); top--; } int y; while(y=fa[x]) { if(ls[y]==x) sr(x); else sl(x); } root=x; } void insert(int d) //不用putdown,因为先建树，再操作 { if(tot==0) { num[root=tot=1]=d; sum[1]=mm[1]=a[d]; si[1]=1; ls[1]=rs[1]=fa[1]=0; return ; } tot++; int p=root; while(true) { si[p]++; sum[p]+=a[d]; mm[p]=max(mm[p],a[d]); if(d<num[p]) if(ls[p]) p=ls[p]; else{ls[p]=tot;break;} else if(rs[p]) p=rs[p]; else{rs[p]=tot;break;} } si[tot]=1,sum[tot]=a[tot],fa[tot]=p,mm[tot]=a[d],num[tot]=d; splay(tot); } //............................................. int k,d,l,r; int getk(int k) { int p=root; while(true) { if(lazy[p]) putdown(p); if(ls[p]&&si[ls[p]]>=k) p=ls[p]; else if(k==1||(ls[p]&&si[ls[p]]==k-1)) return p; else {k-=si[ls[p]]+1;p=rs[p];} } } void change(int xx) { int y; while(fa[xx]!=root) { y=fa[xx]; if(lazy[y]) putdown(y); if(lazy[xx]) putdown(xx); if(ls[y]==xx) sr(xx); else sl(xx); } } int get() { if(l>1&&r<tot) { int a=getk(l-1),b=getk(r+1); splay(a); change(b); return ls[b]; } else if(l>1&&r==tot) { int a=getk(l-1); splay(a); return rs[a]; } else if(l==1&&r<tot) { int b=getk(r+1); splay(b); return ls[b]; } else return root; } //............................................. int main() { int n,m;scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) in_(a[i]),insert(i); for(int i=1,b,kk;i<=m;i++) { in_(b); if(b==1) { in_(k); out_(a[num[getk(k)]]),putchar(10); } else if(b==2) { in_(k),in_(b); kk=num[getk(k)]; a[kk]+=b; splay(kk); } else { in_(l),in_(r); kk=get(); if(b==3) out_(sum[kk]),putchar(10); else if(b==4) out_(mm[kk]),putchar(10); else lazy[kk]^=1; } } }