Codeforces Gym - 101234A Hacker Cups and Balls [二分+线段树]
题意:有n个球和n个杯子,编号都从1-n。每一个杯子里有一个球,第ai个球放在第i个杯子里。接下来要进行m次操作,每次操作给出l,r。当l<r时,将[l,r]范围内的杯子里的球按升序排序,否则降序排,求位置(1+n)/2的数是多少。
题解:二分答案,对于当前mid,我们将大于等于mid的数记为1,否则为0,通过线段树模拟排序过程,区间更新,单点查询,若中间的数是1,则答案肯定大于等于当前的数,l右移。
AC代码:
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define N 100005 int n,m; int ql[N],qr[N]; int a[N],tree[N*4],ad[N*4]; void build(int L,int R,int root,int num) { ad[root]=0; if(L==R) { tree[root]=(a[L]>=num); return ; } int mid=L+R>>1; build(L,mid,root<<1,num); build(mid+1,R,root<<1|1,num); tree[root]=tree[root<<1]+tree[root<<1|1]; } void pushdown(int L,int R,int root) { int mid=L+R>>1; ad[root<<1]=ad[root<<1|1]=ad[root]; if(ad[root]==1) { tree[root<<1|1]=min(tree[root],R-mid); tree[root<<1]=tree[root]-tree[root<<1|1]; } if(ad[root]==2) { tree[root<<1]=min(tree[root],mid-L+1); tree[root<<1|1]=tree[root]-tree[root<<1]; } ad[root]=0; } int query(int l,int r,int L,int R,int root) { if(l<=L&&R<=r)return tree[root]; if(ad[root])pushdown(L,R,root); int mid=L+R>>1; if(r<=mid)return query(l,r,L,mid,root<<1); else if(l>mid)return query(l,r,mid+1,R,root<<1|1); else return query(l,mid,L,mid,root<<1)+query(mid+1,r,mid+1,R,root<<1|1); tree[root]=tree[root<<1]+tree[root<<1|1]; } int query2(int pos,int L,int R,int root) { if(L==R)return tree[root]; if(ad[root])pushdown(L,R,root); int mid=L+R>>1; if(pos<=mid)return query2(pos,L,mid,root<<1); else return query2(pos,mid+1,R,root<<1|1); tree[root]=tree[root<<1]+tree[root<<1|1]; } void update(int l,int r,int L,int R,int root,int flag,int sum) { if(l<=L&&R<=r) { ad[root]=flag; tree[root]=sum; return ; } if(ad[root])pushdown(L,R,root); int mid=L+R>>1,lsum,rsum; if(flag==1)rsum=min(r-mid,sum),lsum=sum-rsum; else lsum=min(mid-l+1,sum),rsum=sum-lsum; if(r<=mid)update(l,r,L,mid,root<<1,flag,sum); else if(l>mid)update(l,r,mid+1,R,root<<1|1,flag,sum); else { update(l,mid,L,mid,root<<1,flag,lsum); update(mid+1,r,mid+1,R,root<<1|1,flag,rsum); } tree[root]=tree[root<<1]+tree[root<<1|1]; } bool judge(int mid) { build(1,n,1,mid); for(int i=0;i<m;i++) { int sum=query(min(ql[i],qr[i]),max(ql[i],qr[i]),1,n,1); if(ql[i]<=qr[i])update(ql[i],qr[i],1,n,1,1,sum); else update(qr[i],ql[i],1,n,1,2,sum); } return query2((1+n)/2,1,n,1); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=0;i<m;i++) scanf("%d%d",&ql[i],&qr[i]); int l=1,r=n,ans; while(l<=r) { int mid=l+r>>1; if(judge(mid)) { ans=mid; l=mid+1; } else r=mid-1; } printf("%d ",ans); }