正文

Sorting（好题）

IP云
IP云V管理员/0 阅读
12/02
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

Sorting

https://www.zhixincode.com/contest/21/problem/I?problem_id=324

题目描述

你有一个数列a_1, a_2, \dots, a_na1​,a2​,…,an​，你要模拟一个类似于快速排序的过程。有一个固定的数字xx。

你要支持三种操作：

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

输入描述

第一行三个整数n, q, x ( 1\leq n, q \leq 2*10^5, 0\leq x\leq 10^9)n,q,x(1≤n,q≤2∗105,0≤x≤109)表示元素的个数和询问的个数。

接下来一行nn个整数a_1, a_2, \dots, a_n(1\leq a_i\leq 10^9)a1​,a2​,…,an​(1≤ai​≤109)。

接下来qq行，每行三个正整数p, l, r (1\leq p\leq 3), 1\leq l\leq r\leq np,l,r(1≤p≤3),1≤l≤r≤n表示操作种类和区间。

输出描述

对于每个第一种操作，输出一行，表示答案。

样例输入 1 

5 9 3

1 5 3 2 4

1 1 5

2 1 5

1 1 1

1 2 2

1 3 3

1 4 4

1 5 5

3 3 5

1 1 4

样例输出 1 

15

1

3

2

5

4
15

首先，排序后小于等于x和大于x的数字的相对顺序是不变的，所以我们可以用0和1分别代替小于等于x和大于x的值。

先记录下小于等于x的数字和大于x的数字的前缀和，然后当区间修改的时候，我们就可以用前缀和来计算区间的值

区间修改的过程：当p==2时，把区间前半部分赋值为0，后半部分赋值为1，p==3时相反 

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define maxn 200005

 int n,q;

 ll x;

 int tree[maxn<<],lazy[maxn<<];

 ll a[maxn];

 //tree中记录了1的个数 

 void push_up(int rt){

     tree[rt]=tree[rt<<]+tree[rt<<|];

 }

 void build(int l,int r,int rt){

     lazy[rt]=-;

     if(l==r){

         if(a[l]<=x) tree[rt]=;

         else tree[rt]=;

         return;

     }

     int mid=l+r>>;

     build(lson);

     build(rson);

     push_up(rt);

 }

 void push_down(int len,int rt){

     if(lazy[rt]!=-){

         if(lazy[rt]==){

             lazy[rt<<]=;

             lazy[rt<<|]=;

             tree[rt<<]=;

             tree[rt<<|]=;

         }

         else{

             lazy[rt<<]=;

             lazy[rt<<|]=;

             tree[rt<<]=len-len/;

             tree[rt<<|]=len/;

         }

         lazy[rt]=-;

     }

 }

 //区间置0和置1

 void add(int L,int R,int v,int l,int r,int rt){

     if(L<=l&&R>=r){

         if(v==) tree[rt]=;

         else tree[rt]=r-l+;

         lazy[rt]=v;

         push_down(r-l+,rt);

         return;

     }

     push_down(r-l+,rt);

     int mid=l+r>>;

     if(L<=mid) add(L,R,v,lson);

     if(R>mid) add(L,R,v,rson);

     push_up(rt);

 } 

 int query(int L,int R,int l,int r,int rt){///查询在L前面1的数量

     if(L<=l&&R>=r){

         return tree[rt];

     }

     push_down(r-l+,rt);

     int mid=l+r>>;

     int ans=;

     if(L<=mid) ans+=query(L,R,lson);

     if(R>mid) ans+=query(L,R,rson);

     push_up(rt);

     return ans;

 }

 ll small[maxn],big[maxn];

 int main(){

     std::ios::sync_with_stdio(false);

     cin>>n>>q>>x;

     int s_co=,b_co=;

     for(int i=;i<=n;i++){

         cin>>a[i];

         if(a[i]<=x) small[s_co]=small[s_co-]+a[i],s_co++;

         else big[b_co]=big[b_co-]+a[i],b_co++;

     }

     build(,n,);

     int p,l,r;

     for(int i=;i<=q;i++){

         cin>>p>>l>>r;

         if(p==){

             int one1,one2,one,zero1,zero2,zero;

             one1=query(,r,,n,);

             if(>l-) one2=;

             else one2=query(,l-,,n,);

             zero1=r-one1;

             if(>l-) zero2=;

             else zero2=l--one2;

             cout<<small[zero1]-small[zero2]+big[one1]-big[one2]<<endl;

         }

         else if(p==){

             int one=query(l,r,,n,);

             int zero=r-l+-one;

             if(l<=l+zero-) add(l,l+zero-,,,n,);

             add(l+zero,r,,,n,);

         }

         else{

             int one=query(l,r,,n,);

             int zero=r-l+-one;

             if(l<=l+one-) add(l,l+one-,,,n,);

             add(l+one,r,,,n,);

         }

     }

 }

相关阅读

目录[+]