首页 > 代码库 > [bzoj4552]排序

[bzoj4552]排序

解题关键:观察发现答案可进行二分,二分答案,将大于等于答案的数记为1,小于的记为0,从而可以使用线段树的区间赋值和区间求和解决。

复杂度:$O(nlog^2n)$

  1 #include<cstdio>  2 #include<cstring>  3 #include<algorithm>  4 #include<cstdlib>  5 #include<cmath>  6 #include<iostream>  7 using namespace std;  8 typedef long long ll;  9 const int maxn=200005; 10 int a[maxn],sum[maxn<<3],add[maxn<<3]; 11 int t1[maxn],t2[maxn],t3[maxn],v[maxn]; 12 int n,m,r; 13  14 void pushdown(int rt,int m){ 15     if(add[rt]!=-1){ 16         add[rt<<1]=add[rt]; 17         add[rt<<1|1]=add[rt]; 18         sum[rt<<1]=add[rt]*(m-(m>>1)); 19         sum[rt<<1|1]=add[rt]*(m>>1); 20         add[rt]=-1; 21     } 22 } 23  24 void pushup(int rt){ 25     sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 26 } 27  28 void build(int rt,int l,int r){ 29     add[rt]=-1; 30     if(l==r){ 31         sum[rt]=v[l]; 32         return; 33     } 34     int mid=(l+r)>>1; 35     build(rt<<1,l,mid); 36     build(rt<<1|1, mid+1, r); 37     pushup(rt); 38 } 39  40 void update(int rt,int l,int r,int tl,int tr,int c){ 41     if(tl>tr) return;//落掉这句话导致在bzoj一直re 42     if(tl<=l&&tr>=r){ 43         sum[rt]=c*(r-l+1); 44         add[rt]=c; 45         return; 46     } 47     pushdown(rt, r-l+1); 48     int mid=(l+r)>>1; 49     if(tl<=mid) update(rt<<1,l,mid,tl,tr, c); 50     if(tr>mid)  update(rt<<1|1, mid+1, r, tl, tr, c); 51     pushup(rt); 52 } 53  54 int query(int rt,int l,int r,int tl,int tr){ 55     if(tl<=l&&tr>=r){ 56         return sum[rt]; 57     } 58     pushdown(rt,r-l+1); 59     int mid=(l+r)>>1,res=0; 60     if(tl<=mid) res+=query(rt<<1,l,mid,tl,tr); 61     if(tr>mid) res+=query(rt<<1|1,mid+1,r,tl,tr); 62     return res; 63 } 64  65 bool check(int x){ 66     for(int i=1;i<=n;i++) v[i]= a[i]>=x?1:0; 67     build(1, 1, n); 68     for(int i=0;i<m;i++){ 69         if(t1[i]){ 70             int tmp=query(1, 1, n, t2[i], t3[i]); 71             update(1, 1, n, t2[i], t2[i]+tmp-1, 1); 72             update(1, 1, n, t2[i]+tmp, t3[i], 0); 73         } 74         else{ 75             int tmp=query(1, 1, n, t2[i], t3[i]); 76             update(1, 1, n, t2[i], t3[i]-tmp, 0); 77             update(1, 1, n, t3[i]-tmp+1, t3[i], 1); 78         } 79     } 80     if(query(1, 1, n, r, r)==1) return true; 81     else return false; 82 } 83  84 int erfen(int l,int r){ 85     while(l<r){ 86         int mid=(l+r+1)>>1; 87         if(check(mid)) l=mid; 88         else r=mid-1; 89     } 90     return r; 91 } 92  93 int main(){ 94     scanf("%d%d",&n,&m); 95     for(int i=1;i<=n;i++)   scanf("%d",a+i); 96     for(int i=0;i<m;i++)    scanf("%d%d%d",t1+i,t2+i,t3+i); 97     scanf("%d",&r); 98     int ans=erfen(1, n); 99     printf("%d\n",ans);100     return 0;101 }

 

[bzoj4552]排序