有点想不到的trick
题目有两个操作，分别是对 \([l,r]\) 区间进行升序和降序排序，在最后询问某个位置 \(q\) 上的值是多少。
真的去对一个序列做排序会让复杂度很难看，但如果是给一个 \(01\) 序列排序是比较轻松的，记录一下 \(1\) 的个数，每次1操作就可以用两次区间覆盖来代替，又因为最终的询问只有一次，所以考虑这样一个做法：
二分一个答案 \(mid\) 并将原序列以 \(\geq mid\) 的值设为 \(1\) 其余设为 \(0\) 的方式变成 \(01\) 序列，并在操作完成后检查 \(q\) 上的值是不是 \(1\) 。
这个东西的单调性可以被满足是因为，如果当前 \(q\) 上的值大于 \(mid\)，那么 \(mid\) 取更大值时 \(q\) 也可能大于等于 \(mid\)。而小于 \(mid\) 则肯定不会再取到更大的值，最终二分到 \(q\) 位置上是 \(1\)，关系取等号的 \(mid\) 就是答案。
点击查看代码
using namespace std;
const int N=1e5+5;
int n,m,a[N],q;
int P=1,DEP;
struct {int opt,l,r;
}que[N];
struct {int sum,tag;bool chk;
}t[N*3];
ili void pushdown(int i,int siz){siz>>=1;if(t[i].chk){t[ls(i)].sum=siz*t[i].tag;t[rs(i)].sum=siz*t[i].tag;t[ls(i)].tag=t[i].tag;t[rs(i)].tag=t[i].tag;t[ls(i)].chk=1;t[rs(i)].chk=1;t[i].chk=0;}
}
ili void update(int l,int r,int v){l=l+P-1,r=r+P+1;int siz=1;for(int i=DEP;i;i--) pushdown(l>>i,1<<i),pushdown(r>>i,1<<i);while(l^1^r){if(~l&1){t[l^1].sum=siz*v,t[l^1].chk=1,t[l^1].tag=v;}if(r&1){t[r^1].sum=siz*v,t[r^1].chk=1,t[r^1].tag=v;}l>>=1,r>>=1,siz<<=1;t[l].sum=t[ls(l)].sum+t[rs(l)].sum;t[r].sum=t[ls(r)].sum+t[rs(r)].sum;}for(l>>=1;l;l>>=1) t[l].sum=t[ls(l)].sum+t[rs(l)].sum;
}
ili int query(int l,int r){l=l+P-1,r=r+P+1;int res=0;for(int i=DEP;i;i--) pushdown(l>>i,1<<i),pushdown(r>>i,1<<i);while(l^1^r){if(~l&1) res+=t[l^1].sum;if(r&1) res+=t[r^1].sum;l>>=1,r>>=1;}return res;
}
int check(int mid){for(int i=1;i<=n;i++){t[i+P].sum=(mid<=a[i]);t[i+P].chk=0;}for(int i=P-1;i;i--){t[i].chk=0;t[i].sum=t[ls(i)].sum+t[rs(i)].sum;}for(int i=1;i<=m;i++){int opt=que[i].opt,l=que[i].l,r=que[i].r;int sum=query(l,r);if(opt==0){sum=r-l+1-sum;//0的个数update(l,l+sum-1,0);update(l+sum,r,1);}else{update(l,l+sum-1,1);update(l+sum,r,0);}}return query(q,q);
}
void xpigeon(){rd(n,m);for(int i=1;i<=n;i++){rd(a[i]);}for(int i=1;i<=m;i++){rd(que[i].opt,que[i].l,que[i].r);}rd(q);while(P<=n+1) P<<=1,DEP++;int L=0,R=n+1;int ans=-1;while(R-L>1){int mid=(L+R)>>1;if(check(mid)){ans=mid;L=mid;}else{R=mid;}}cout<<ans<<'\n';
}