又是久违的1A哇...
好喵喵的题！二分a[p]，把大于mid的数改为1，小于等于mid的数改为0，变成01串后就可以用线段树进行那一连串排序了，排序后如果p的位置上的数为0，说明答案比mid小，如果为1，说明答案比mid大。
如何理解呢？我们的目的其实是让比a[p]大的数都为1，这样子p位置上刚好为0。如果p位置上为1，说明mid较小，a[p]>mid，把a[p]给标记成了1。如果p位置上为0，就是把a[p]<=mid，把a[p]标记成了0，但是这样还有一些大于a[p]的位置也是0，所以继续往小的地方逼近答案。
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int maxn=500010,inf=1e9; struct poi{int sum,tag;}tree[maxn]; int n,m,q; int a[maxn],b[maxn],l[maxn],r[maxn],ty[maxn]; inline void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } inline void pushup(int x){tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;} inline void pushdown(int x,int l,int r) { if(tree[x].tag==-1)return; int mid=(l+r)>>1; if(tree[x].tag==1) { tree[x<<1].sum=mid-l+1;tree[x<<1].tag=1; tree[x<<1|1].sum=r-mid;tree[x<<1|1].tag=1; } else tree[x<<1].sum=tree[x<<1|1].sum=tree[x<<1].tag=tree[x<<1|1].tag=0; tree[x].tag=-1; } void build(int x,int l,int r) { tree[x].tag=-1; if(l==r){tree[x].sum=b[l];return;} int mid=(l+r)>>1; build(x<<1,l,mid);build(x<<1|1,mid+1,r); pushup(x); } void update(int x,int l,int r,int cl,int cr,int ty) { if(cl<=l&&r<=cr){tree[x].sum=ty*(r-l+1);tree[x].tag=ty;return;} pushdown(x,l,r); int mid=(l+r)>>1; if(cl<=mid)update(x<<1,l,mid,cl,cr,ty); if(cr>mid)update(x<<1|1,mid+1,r,cl,cr,ty); pushup(x); } int query(int x,int l,int r,int cl,int cr) { if(cl<=l&&r<=cr)return tree[x].sum; pushdown(x,l,r); int mid=(l+r)>>1,ret=0; if(cl<=mid)ret+=query(x<<1,l,mid,cl,cr); if(cr>mid)ret+=query(x<<1|1,mid+1,r,cl,cr); return ret; } bool check(int x) { for(int i=1;i<=n;i++)b[i]=a[i]>x; build(1,1,n); for(int i=1;i<=m;i++) { int x=query(1,1,n,l[i],r[i]); if(ty[i]) { if(x)update(1,1,n,l[i],l[i]+x-1,1); if(l[i]+x<=r[i])update(1,1,n,l[i]+x,r[i],0); } else { if(l[i]<=r[i]-x)update(1,1,n,l[i],r[i]-x,0); if(x)update(1,1,n,r[i]-x+1,r[i],1); } } return !query(1,1,n,q,q); } int main() { read(n);read(m); for(int i=1;i<=n;i++)read(a[i]); for(int i=1;i<=m;i++)read(ty[i]),read(l[i]),read(r[i]); read(q); int l=1,r=n; while(l<r) { int mid=(l+r)>>1; if(check(mid))r=mid; else l=mid+1; } printf("%d",l); }