2018CCPC-Wannafly Winter Camp Day5 [I. Sorting] （非常优秀的题目，十分巧妙的线段树）

先呈上原题链接

这是一道非常优秀的线段的题目，如此说的原因不是因为它的操作有多么新奇，而是因为解该题的思路有着很好的启发作用。

题意：
你有一个数列 $a_{1}, a_{2}, \dots, a_{n}$ ，你要模拟一个类似于快速排序的过程。有一个固定的数字 $x$ 。

你要支持三种操作：

询问区间 $[l, r]$ 之间的元素的和，也就是 $\sum_{i = l}^{r} a_{i}$
对区间 $[l, r]$ 进行操作，也就是说你把区间中所有的数字拿出来，然后把小于等于 $x$ 的数字按顺序放在左边，把大于 $x$ 的数字按顺序放在右边，把这些数字接起来，放回到数列中。比如说 $x = 3$ ，你的区间里的数字是 $1, 5, 3, 2, 4$ ，那么操作完之后区间里面的数字变为 $1, 3, 2, 5, 4$
对区间 $[l, r]$ 进行操作，也就是说你把区间中所有的数字拿出来，然后把大于 $x$ 的数字按顺序放在左边，把小于等于 $x$ 的数字按顺序放在右边，把这些数字接起来，放回到数列中。

思路：

首先注意到， $x$ 是给定的。所以无论何时，所有小于等于 $x$ 的数的相对顺序不会变，所有大于 $x$ 的数的相对顺序也不会变。
那么我们把所有大于 $x$ 的数看作是 $1$ ，把所有小于等于 $x$ 的数看作是 $0$ ，每一次区间更新前先查询一下该区间有多少个 $1$ ，然后就是把区间的前（后）一段赋值为 $1$ 后（前）一段赋值为 $0$ 。至此就可以想想查询操作有没有怎么好的性质。
对于区间 $[l, r]$ 查询，我们可以直接查询 $[1, l - 1]$ 区间有多少个大于 $x$ 的数，即这个区间有多少个 $1$ ，再查询 $[1, r]$ 区间有多少个大于 $x$ 的数。然后因为他们的相对顺序不变，我们就可以知道要查询的 $[l, r]$ 区间内大于 $x$ 的数是从第几个起到第几个的了，此时我们只需要维护一个大于 $x$ 的数的前缀和就行了。对于小于等于 $x$ 的数同理。
所有该题用线段树加前缀和就能搞定。

坑点：
注意有没有爆范围。。。

good luck and have fun!!!
附上代码：

#include<bits/stdc++.h>
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define test(flag,value) cout<<flag<<":"<<(value)<<endl
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int MAXN=8e5+10;
const int MOD=998244353;
const double PI=acos(-1);

int row[MAXN],sum[MAXN],a[MAXN],lazy[MAXN];
LL pre1[MAXN],pre2[MAXN];
inline void push_up(int rt)
{
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void push_down(int rt,int l,int r)
{
	if(lazy[rt]==-1) return;
	int m=(l+r)>>1;
	lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];
	sum[rt<<1]=lazy[rt]*(m-l+1);
	sum[rt<<1|1]=lazy[rt]*(r-m);
	lazy[rt]=-1;
}
void build(int l,int r,int rt)
{
	if(l==r)
	{
		sum[rt]=a[l];
		return;
	}
	int m=(l+r)>>1;
	build(l,m,rt<<1);
	build(m+1,r,rt<<1|1);
	push_up(rt);
}
void update(int L,int R,int l,int r,int rt,int val)
{
	if(L>R)return;
	if(L<=l&&r<=R)
	{
		sum[rt]=val*(r-l+1);
		lazy[rt]=val;
		return;
	}
	int m=(l+r)>>1;
	push_down(rt,l,r);
	if(m>=L) update(L,R,l,m,rt<<1,val);
	if(m<R)  update(L,R,m+1,r,rt<<1|1,val);
	push_up(rt);
}
int query(int L,int R,int l,int r,int rt)
{
	if(L>R)return 0;
	if(L<=l&&r<=R)return sum[rt];
	int m=(l+r)>>1;
	push_down(rt,l,r);
	int res=0;
	if(m>=L) res+=query(L,R,l,m,rt<<1);
	if(m<R)  res+=query(L,R,m+1,r,rt<<1|1);
	return res;
}
int main(void)
{
	int n,q,x;
	mem(lazy,-1);
	scanf("%d%d%d",&n,&q,&x);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",row+i);
		if(row[i]>x)
			a[i]=1;
		else a[i]=0;
	}
	build(1,n,1);
	pre1[0]=pre2[0]=0;
	int p1=1,p2=1;
	for(int i=1;i<=n;i++)
	{
		if(a[i]==1)
		{
			pre2[p2]=row[i]+pre2[p2-1];
			p2++;
		}
		else
		{
			pre1[p1]=row[i]+pre1[p1-1];
			p1++;
		}
	}
	while(q--)
	{
		int type,l,r;
		scanf("%d%d%d",&type,&l,&r);
		if(type==1)
		{
			LL ans=0;
			int totr=query(1,r,1,n,1);
			int totl=query(1,l-1,1,n,1);
			LL tot1=pre2[totr]-pre2[totl];
			LL tot0=pre1[r-totr]-pre1[l-1-totl];
			ans=tot1+tot0;
			printf("%lld\n", ans);
		}
		else if(type==2)
		{
			int tot1=query(l,r,1,n,1);
			update(r-tot1+1,r,1,n,1,1);
			update(l,r-tot1,1,n,1,0);
		}
		else if(type==3)
		{
			int tot1=query(l,r,1,n,1);
			update(l,l+tot1-1,1,n,1,1);
			update(l+tot1,r,1,n,1,0);
		}
	}
}