BZOJ4552 - [TJOI2016]排序

Description

给出一个\(1..n(n\leq10^5)\)的排列，进行\(m(m\leq10^5)\)次操作：

升序排列\([L,R]\)中的数。
降序排列\([L,R]\)中的数。

所有操作完成后，求位置\(q\)上的值。

Solution

居然是二分答案...！

对于可能的答案\(x\)，将所有小于\(x\)的数视为\(0\)，大于等于\(x\)的数视为\(1\)。那么每次排序就能利用线段树在\(O(logn)\)的时间内处理（区间赋值\(0/1\)）。操作完成后，如果位置\(q\)上的数为\(0\)，则说明真正的答案\(ans<x\)；否则说明\(ans\geq x\)。

时间复杂度\(O(mlog^2n)\)。

Code

//排序

#include <algorithm>

#include <cstdio>

#include <cstring>

using std::sort;

inline char gc()

{

    static char now[1<<16],*s,*t;

    if(s==t) {t=(s=now)+fread(now,1,1<<16,stdin); if(s==t) return EOF;}

    return *s++;

}

inline int read()

{

    int x=0; char ch=gc();

    while(ch<'0'||'9'<ch) ch=gc();

    while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=gc();

    return x;

}

int const N=1e5+10;

int n,m,Q,a[N];

struct rQuery{int opt,L,R;} q[N];

#define Ls (p<<1)

#define Rs ((p<<1)|1)

int rt; int sum[N<<2],tag[N<<2];

void update(int p) {sum[p]=sum[Ls]+sum[Rs];}

void change(int p,int L0,int R0,int x) {sum[p]=x*(R0-L0+1),tag[p]=x;}

void pushdw(int p,int L0,int R0)

{

    if(tag[p]<0) return;

    int mid=L0+R0>>1;

    change(Ls,L0,mid,tag[p]);

    change(Rs,mid+1,R0,tag[p]);

    tag[p]=-1;

}

int L,R;

void ins(int p,int L0,int R0,int x)

{

    if(L<=L0&&R0<=R) {change(p,L0,R0,x); return;}

    pushdw(p,L0,R0);

    int mid=L0+R0>>1;

    if(L<=mid) ins(Ls,L0,mid,x);

    if(mid<R) ins(Rs,mid+1,R0,x);

    update(p);

}

int query(int p,int L0,int R0)

{

    if(L<=L0&&R0<=R) return sum[p];

    pushdw(p,L0,R0);

    int mid=L0+R0>>1,res=0;

    if(L<=mid) res+=query(Ls,L0,mid);

    if(mid<R) res+=query(Rs,mid+1,R0);

    return res;

}

bool check(int x)

{

    memset(sum,0,sizeof sum);

    memset(tag,-1,sizeof tag);

    for(int i=1;i<=n;i++) L=R=i,ins(rt,1,n,a[i]>=x);

    for(int i=1;i<=m;i++)

    {

        int opt=q[i].opt;

        L=q[i].L,R=q[i].R; int cnt=query(rt,1,n);

        if(opt==0) cnt=q[i].R-q[i].L+1-cnt;

        L=q[i].L,R=L+cnt-1; if(L<=R) ins(rt,1,n,opt);

        L=q[i].L+cnt,R=q[i].R; if(L<=R) ins(rt,1,n,opt^1);

    }

    L=R=Q; return query(rt,1,n);

}

int main()

{

    n=read(),m=read();

    for(int i=1;i<=n;i++) a[i]=read();

    for(int i=1;i<=m;i++) q[i].opt=read(),q[i].L=read(),q[i].R=read();

    Q=read();

    rt=1;

    int left=2,right=n;

    while(left<=right)

    {

        int mid=left+right>>1;

        if(check(mid)) left=mid+1;

        else right=mid-1;

    }

    printf("%d\n",right);

    return 0;

}

P.S.

苦恼于找不到一个美妙的线段树写法...

巴特西

BZOJ4552 - [TJOI2016]排序

Description

Solution

Code

P.S.

最新文章

热门文章