bzoj4552 [Tjoi2016&Heoi2016]排序 線段樹+二分答案

Description

在2016年，佳媛姐姐喜歡上了數字序列。因而他經常研究關于序列的一些奇奇怪怪的問題，現在他在研究一個難題

，需要你來幫助他。這個難題是這樣子的：給出一個1到n的全排列，現在對這個全排列序列進行m次局部排序，排

序分為兩種：1:(0,l,r)表示将區間[l,r]的數字升序排序2:(1,l,r)表示将區間[l,r]的數字降序排序最後詢問第q

位置上的數字。

1 <= n, m <= 10^5

Solution

可以二分一個答案，然後把數字分成大于mid和小于mid的兩部分，這樣就能用線段樹區間維護排序操作了

感謝loj的資料

Code

#include <stdio.h>
#include <string.h>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define fill(x,t) memset(x,t,sizeof(x))
const int N=;
int lazy[N<<],c[N<<];
int opt[N][],a[N];
int n,m,pos;
int read() {
    int x=,v=; char ch=getchar();
    for (;ch<'0'||ch>'9';v=(ch=='-')?(-):(v),ch=getchar());
    for (;ch<='9'&&ch>='0';x=x*+ch-'0',ch=getchar());
    return x*v;
}
void push_down(int now,int tl,int tr) {
    if (lazy[now]==-) return ;
    int mid=(tl+tr)>>;
    lazy[now<<]=lazy[now<<|]=lazy[now];
    c[now<<]=(mid-tl+)*lazy[now];
    c[now<<|]=(tr-mid)*lazy[now];
    lazy[now]=-;
}
void modify(int now,int tl,int tr,int l,int r,int v) {
    if (l>r) return ;
    if (tl==l&&tr==r) {
        lazy[now]=v;
        c[now]=(r-l+)*v;
        return ;
    }
    push_down(now,tl,tr);
    int mid=(tl+tr)>>;
    if (r<=mid) modify(now<<,tl,mid,l,r,v);
    else if (l>mid) modify(now<<|,mid+,tr,l,r,v);
    else {
        modify(now<<,tl,mid,l,mid,v);
        modify(now<<|,mid+,tr,mid+,r,v);
    }
    c[now]=c[now<<]+c[now<<|];
}
int query(int now,int tl,int tr,int l,int r) {
    if (tl==l&&tr==r) return c[now];
    push_down(now,tl,tr);
    int mid=(tl+tr)>>;
    if (r<=mid) return query(now<<,tl,mid,l,r);
    else if (l>mid) return query(now<<|,mid+,tr,l,r);
    else return query(now<<,tl,mid,l,mid)+query(now<<|,mid+,tr,mid+,r);
}
int solve(int now) {
    fill(c,);
    fill(lazy,-);
    rep(i,,n) modify(,,n,i,i,a[i]>=now);
    rep(i,,m) {
        int ret=query(,,n,opt[i][],opt[i][]);
        if (opt[i][]==) {
            modify(,,n,opt[i][],opt[i][]-ret,);
            modify(,,n,opt[i][]-ret+,opt[i][],);
//          printf("%d %d %d %d\n",opt[i][1],opt[i][2]-ret,opt[i][2]-ret+1,opt[i][2]);
        } else {
            modify(,,n,opt[i][],opt[i][]+ret-,);
            modify(,,n,opt[i][]+ret,opt[i][],);
//          printf("%d %d %d %d\n",opt[i][1],opt[i][1]+ret-1,opt[i][1]+ret,opt[i][2]);
        }
    }
    return query(,,n,pos,pos);
}
int main(void) {
    n=read(); m=read();
    rep(i,,n) a[i]=read();
    rep(i,,m) opt[i][]=read(),opt[i][]=read(),opt[i][]=read();
    pos=read();
    int ans=;
    int l=,r=n;
    while (l<=r) {
        int mid=(l+r)>>;
        if (solve(mid)) l=mid+,ans=mid;
        else r=mid-;
    }
    printf("%d\n", ans);
    return ;
}