看心情填坑

厚颜无耻骗访问量系列。

2MB内存限制非常的难受。

splay就算把fa、l、r压成一个long long，sum和num压成一个long long再加一个size的int也还是会挂。所以我们要考虑内存更小的数据结构。

块状链表（本人一不当心就写成了分块+链表_(:зゝ∠)_）

对于每个节点维护前驱后继以及它的值，对于每个块维护这个块的开始节点和sum。为了减小常数和方便我还维护了一个belong。维护belong的时候可以顺便维护belong修改对sum的影响。

对于第一二个操作直接维护即可。

对于第三个操作，枚举每个开始节点在区间内的块，记开始节点为k，把开始节点改为pre(k)，同时修改pre(k)的belong。

当L是开始节点时还要把R修改为开始节点。

为了卡内存把点的4个信息压成了一个long long，华丽丽地TLE了。

算一下17+17+20+9=63刚刚好可以用二进制压位。压进去就过了。

#include<cstdio>
#include<cmath>
#define S1 131071
#define S2 131071
#define S3 1048575
using namespace std;
int sum[320],st[320];
long long f[100005];
char s[2];
int n,m,size;
inline int read(){
	int ret=0;char c=getchar();
	while((c<'0')||(c>'9'))c=getchar();
	while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
	return ret;
}
inline int pre(int k){return f[k]&S1;}
void cpre(int k,int x){f[k]^=pre(k)^x;}
inline int next(int k){return (f[k]>>17)&S2;}
void cnext(int k,long long x){f[k]^=((next(k)^x)<<17);}
inline int num(int k){return (f[k]>>34)&S3;}
void cnum(int k,long long x){f[k]^=(num(k)^x)<<34;}
inline int belong(int k){return f[k]>>54;}
void cbelong(int k,long long x){sum[belong(k)]-=num(k);f[k]^=(belong(k)^x)<<54;sum[x]+=num(k);}
void del(int k){
	if(pre(k))cnext(pre(k),next(k));
	if(next(k))cpre(next(k),pre(k));
}
void ins(int x,int k){
	cpre(x,pre(k));cnext(x,k);
	if(pre(x))cnext(pre(x),x);
	if(next(x))cpre(next(x),x);
}
inline int find(int k){
	if(k==0)return 0;
	int p=st[(k-1)/size];
	k=(k-1)%size;
	while(k)p=next(p),k--;
	return p;
}
inline long long query(int l,int r){
	long long ans=0;
	if((l-1)/size==(r-1)/size){
		int k=find(l);
		while(l<=r)ans+=num(k),l++;
		return ans;
	}
	for(int i=(l-1)/size+1;i<(r-1)/size;i++)ans+=sum[i];
	int rest=size-(l-1)%size,k=pre(st[(l-1)/size+1]);
	while(rest)ans+=num(k),k=pre(k),rest--;
	rest=(r-1)%size+1,k=st[(r-1)/size];
	while(rest)ans+=num(k),k=next(k),rest--;
	return ans;
}
void rev(int l,int r){
	int L=find(l),R=find(r);
	cbelong(R,belong(L));
	if(st[(l-1)/size]==L)st[(l-1)/size]=R;
	for(int i=(l-1)/size+1;i<=(r-1)/size;i++)cbelong(pre(st[i]),i),st[i]=pre(st[i]);
	del(R);ins(R,L);
}
int main(){
	n=read();m=read();size=int(sqrt(n)+0.00001);
	for(int i=1;i<=n;i++)cnum(i,read()),cnext(i,i+1),cpre(i,i-1);
	for(int i=1;i<=n;i++){
		cbelong(i,(i-1)/size);
		sum[0]+=num(i);
		if((i-1)%size==0)st[(i-1)/size]=i;
	}
	while(m--){
		scanf("%s",s);
		if(s[0]=='Q'){int l=read(),r=read();printf("%lld\n",query(l,r));}
		if(s[0]=='C'){
			int k=find(read()),x=read();
			sum[belong(k)]+=x-num(k);
			cnum(k,x);
		}
		if(s[0]=='M'){
			int r=read(),l=read();
			rev(l,r);
		}	
	}
}

叶队讲了一个复杂度非常优但是非常难写的写法，我这里大略口胡一下。

首先维护全局的链表，为了卡内存可以只记后继。

定一个S，把连续的每S个位置压成一个点，把n/S个点构成一个splay，记下每个节点在原数列中的开始节点，它包含了原序列的节点数s以及sum,size。

查询操作直接splay上的部分算出来，点内的部分暴力，和分块差不多。

对于某一个位置我们可以在splay上二分来查找它属于splay中的哪一个点。这样第二个操作就可以解决了。

第三个操作等价于从splay中的某个节点的链表中拎一个节点出来插到splay的另一个节点的链表当中。

链表部分暴力维护,splay只要维护一下sum和s没有什么问题。

但是多次操作之后就会导致某个节点包含原序列中的很多节点，这样查询复杂度就不对了。

所以每次第三个操作完之后，判断一下，是否存在某个节点s≥2S，是的话就把这个splay节点拆成两个splay节点。

假如存在连续两个节点s和≤S，是的话就把这两个节点合并。

想想就觉得难写。复杂度O(Q(S+log(n/S)))对这题来说S稍微开大一些可以减少内存。