记录编号	616831	评测结果	AAAAAAAAAA
题目名称	2276.[HEOI 2016] 排序	最终得分	100
用户昵称	exil	是否通过	通过
代码语言	C++	运行时间	7.253 s
提交时间	2026-07-01 10:16:08	内存使用	11.05 MiB

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int xu[100005];
int lie[100005];
struct node{
    int sum1;
    int sum0;
    int l;
    int r;
    int lan;
};
node tree[600005];
void jianshu(int k,int l,int r){
    tree[k]={0,0,l,r,0};
    if(l==r){
        if(lie[l]==1)tree[k].sum1=1,tree[k].sum0=0;
        else tree[k].sum0=1,tree[k].sum1=0;
        return;
    }
    int mid=(l+r)/2;
    jianshu(k<<1,l,mid);
    jianshu(k<<1|1,mid+1,r);
    tree[k].sum1=tree[k<<1].sum1+tree[k<<1|1].sum1;
    tree[k].sum0=tree[k<<1].sum0+tree[k<<1|1].sum0;
}
vector<int> v[100005];
void pushdown(int x){
    if(tree[x].lan==0)return;
    tree[x<<1].lan=tree[x].lan;
    tree[x<<1|1].lan=tree[x].lan;
    if(tree[x].lan==1){
        tree[x<<1].sum1=tree[x<<1].r-tree[x<<1].l+1;
        tree[x<<1].sum0=0;
        tree[x<<1|1].sum1=tree[x<<1|1].r-tree[x<<1|1].l+1;
        tree[x<<1|1].sum0=0;
    }
    else{
        tree[x<<1].sum0=tree[x<<1].r-tree[x<<1].l+1;
        tree[x<<1].sum1=0;
        tree[x<<1|1].sum0=tree[x<<1|1].r-tree[x<<1|1].l+1;
        tree[x<<1|1].sum1=0;
    }
    tree[x].lan=0;
}
void add(int k,int l,int r,int v){
    if(tree[k].l>r || tree[k].r<l)return;
    pushdown(k);
    if(tree[k].l>=l && tree[k].r<=r){
        if(v==1){
            tree[k].sum1=tree[k].r-tree[k].l+1;
            tree[k].sum0=0;
            tree[k].lan=1;
            return;
        }
        else{
            tree[k].sum0=tree[k].r-tree[k].l+1;
            tree[k].sum1=0;
            tree[k].lan=2;
            return;
        }
    }
    add(k<<1,l,r,v);
    add(k<<1|1,l,r,v);
    tree[k].sum1=tree[k<<1].sum1+tree[k<<1|1].sum1;
    tree[k].sum0=tree[k<<1].sum0+tree[k<<1|1].sum0;
}
int cha(int k,int l,int r,int v){
    if(tree[k].l>r || tree[k].r<l)return 0;
    pushdown(k);
    if(tree[k].l>=l && tree[k].r<=r){
        if(v==1)return tree[k].sum1;
        else return tree[k].sum0;
    }
    return cha(k<<1,l,r,v)+cha(k<<1|1,l,r,v);
}
signed main(){
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        cin>>xu[i];
    }
    for(int i = 1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        v[i].push_back(a),v[i].push_back(b),v[i].push_back(c);
    }
    int l=1,r=n;
    int ans=0;
    int q;
    cin>>q;
    while(l<=r){
        int mid=(l+r)/2;
        for(int i = 1;i<=n;i++){
            if(xu[i]>=mid)lie[i]=1;
            else lie[i]=0;
        }
        jianshu(1,1,n);
        for(int i = 1;i<=m;i++){
            if(v[i][0]==0){
                int l=v[i][1],r=v[i][2];
                int shu0=cha(1,l,r,0);
                add(1,l,shu0+l-1,0);
                add(1,shu0+l,r,1);
            }
            else{
                int l=v[i][1],r=v[i][2];
                int shu1=cha(1,l,r,1);
                add(1,l,shu1+l-1,1);
                add(1,l+shu1,r,0);
            }
        }
        if(cha(1,q,q,1)==1){
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
        
    }
    cout<<ans;
    return 0;
}