题目链接:CCPC-WannaFly 2018WC Day5 I.Sorting
题意:
给定一个序列以及一个x,然后有三种操作:
- 查询区间和。
- 把小于等于x的数字按顺序放在左边,把大于x的数字按顺序放在右边,把这些数字接起来,放回到数列中。
- 把小于等于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;
}