题目链接

题目大意

给定n个数字的排列，m次询问。每次给定一个区间[l,r]使得其间的数字按照升序/降序排列。m次操作后求最中间的数字

解题思路

观察复杂度 硬做是不可以的。

考虑到K是一个小于10^6的数，我们不妨可以考虑对于答案进行验证，因此首先我想到模拟退火，但是实际上易得该函数是单峰函数，因此二分即可。

二分答案的过程中注意到N小于10^5可以考虑到使用O(nlogn)的算法进行解决。而此时整个数组可以分成两组，即大于答案的数和小于答案的数字。如此，我们可以把大于答案的设为1，小于答案的设为0。之后利用数据结构维护每一次询问的修改，从而根据每次中间值得到二分的左右边界。

数据结构的选择上起初选择珂朵莉树但是没有准备板子+不怎么理解，所以作罢。后来考虑到可以使用线段树进行区间赋值操作，因此决定现场写一个赋值线段树以维护之。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5+7;
int n,m;
int a[N*4],sum[N*4];
struct P{
    int add,mul,col;//三种懒标记
}tag[N*4];
void pushup(int x){
    sum[x]=sum[x<<1]+sum[x<<1|1];
}
void build(int x,int l,int r){
    if(l==r){
        sum[x]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pushup(x);
}
void pushdown(int x,int l,int r){
    int ls=x<<1,rs=x<<1|1,mid=(l+r)>>1;
    if(tag[x].col != -1){//有赋值标记
        tag[ls].add = tag[rs].add = 0;
        tag[ls].mul = tag[rs].mul = 1;
        sum[ls] = tag[x].col * (mid - l + 1);
        sum[rs] = tag[x].col * (r - mid );
        tag[ls].col = tag[rs].col = tag[x].col;
        tag[x].col = -1;
    }
    if(tag[x].mul != 1){ //有乘法标记
        int c = tag[x].mul;
        tag[ls].mul *= c;
        tag[rs].mul *= c;
        sum[ls] *= c;
        sum[rs] *= c;
        tag[ls].add *= c;
        tag[rs].add *= c;
        tag[x].mul = 1;
    }
    if(tag[x].add > 0){ //有加法标记
        int c = tag[x].add;
        tag[ls].add += c;
        tag[rs].add += c;
        sum[ls] += c * (mid - l + 1);
        sum[rs] += c * (r - mid);
        tag[x].add = 0;
    }
    return;
}
void updata_col(int x,int l,int r,int ll,int rr,int k){//赋值操作
    if(r<ll || l>rr) return;
    if(l>=ll && r<=rr){
        sum[x] = k * (r - l + 1);
        tag[x].mul = 1;
        tag[x].add = 0;
        tag[x].col = k;
        return;
    }
    pushdown(x,l,r);
    int mid=(l+r)>>1;
    updata_col(x<<1,l,mid,ll,rr,k);
    updata_col(x<<1|1,mid+1,r,ll,rr,k);
    pushup(x);
}

void updata_mul(int x,int l,int r,int ll,int rr,int k){//乘法操作
    if(r<ll || l>rr) return;
    if(l>=ll && r<=rr){
        sum[x]=sum[x]*k;
        tag[x].mul=tag[x].mul*k;
        tag[x].add=tag[x].add*k;
        return;
    }
    pushdown(x,l,r);
    int mid=(l+r)>>1;
    updata_mul(x<<1,l,mid,ll,rr,k);
    updata_mul(x<<1|1,mid+1,r,ll,rr,k);
    pushup(x);
}
void updata_add(int x,int l,int r,int ll,int rr,int k){//加法操作
    if(r<ll || l>rr) return;
    if(l>=ll && r<=rr){
        sum[x]=sum[x]+k*(r-l+1);
        tag[x].add=tag[x].add+k;
        return;
    }
    pushdown(x,l,r);
    int mid=(l+r)>>1;
    updata_add(x<<1,l,mid,ll,rr,k);
    updata_add(x<<1|1,mid+1,r,ll,rr,k);
    pushup(x);
}
int query(int x,int l,int r,int ll,int rr){//查询
    if(r<ll || l>rr) return 0;
    if(l>=ll && r<=rr){
        return sum[x];
    }
    pushdown(x,l,r);
    int mid=(l+r)>>1;
    return query(x<<1,l,mid,ll,rr)+query(x<<1|1,mid+1,r,ll,rr);
}

int b[N];
int s[N],t[N];
int sss;
int check(int x){
    for(int i=1;i<=4*n;i++) tag[i].mul=1;
    for(int i=1;i<=4*n;i++) tag[i].col=-1;
    for(int i=1;i<=n;i++){
        if(b[i]>=x){
            a[i]=1;
        }
        else{
            a[i]=0;
        }
    }
    build(1,1,n);
    for(int i=1;i<=m;i++){
        if(s[i]<t[i]){
            sss = query(1,1,n,s[i],t[i]);
            updata_col(1,1,n,t[i]-sss+1,t[i],1);
            updata_col(1,1,n,s[i],t[i]-sss,0);
        }
        else{
            sss = query(1,1,n,t[i],s[i]);
            updata_col(1,1,n,t[i],t[i]+sss-1,1);
            updata_col(1,1,n,t[i]+sss,s[i],0);
        }
    }
    int ans_=query(1,1,n,(1+n)/2,(1+n)/2);
    if(ans_) return 1;
    return 0;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    for(int i=1;i<=m;i++){
        cin>>s[i]>>t[i];
    }
    int l=1,r=n,mid,ans=0;
    while(l<=r){
        mid=l+r>>1;
        if(check(mid)){
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    cout<<ans<<endl;
    return 0;
}