自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 21:46:34，当前版本为作者最后更新于2019-10-25 17:22:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先，设 ( = -1，) = 1，定义 $\text{prmax}$ 为前缀最大值，$\text{sfmin}$ 为后缀最小值，那么一个区间的答案为

$$\lceil \text{prmax}/2\rceil+\lceil|\text{sfmin}|/2\rceil $$

要维护答案，考虑众所周知的 线段树/平衡树 五问：
(跟 zyb 学的)

1、每个节点需要记录哪些信息？

要记录区间和，前缀最大、最小，后缀最大、最小。

2、需要哪些标记？

只需要题目中的三种操作标记即可。

3、如何下传标记？

先来考虑标记优先级：取反、覆盖、翻转。

打取反标记时，区间和、节点值直接取反；$\text{prmax}$ 变 $-\text{prmin}$，$\text{prmin}$ 变 $-\text{prmax}$，对于后缀同理。别忘了还要对覆盖标记取反。

对于覆盖标记，若赋值为正数，$\text{prmax,sfmax}$ 变区间和，$\text{prmin,sfmin}$ 变为 $0$。对于赋值为负数同理。

翻转标记比较简单，除了交换左右儿子，再交换前缀、后缀的最大最小和即可。

4、如何对区间整体修改？

这个没什么好说的，直接在对应区间的子树根上打标记即可。

5、如何合并区间 (上传信息)？

这里可以参考 GSS1 传标记的做法，也就是这样：

prmax[u] = max(prmax[ls],sum[ls]+a[u]+prmax[rs]);
prmin[u] = min(prmin[ls],sum[ls]+a[u]+prmin[rs]);
sfmax[u] = max(sfmax[rs],sum[rs]+a[u]+sfmax[ls]);
sfmin[u] = min(sfmin[rs],sum[rs]+a[u]+sfmin[ls]);

这里 ls 和 rs 分别指左右儿子。 解决了上面五问，整个题就解决啦。

参考代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#define reg register
#define N 100003
#define ls son[u][0]
#define rs son[u][1]
using namespace std;

inline void read(int &x){
	x = 0;
	char c = getchar();
	while(c<'0'||c>'9') c = getchar();
	while(c>='0'&&c<='9'){
		x = (x<<3)+(x<<1)+(c^48);
		c = getchar();
	}
}

int n,q;

struct fhqTreap{
	int a[N],son[N][2],rnd[N],sum[N],sfmax[N],sfmin[N];
	int tag[N],size[N],prmax[N],prmin[N];
	bool rev[N],inv[N];
	int rt,cnt;
	
	inline int neww(int x){
		int u = ++cnt;
		sum[u] = a[u] = x;
		if(x==1) prmax[u] = sfmax[u] = 1;
		else sfmin[u] = prmin[u] = -1;
		size[u] = 1;
		rnd[u] = rand();
		return u;
	}
	
	inline void pushup(int u){
		sum[u] = sum[ls]+sum[rs]+a[u];
		size[u] = size[ls]+size[rs]+1;
		prmax[u] = max(prmax[ls],sum[ls]+a[u]+prmax[rs]);
		prmin[u] = min(prmin[ls],sum[ls]+a[u]+prmin[rs]);
		sfmax[u] = max(sfmax[rs],sum[rs]+a[u]+sfmax[ls]);
		sfmin[u] = min(sfmin[rs],sum[rs]+a[u]+sfmin[ls]);
	}
	
	inline void pushr(int u){
		swap(ls,rs);
		swap(prmax[u],sfmax[u]);
		swap(prmin[u],sfmin[u]);
		rev[u] ^= 1;
	}
	
	inline void pushiv(int u){
		a[u] = -a[u];
		sum[u] = -sum[u];
		int x = prmax[u],y = prmin[u];
		prmin[u] = -x,prmax[u] = -y;
		x = sfmax[u],y = sfmin[u];
		sfmin[u] = -x,sfmax[u] = -y;
		inv[u] ^= 1;
		tag[u] = -tag[u];
	}
	
