本文共 1912 字，大约阅读时间需要 6 分钟。
分析
二分一个数表示查询位置的数是多少，将序列中大于等于这个数的数赋为1，其余赋为0，对于每一个区间查询区间和（即区间内1的个数），然后区间修改将前/后半部分修改为1，其余修改为0即可
代码
#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;int a[100100],d[400400],col[400400],k[100100],x[100100],y[100100];inline void update(int le,int ri,int wh,int pl,int sum){ col[wh]=-1; if(le==ri){ d[wh]=sum; return; } int mid=(le+ri)>>1; if(mid>=pl)update(le,mid,wh<<1,pl,sum); else update(mid+1,ri,wh<<1|1,pl,sum); d[wh]=d[wh<<1]+d[wh<<1|1]; return;}inline void build(int le,int ri,int wh,int X,int Y,int sum){ if(le>=X&&ri<=Y){ col[wh]=sum; d[wh]=(ri-le+1)*sum; return; } int mid=(le+ri)>>1; if(col[wh]!=-1){ col[wh<<1]=col[wh<<1|1]=col[wh]; d[wh<<1]=col[wh]*(mid-le+1); d[wh<<1|1]=col[wh]*(ri-mid); col[wh]=-1; } if(mid>=X)build(le,mid,wh<<1,X,Y,sum); if(mid <<1|1,X,Y,sum); d[wh]=d[wh<<1]+d[wh<<1|1]; return;}inline int q(int le,int ri,int wh,int X,int Y){ if(le>=X&&ri<=Y)return d[wh]; int mid=(le+ri)>>1,ans=0; if(col[wh]!=-1){ col[wh<<1]=col[wh<<1|1]=col[wh]; d[wh<<1]=col[wh]*(mid-le+1); d[wh<<1|1]=col[wh]*(ri-mid); col[wh]=-1; } if(mid>=X)ans+=q(le,mid,wh<<1,X,Y); if(mid <<1|1,X,Y); d[wh]=d[wh<<1]+d[wh<<1|1]; return ans;}int main(){ int n,m,i,j,l,r,pos; scanf("%d%d",&n,&m); for(i=1;i<=n;i++)scanf("%d",&a[i]); for(i=1;i<=m;i++)scanf("%d%d%d",&k[i],&x[i],&y[i]); scanf("%d",&pos); l=1,r=n+1; while(r-l>1){ int mid=(l+r)>>1; for(i=1;i<=n;i++) update(1,n,1,i,(a[i]>=mid)); for(i=1;i<=m;i++){ int sum=q(1,n,1,x[i],y[i]); if(k[i]){ build(1,n,1,x[i],x[i]+sum-1,1); build(1,n,1,x[i]+sum,y[i],0); }else { build(1,n,1,x[i],y[i]-sum,0); build(1,n,1,y[i]-sum+1,y[i],1); } } if(q(1,n,1,pos,pos))l=mid; else r=mid; } printf("%d\n",l); return 0;}
转载于:https://www.cnblogs.com/yzxverygood/p/9751008.html