题目链接：CCPC-WannaFly 2018WC Day5 I.Sorting

题意：

给定一个序列以及一个x，然后有三种操作：

1. 查询区间和。
2. 把小于等于x的数字按顺序放在左边，把大于x的数字按顺序放在右边，把这些数字接起来，放回到数列中。
3. 把小于等于x的数字按顺序放在右边，把大于x的数字按顺序放在左边，把这些数字接起来，放回到数列中。

题解：

把大于x的数看作1，小于等于的看作0，转化为01序列。

然后可以发现，无论怎样操作，1的相对位置和0的相对位置都是不会发生改变的。

所以区间求和时只需要用线段树确定是从第几个0加到第几个0，从第几个1加到第几个1，然后用前缀和维护即可。

简而言之，就是线段树区间求和+区间赋值+前缀和。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q,x;
int a[200009];
int tree[200009*4],lazy[200009*4];
ll sum0[200009],sum1[200009];
void pushup(int rt)
{
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
void pushdown(int l,int r,int rt)
{
    if(lazy[rt]!=-1)
    {
        lazy[rt<<1]=lazy[rt];
        lazy[rt<<1|1]=lazy[rt];
        int mid=(l+r)>>1;
        tree[rt<<1]=(mid-l+1)*lazy[rt];
        tree[rt<<1|1]=(r-mid)*lazy[rt];
        lazy[rt]=-1;
    }
}
void build(int l,int r,int rt)
{
    lazy[rt]=-1;
    tree[rt]=0;
    if(l==r)
    {
        tree[rt]=(a[l]>x);
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
void update(int L,int R,int val,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        lazy[rt]=val;
        tree[rt]=val*(r-l+1);
        return;
    }
    pushdown(l,r,rt);
    int mid=(l+r)>>1;
    if(L<=mid)
        update(L,R,val,l,mid,rt<<1);
    if(R>mid)
        update(L,R,val,mid+1,r,rt<<1|1);
    pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
    if(L>R)
        return 0;
    if(L<=l&&r<=R)
        return tree[rt];
    pushdown(l,r,rt);
    int mid=(l+r)>>1;
    int res=0;
    if(L<=mid)
        res+=query(L,R,l,mid,rt<<1);
    if(R>mid)
        res+=query(L,R,mid+1,r,rt<<1|1);
    return res;
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out1.txt","w",stdout);
    scanf("%d%d%d",&n,&q,&x);
    int p1=0,p0=0;
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        if(a[i]>x)
            p1++,sum1[p1]=sum1[p1-1]+a[i];
        else
            p0++,sum0[p0]=sum0[p0-1]+a[i];
    }
    build(1,n,1);
    while(q--)
    {
        int op,l,r;
        scanf("%d%d%d",&op,&l,&r);
        if(op==1)
        {
            int rb=query(1,r,1,n,1);
            int lb=query(1,l-1,1,n,1);
            printf("%lld\n",(sum1[rb]-sum1[lb])+(sum0[r-rb]-sum0[l-1-lb]));
        }
        else    if(op==2)
        {
            int temp=query(l,r,1,n,1);
            temp=(r-l+1)-temp;
            update(l,l+temp-1,0,1,n,1);
            update(l+temp,r,1,1,n,1);
        }
        else
        {
           int temp=query(l,r,1,n,1);
           update(l,l+temp-1,1,1,n,1);
           update(l+temp,r,0,1,n,1);
        }
    }
    return 0;
}