首页 > 代码库 > [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]排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。