[HEOI2016/TJOI2016]排序

https://www.luogu.com.cn/problem/P2824 题解：仔细思考可以发现这道题与https://arc101.contest.atcoder.jp/tasks/arc101_b?lang=en 是等价的。二分之后原问题就转化为了$0,1$序列,可以直接用线段树维护。 ``` #include using namespace std; struct node { int l,r,data,lazy; }; struct reads { int op,l,r; }; node tree[1000001]; reads q[1000001]; int a[1000001],p[1000001],n,m,Q; void build(int k,int l,int r) { tree[k].l=l; tree[k].r=r; tree[k].lazy=-1; int mid=(l+r)/2; if (l==r) { tree[k].data=p[l]; return; } build(k*2,l,mid); build(k*2+1,mid+1,r); tree[k].data=tree[k*2].data+tree[k*2+1].data; return; } void spread(int k) { if (tree[k].lazy==0) { tree[k].lazy=-1; tree[k*2].lazy=tree[k*2+1].lazy=tree[k*2].data=tree[k*2+1].data=0; return; } if (tree[k].lazy==1) { tree[k].lazy=-1; tree[k*2].data=tree[k*2].r-tree[k*2].l+1; tree[k*2+1].data=tree[k*2+1].r-tree[k*2+1].l+1; tree[k*2].lazy=tree[k*2+1].lazy=1; return; } return; } void add(int k,int l,int r,int d) { if (l>r) return; if (tree[k].l==l&&tree[k].r==r) { tree[k].data=d*(tree[k].r-tree[k].l+1); tree[k].lazy=d; return; } spread(k); int mid=(tree[k].l+tree[k].r)/2; if (l<=mid&&r<=mid) { add(k*2,l,r,d); tree[k].data=tree[k*2].data+tree[k*2+1].data; return; } if (l>=mid+1&&r>=mid+1) { add(k*2+1,l,r,d); tree[k].data=tree[k*2].data+tree[k*2+1].data; return; } add(k*2,l,mid,d); add(k*2+1,mid+1,r,d); tree[k].data=tree[k*2].data+tree[k*2+1].data; return; } int sum(int k,int l,int r) { if (tree[k].l==l&&tree[k].r==r) return tree[k].data; spread(k); int mid=(tree[k].l+tree[k].r)/2; if (l<=mid&&r<=mid) return sum(k*2,l,r); if (l>=mid+1&&r>=mid+1) return sum(k*2+1,l,r); return sum(k*2,l,mid)+sum(k*2+1,mid+1,r); } bool msort(int S) { int res; for (int i=1;i<=n;++i) p[i]=(a[i]>=S); build(1,1,n); for (int i=1;i<=m;++i) { res=sum(1,q[i].l,q[i].r); if (q[i].op==0) { add(1,q[i].l,q[i].r-res,0); add(1,q[i].r-res+1,q[i].r,1); } else { add(1,q[i].l,q[i].l+res-1,1); add(1,q[i].l+res,q[i].r,0); } } return sum(1,Q,Q); } int main() { cin>>n>>m; for (int i=1;i<=n;++i) cin>>a[i]; for (int i=1;i<=m;++i) cin>>q[i].op>>q[i].l>>q[i].r; cin>>Q; int first=1,last=n,mid,ans=1; while (first<=last) { mid=(first+last)/2; if (msort(mid)) { ans=max(ans,mid); first=mid+1; } else last=mid-1; } cout<