	inline void pushc(int u,int k){
		a[u] = tag[u] = k;
		sum[u] = size[u]*k;
		if(k==1){
			prmin[u] = sfmin[u] = 0;
			prmax[u] = sfmax[u] = sum[u];
		}else{
			prmax[u] = sfmax[u] = 0;
			prmin[u] = sfmin[u] = sum[u];
		}
	}
	
	inline void pushdown(int u){
		if(inv[u]){
			if(ls) pushiv(ls);
			if(rs) pushiv(rs);
			inv[u] = 0;
		}
		if(tag[u]){
			if(ls) pushc(ls,tag[u]);
			if(rs) pushc(rs,tag[u]);
			tag[u] = 0;
		}
		if(!rev[u]) return;
		if(ls) pushr(ls);
		if(rs) pushr(rs);
		rev[u] = 0;
	}
	
	int merge(int u,int v){
		pushdown(u);
		pushdown(v);
		if(!u||!v) return u|v;
		if(rnd[u]<rnd[v]){
			son[u][1] = merge(son[u][1],v);
			pushup(u);
			return u;
		}else{
			son[v][0] = merge(u,son[v][0]);
			pushup(v);
			return v;
		}
	}
	
	void split(int cur,int k,int &u,int &v){
		if(!cur){
			u = v = 0;
			return;
		}
		pushdown(cur);
		if(size[son[cur][0]]<k){
			u = cur;
			split(son[u][1],k-size[ls]-1,son[u][1],v);
		}else{
			v = cur;
			split(son[v][0],k,u,son[v][0]);
		}
		pushup(cur);
	}
	
	inline void push_back(int x){
		rt = merge(rt,neww(x));
	}
	
	inline int query(int l,int r){
		int x,y,z,t,res;
		split(rt,l-1,x,y);
		split(y,r-l+1,y,z);
		t = prmax[y];
		res = (t&1)?(t>>1)+1:(t>>1);
		t = abs(sfmin[y]);
		res += (t&1)?(t>>1)+1:(t>>1);
		rt = merge(merge(x,y),z);
		return res;
	}
	
	inline void reverse(int l,int r){
		int x,y,z;
		split(rt,l-1,x,y);
		split(y,r-l+1,y,z);
		pushr(y);
		rt = merge(merge(x,y),z);
	}
	
	inline void replace(int l,int r,int k){
		int x,y,z;
		split(rt,l-1,x,y);
		split(y,r-l+1,y,z);
		pushc(y,k);
		rt = merge(merge(x,y),z);
	}
	
	inline void invert(int l,int r){
		int x,y,z;
		split(rt,l-1,x,y);
		split(y,r-l+1,y,z);
		pushiv(y);
		rt = merge(merge(x,y),z);
	}
	
	void dfs(int u){
		pushdown(u);
		if(ls) dfs(ls);
		printf("%d ",a[u]);
		if(rs) dfs(rs);
	}
}T;

inline bool check(char c){
	return (c>='a'&&c<='z')||(c>='A'&&c<='Z');
}

int main(){
	srand(time(0));
	int l,r,k;
	read(n),read(q);
	char op,c = getchar();
	while(c!='('&&c!=')') c = getchar();
	while(c=='('||c==')'){
		T.push_back(c==')'?1:-1);
		c = getchar();
	}
	while(q--){
		c = getchar();
		while(!check(c)) c = getchar();
		op = c;
		while(check(c)) c = getchar();
		read(l),read(r);
		if(op=='R'){
			c = getchar();
			while(c!='('&&c!=')') c = getchar();
			k = c==')'?1:-1;
		}
		if(op=='R') T.replace(l,r,k);
		else if(op=='S') T.reverse(l,r);
		else if(op=='I') T.invert(l,r);
		else printf("%d\n",T.query(l,r));
	}
    return 0;
}