I - Sorting

将小于等于X的数当做0,大于x的数当做1,因为交换后相对顺序不会变,就可以预处理出各自的前缀和,根据处于的位置计算值。用线段树来维护区间内01的个数,Ok啦

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
#define ls rt<<1
#define rs rt<<1|1
int a[maxn],b[maxn];
long long int r0[maxn],r1[maxn];
int cnt1=1,cnt0=1;

struct tree{
    int l,r;
    int x;
    int sum;
    int lazy;
}t[maxn*4];
void pushdown(int rt){

    if(t[rt].lazy==1){
        t[ls].sum=t[ls].r-t[ls].l+1;
        t[rs].sum=t[rs].r-t[rs].l+1;
        t[ls].lazy=1;
        t[rs].lazy=1;
    }
    else if(t[rt].lazy==-1){
        t[ls].sum=0;
        t[rs].sum=0;
        t[ls].lazy=-1;
        t[rs].lazy=-1;
    }
    t[rt].lazy=0;
}
void build(int rt,int l,int r){
    t[rt].l=l;
    t[rt].r=r;
    t[rt].x=0;
    t[rt].sum=0;
    t[rt].lazy=0;
    if(t[rt].l==t[rt].r){
        return ;
    }
    int mid=l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
}
void dadd(int rt,int x){
    if(t[rt].l==x && t[rt].r==x){
        t[rt].x=1;
        t[rt].sum++;
        return;
    }
    int mid=t[rt].l+t[rt].r>>1;
    if(mid<x)
    dadd(rs,x);
    else
    dadd(ls,x);
    t[rt].sum=t[ls].sum+t[rs].sum;
}
void change(int rt,int ql,int qr,int l,int r,int x,int type){

    if(ql>=l && qr<=r){
            if(x==0){
                 t[rt].sum=0;
                 t[rt].lazy=-1;
            }
            else{
                t[rt].sum=qr-ql+1;
                t[rt].lazy=1;
            }

        return ;
    }
    pushdown(rt);
    int mid=ql+qr>>1;
    if(l<=mid)
        change(ls,ql,mid,l,r,x,type);
    if(r>mid)
        change(rs,mid+1,qr,l,r,x,type);
    t[rt].sum=t[ls].sum+t[rs].sum;
}
int query(int rt,int ql,int qr,int l,int r){
    if(l>r)return 0;
     if(ql>=l && qr<=r){
        return t[rt].sum;
    }
    pushdown(rt);
    int mid=ql+qr>>1;
    int sum=0;
    if(l<=mid)
      sum+=  query(ls,ql,mid,l,r);
    if(r>mid)
    sum+=query(rs,mid+1,qr,l,r);
    return sum;
}
int main(){

    int n,q,x;
    cin>>n>>q>>x;
    build(1,1,n);
    for(int i=1;i<=n;i++){
         cin>>a[i];
        if(a[i]<=x)r0[cnt0]=r0[cnt0++-1]+a[i];
        else dadd(1,i),r1[cnt1]=r1[cnt1++-1]+a[i];
    }
    int o,L,R;

    for(int i=1;i<=q;i++){
          cin>>o>>L>>R;
          if(o==1){
            int k=query(1,1,n,L,R);//区间内有k个1
            int k1=query(1,1,n,1,L-1);//前面有k1个1
            int S=R-L+1;
            int k0=S-k;
            int k00=L-1-k1;
            long long int sum1=r1[k1+k]-r1[k1];
            long long int sum0=r0[ S-k + L-1-k1 ]-r0[L-1-k1];
            cout<<sum1 + sum0<<endl;
          }
          else if(o==2){
            int k=query(1,1,n,L,R);//区间内有k个1
            int k1=R-L+1-k;//k1个0
            change(1,1,n,L,L+k1-1,0,0);
            change(1,1,n,L+k1,R,1,1);
          }
          else if(o==3){
            int k=query(1,1,n,L,R);//区间内有k个1
            int k1=R-L+1-k;//k1个0
            change(1,1,n,L,L+k-1,1,1);
            change(1,1,n,L+k,R,0,0);
          }
    }

    return 0;
}