又轮到我出题，随便出了场娱乐赛，T1画风比较正常，T2乱哈希，T3提答找规律，这里就贴下T1吧。
T1.签到题
题目大意：一个长度为n的序列，支持以下100种操作：操作1，查询若每次能使区间同时+1或同时-1，把[l,r]区间都变成0至少要几次；操作10，区间加上一个数；操作11，区间翻转；操作100，回到k次操作前的状态。（n,操作数<=10^5）
思路：Splay或Treap维护区间左右端点和区间内差分绝对值之和，每次查询的答案为这三者绝对值之和。由于空间限制较紧，可持久化无法通过，考虑离线，第i次操作回到k次前就让i-k-1向i连边，否则i-1向i连边，从头开始dfs，离开时撤销，时间复杂度O(nlogn)，空间复杂度O(n)。
#include<cstdio> #include<algorithm> using namespace std; #define ll long long inline int read() { int x,f=1;char c; while((c=getchar())<'0'||c>'9')if(c=='-')f=0; for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=(x<<3)+(x<<1)+c-'0'; return f?x:-x; } #define MN 100000 #define rtf MN+3 #define L(x) c[x][0] #define R(x) c[x][1] #define rt L(rtf) #define rr R(rt) #define rrl L(rr) struct edge{int nx,t;}e[MN+5]; int a[MN+5],t[MN+5],l[MN+5],r[MN+5],ad[MN+5],h[MN+5],en; inline int z(int x){return x<0?-x:x;} struct data { int lh,rh;ll s; friend data operator+(data a,data b){return (data){a.lh,b.rh,a.s+b.s+z(a.rh-b.lh)};} }d[MN+5]; int fa[MN+5],c[MN+5][2],s[MN+5],mk[MN+5],rv[MN+5]; ll ans[MN+5]; inline void ins(int x,int y){e[++en]=(edge){h[x],y};h[x]=en;} inline void up(int x) { s[x]=s[L(x)]+s[R(x)]+1; d[x]=(data){a[x],a[x],0}; if(L(x))d[x]=d[L(x)]+d[x]; if(R(x))d[x]=d[x]+d[R(x)]; } inline void rev(int x) { swap(L(x),R(x)); swap(d[x].lh,d[x].rh); rv[x]^=1; } inline void mark(int x,int z) { d[x].lh+=z;d[x].rh+=z; a[x]+=z;mk[x]+=z; } inline void down(int x) { if(rv[x])rev(L(x)),rev(R(x)),rv[x]=0; if(mk[x])mark(L(x),mk[x]),mark(R(x),mk[x]),mk[x]=0; } void build(int f,int t,int l,int r) { if(l>r)return; int mid=l+r>>1; fa[c[f][t]=mid]=f;s[f=c[f][t]]=1; build(f,0,l,mid-1);build(f,1,mid+1,r); up(f); } void rotate(int x) { int f=fa[x],ff=fa[f],l=R(f)==x,r=l^1; fa[f]=x;fa[x]=ff;fa[c[x][r]]=f; c[ff][R(ff)==f]=x;c[f][l]=c[x][r];c[x][r]=f; up(f); } void splay(int x,int rf) { for(int f;(f=fa[x])!=rf;rotate(x)) if(fa[f]!=rf)rotate(L(fa[f])==f^L(f)==x?x:f); up(x); } int find(int x,int k) { while(down(x),k) if(k<=s[L(x)])x=L(x); else if(k-=s[L(x)]+1)x=R(x); return x; } void work(int x) { if(t[x]==1) { splay(find(rt,l[x]),rtf);splay(find(rt,r[x]+2),rt); ans[x]=d[rrl].s+z(d[rrl].lh)+z(d[rrl].rh)>>1; } if(t[x]==10) { splay(find(rt,l[x]),rtf);splay(find(rt,r[x]+2),rt); mark(rrl,ad[x]);up(rr);up(rt); } if(t[x]==11) { splay(find(rt,l[x]),rtf);splay(find(rt,r[x]+2),rt); rev(rrl);up(rr);up(rt); } for(int i=h[x];i;i=e[i].nx)work(e[i].t); if(t[x]==10) { splay(find(rt,l[x]),rtf);splay(find(rt,r[x]+2),rt); mark(rrl,-ad[x]);up(rr);up(rt); } if(t[x]==11) { splay(find(rt,l[x]),rtf);splay(find(rt,r[x]+2),rt); rev(rrl);up(rr);up(rt); } } int main() { freopen("sign.in","r",stdin); freopen("sign.out","w",stdout); int n,m,i; n=read();m=read(); for(i=1;i++<=n;)a[i]=read(); build(rtf,0,1,n+2); for(i=1;i<=m;++i) { t[i]=read();l[i]=read(); ins(t[i]==100?i-l[i]-1:i-1,i); if(t[i]<100)r[i]=read(); if(t[i]==10)ad[i]=read(); } work(0); for(i=1;i<=m;++i)if(t[i]==1)printf("%I64d ",ans[i]); fclose(stdin);fclose(stdout);return 0; }