题意
你现在要用数据结构维护一个长度为n的序列。
这个序列支持三种操作：
1 l r：将序列中的第l项到第r项这一段翻转。
2 l r：查询序列中[l,r]这一段的和。
3 p：回到第p个历史版本。
每一个翻转操作的时候记作序列处于一次新的版本，初始的版本是0。
每一个回到历史版本之后再操作的版本都是一个最新版本，不是第p+1版本。
\(1\leq n\leq 50000\)
代码
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
const int N=65536;
const int M=65536;
const int S=8388608;
int n,m;
int a[N];
namespace Treap {
int rt[M],nowVer,allVer;
int tot;
struct Node {
int c[2]; int rev;
int fix; //fix=dep
int dat,sum;
int siz;
Node(int _fix=0,int _dat=0,int _siz=0) {
c[0]=c[1]=rev=0;
fix=_fix;
dat=sum=_dat;
siz=_siz;
}
}tr[S];
struct D {
int c[2];
D(void) {
c[0]=c[1]=0;
}
};
void Update(int x) {
tr[x].sum=tr[tr[x].c[0]].sum+tr[tr[x].c[1]].sum+tr[x].dat;
tr[x].siz=tr[tr[x].c[0]].siz+tr[tr[x].c[1]].siz+1;
}
int New_Node(int key,int fix,int dat) {
int x=++tot;
tr[x]=Node(fix,dat,1);
return x;
}
int Copy_Node(int form) {
int x=++tot;
tr[x]=tr[form];
return x;
}
int Build(int *a,int l,int r,int dep) {
int mid=(l+r)>>1;
int x=New_Node(mid,dep,a[mid]);
if (l<mid)
tr[x].c[0]=Build(a,l,mid-1,dep+1);
if (mid<r)
tr[x].c[1]=Build(a,mid+1,r,dep+1);
Update(x);
return x;
}
void Clear(int x) {
if (!tr[x].rev) return; tr[x].rev=0;
if (tr[x].c[0]>0) {
tr[x].c[0]=Copy_Node(tr[x].c[0]);
tr[tr[x].c[0]].rev^=1;
}
if (tr[x].c[1]>0) {
tr[x].c[1]=Copy_Node(tr[x].c[1]);
tr[tr[x].c[1]].rev^=1;
}
swap(tr[x].c[0],tr[x].c[1]);
}
D Split(int x,int rk) {
D t; if (!x) return t;
int x1=Copy_Node(x); Clear(x1);
if (rk<=tr[tr[x1].c[0]].siz) {
t=Split(tr[x1].c[0],rk);
tr[x1].c[0]=t.c[1]; Update(x1);
t.c[1]=x1;
}
else if (rk==tr[tr[x1].c[0]].siz+1) {
t.c[1]=tr[x1].c[1];
tr[x1].c[1]=0; Update(x1);
t.c[0]=x1;
}
else {
t=Split(tr[x1].c[1],rk-1-tr[tr[x1].c[0]].siz);
tr[x1].c[1]=t.c[0]; Update(x1);
t.c[0]=x1;
}
return t;
}
int Merge(int x1,int x2) {
if (!x1) return x2;
if (!x2) return x1;
if (tr[x1].fix<tr[x2].fix) {
int x3=Copy_Node(x1);
Clear(x3);
tr[x3].c[1]=Merge(tr[x3].c[1],x2);
Update(x3);
return x3;
}
else {
int x3=Copy_Node(x2);
Clear(x3);
tr[x3].c[0]=Merge(x1,tr[x3].c[0]);
Update(x3);
return x3;
}
}
}
int rd(void) {
int x=0,f=1; char c=getchar();
while (!isdigit(c)) {
if (c=='-') f=-1;
c=getchar();
}
while (isdigit(c)) {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
void Goto(int p) {
using namespace Treap;
nowVer=p;
}
void Reverse(int l,int r) {
using namespace Treap;
D t1=Split(rt[nowVer],r);
D t2=Split(t1.c[0],l-1); //use t2.c[1]
int x=Copy_Node(t2.c[1]);
tr[x].rev^=1;
rt[++allVer]=Merge(Merge(t2.c[0],x),t1.c[1]);
nowVer=allVer;
}
int Query(int l,int r) {
using namespace Treap;
D t1=Split(rt[nowVer],r);
D t2=Split(t1.c[0],l-1);
return tr[t2.c[1]].sum;
}
int main(void) {
#ifndef ONLINE_JUDGE
freopen("N.in","r",stdin);
freopen("N.out","w",stdout);
#endif
n=rd(),m=rd();
rep(i,1,n) a[i]=rd();
Treap::rt[0]=Treap::Build(a,1,n,1);
rep(i,1,m) {
int c=rd();
switch (c) {
case 1: {
int l=rd(),r=rd();
Reverse(l,r);
break;
}
case 2: {
int l=rd(),r=rd();
int ans=Query(l,r);
printf("%d\n",ans);
break;
}
case 3: {
int p=rd();
Goto(p);
break;
}
}
}
return 0;
}