[bzoj 4552] [Tjoi 2016] [Heoi 2016] [정렬] [이분 정 답] [선분 트 리]

제목 의 대의
길이 가 n 인 서열 을 제시 합 니 다. m 개의 정렬 작업 이 있 습 니 다. 한 구간 의 오름차 나 내림차 순 서 를 정렬 하여 특정한 값 을 다 조작 하 십시오.
해제
매우 뚜렷 하지 않 은 성질 로 본 제 는 이분 성 을 만족시킨다.2 분 의 1 의 답 은 원수 가 크 거나 같 으 면 1 로 표시 하고 그렇지 않 으 면 0 으로 표시 한다.정렬 을 마치 면 목표 위치 가 답 보다 큰 지 작은 지 알 수 있 고 답 을 적당 하 게 조정 하면 된다.
code

#include
#include
#include
#include
#include
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
int const maxn=100000;
int n,m,q,a[maxn+10],l[maxn+10],r[maxn+10],op[maxn+10],ans[maxn*50+10],flag[maxn*50+10];
void change(int now,int l,int r,int l1,int r1,int val){
    if(l1>r1)return;
    int m=(l+r)/2;
    if((flag[now]!=-1)&&(l!=r)){
        ans[now*2]=(m-l+1)*flag[now];
        ans[now*2+1]=(r-m)*flag[now];
        flag[now*2]=flag[now*2+1]=flag[now];
        flag[now]=-1;
    }
    if((l==l1)&&(r==r1)){
        ans[now]=(r-l+1)*val;
        flag[now]=val;
        return;
    }else if(r1<=m)change(now*2,l,m,l1,r1,val);
    else if(m*2+1,m+1,r,l1,r1,val);
    else{
        change(now*2,l,m,l1,m,val);
        change(now*2+1,m+1,r,m+1,r1,val);
    }
    ans[now]=ans[now*2]+ans[now*2+1];
}
int ask(int now,int l,int r,int l1,int r1){
    if(l1>r1)return 0;
    int m=(l+r)/2;
    if((flag[now]!=-1)&&(l!=r)){
        ans[now*2]=(m-l+1)*flag[now];
        ans[now*2+1]=(r-m)*flag[now];
        flag[now*2]=flag[now*2+1]=flag[now];
        flag[now]=-1;
    }
    if((l==l1)&&(r==r1))return ans[now];
    else if(r1<=m)return ask(now*2,l,m,l1,r1);
    else if(mreturn ask(now*2+1,m+1,r,l1,r1);
    else return ask(now*2,l,m,l1,m)+ask(now*2+1,m+1,r,m+1,r1);
}
int main(){
    //freopen("len.in","r",stdin);
    //freopen("len.out","w",stdout);
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    scanf("%d%d",&n,&m);
    fo(i,1,n)scanf("%d",&a[i]);
    fo(i,1,m)
        scanf("%d%d%d",&op[i],&l[i],&r[i]);
    scanf("%d",&q);
    int le=1,ri=n;
    memset(flag,255,sizeof(flag));
    while(le!=ri){
        int mid=(le+ri+1)/2;
        fo(i,1,n)
            change(1,1,n,i,i,a[i]>=mid);
        fo(i,1,m){
            int tmp=ask(1,1,n,l[i],r[i]);
            if(op[i]){
                change(1,1,n,l[i],l[i]+tmp-1,1);
                change(1,1,n,l[i]+tmp,r[i],0);
            }else{
                change(1,1,n,l[i],r[i]-tmp,0);
                change(1,1,n,r[i]-tmp+1,r[i],1);
            }
        }
        if(ask(1,1,n,q,q))le=mid;
        else ri=mid-1;
    }
    printf("%d",le);
    return 0;
}