先呈上原题链接
这是一道非常优秀的线段的题目,如此说的原因不是因为它的操作有多么新奇,而是因为解该题的思路有着很好的启发作用。
题意:
你有一个数列 a1,a2,…,an ,你要模拟一个类似于快速排序的过程。有一个固定的数字 x。
你要支持三种操作:
- 询问区间 [l,r] 之间的元素的和,也就是 ∑i=lrai
- 对区间 [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);
}
}
}