正解:线段树+二分
解题报告:
昂着题好神噢我$jio$得$QwQQQQQ$,,,
开始看到长得很像之前考试题的亚子,,,然后仔细康康发现不一样昂$kk$,就这里范围是$[1,n]$,而且每个数字只出现了一次,显然就不能用线段树维护每个数字的出现次数了$QAQ$
考虑先二分这个位置上的数字,然后把所有大于这个数字的赋值为1其他赋值为0,然后就直接按01排序,最后$check$这个位置是0还是1就成$QwQ$
$over$
#include<bits/stdc++.h> using namespace std; #define il inline #define gc getchar() #define ri register int #define rc register char #define rb register bool #define rp(i,x,y) for(ri i=x;i<=y;++i) #define my(i,x,y) for(ri i=x;i>=y;--i) const int N=1e5+10,inf=1e9; int n,m,q,a[N],st[N],l=inf,r,tr[N<<2],tag[N<<2],as; struct node{int op,l,r;}nod[N]; il int read() { rc ch=gc;ri x=0;rb y=1; while(ch!='-' && (ch>'9' || ch<'0'))ch=gc; if(ch=='-')ch=gc,y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc; return y?x:-x; } void build(ri nw,ri l,ri r) { if(l==r)return void(tr[nw]=st[l]); ri mid=(l+r)>>1;build(nw<<1,l,mid);build(nw<<1|1,mid+1,r);tr[nw]=tr[nw<<1]+tr[nw<<1|1]; } void pushdown(ri x,ri l,ri r) { if(tag[x]==-1)return; ri mid=(l+r)>>1;tr[x<<1]=tag[x]*(mid-l+1);tr[x<<1|1]=tag[x]*(r-mid);tag[x<<1]=tag[x<<1|1]=tag[x];tag[x]=-1; } int query(ri nw,ri l,ri r,ri to_l,ri to_r) { if(to_l<=l && r<=to_r)return tr[nw]; ri mid=(l+r)>>1,ret=0;pushdown(nw,l,r); if(mid>=to_l)ret+=query(nw<<1,l,mid,to_l,to_r); if(mid<to_r)ret+=query(nw<<1|1,mid+1,r,to_l,to_r); tr[nw]=tr[nw<<1]+tr[nw<<1|1]; return ret; } void modify(ri nw,ri l,ri r,ri to_l,ri to_r,ri dat) { if(to_l>to_r)return; if(to_l<=l && r<=to_r){tag[nw]=dat,tr[nw]=dat*(r-l+1);return;} ri mid=(l+r)>>1;pushdown(nw,l,r); if(mid>=to_l)modify(nw<<1,l,mid,to_l,to_r,dat); if(mid<to_r)modify(nw<<1|1,mid+1,r,to_l,to_r,dat); tr[nw]=tr[nw<<1]+tr[nw<<1|1]; } il bool check(ri d) { rp(i,1,n)st[i]=a[i]>=d; build(1,1,n);memset(tag,-1,sizeof(tag)); rp(i,1,m) { ri dat=query(1,1,n,nod[i].l,nod[i].r); if(nod[i].op){modify(1,1,n,nod[i].l,nod[i].l+dat-1,1);modify(1,1,n,nod[i].l+dat,nod[i].r,0);} else{modify(1,1,n,nod[i].r-dat+1,nod[i].r,1);modify(1,1,n,nod[i].l,nod[i].r-dat,0);} } return query(1,1,n,q,q); } int main() { l=1;r=n=read();m=read();memset(tag,-1,sizeof(tag)); rp(i,1,n)a[i]=read();rp(i,1,m)nod[i]=(node){read(),read(),read()};q=read(); while(l<=r){ri mid=(l+r)>>1;if(check(mid))l=mid+1,as=mid;else r=mid-1;}printf("%d ",as); return 0; }