P2824 [HEOI2016/TJOI2016]排序

题意：

有一个长度为\(n\)的1-n的排列\(m\)次操作

\((0,l,r)\)表示序列从\(l\)到\(r\)降序

\((1,l,r)\)表示序列从\(l\)到\(r\)升序

问最终第\(q\)位的元素

数据范围：

\(n,m<=1e5\)

二分答案神题。

我们发现维护区间排序非常困难，然后最终只是若干修改一次询问。

所以我们可以枚举第\(q\)位的是什么，然后把小于等于它的置0，大于它的置0。

这样的话，我们就可以用支持区间查询和区间覆盖的线段树维护升降序了

进一步的，我们发现第q位的数字满足单调性，于是二分答案

复杂度：\(O(nlog^2n)\)

Code:

#include <cstdio>

#define ls id<<1

#define rs id<<1|1

const int N=30010;

int dat[N<<2],lazy[N<<2],m,n,op[N],opr[N],opl[N],a[N],q;

void build(int id,int l,int r,int M)

{

    lazy[id]=-1;

    if(l==r)

    {

        dat[id]=(M<a[l]);

        return;

    }

    int mid=l+r>>1;

    build(ls,l,mid,M);

    build(rs,mid+1,r,M);

    dat[id]=dat[ls]+dat[rs];

}

void push_down(int id,int L,int R)

{

    if(lazy[id]==-1) return;

    if(L!=R)

    {

        int mid=L+R>>1;

        dat[ls]=(mid+1-L)*lazy[id];

        dat[rs]=(R-mid)*lazy[id];

        lazy[ls]=lazy[rs]=lazy[id];

    }

    lazy[id]=-1;

}

void change(int id,int L,int R,int l,int r,int delta)

{

    if(l>r) return;

    push_down(id,L,R);

    if(L==l&&R==r)

    {

        dat[id]=(r+1-l)*delta;

        lazy[id]=delta;

        return;

    }

    int mid=L+R>>1;

    if(r<=mid)

        change(ls,L,mid,l,r,delta);

    else if(l>mid)

        change(rs,mid+1,R,l,r,delta);

    else

        change(ls,L,mid,l,mid,delta),change(rs,mid+1,R,mid+1,r,delta);

    dat[id]=dat[ls]+dat[rs];

}

int query(int id,int L,int R,int l,int r)

{

    push_down(id,L,R);

    if(L==l&&R==r)

        return dat[id];

    int mid=L+R>>1;

    if(r<=mid)

        return query(ls,L,mid,l,r);

    else if(l>mid)

        return query(rs,mid+1,R,l,r);

    else

        return query(ls,L,mid,l,mid)+query(rs,mid+1,R,mid+1,r);

}

bool check(int d)

{

    build(1,1,n,d);

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

    {

        int cn1=query(1,1,n,opl[i],opr[i]);

        int cn0=opr[i]+1-opl[i]-cn1;

        if(op[i]==0)

        {

            change(1,1,n,opl[i],opl[i]+cn0-1,0);

            change(1,1,n,opl[i]+cn0,opr[i],1);

        }

        else

        {

            change(1,1,n,opl[i],opl[i]+cn1-1,1);

            change(1,1,n,opl[i]+cn1,opr[i],0);

        }

    }

    return query(1,1,n,q,q);

}

int main()

{

    scanf("%d%d",&n,&m);

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

        scanf("%d",a+i);

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

        scanf("%d%d%d",op+i,opl+i,opr+i);

    scanf("%d",&q);

    int l=1,r=n;

    while(l<r)

    {

        int mid=l+r>>1;

        if(check(mid))

            l=mid+1;

        else

            r=mid;

    }

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

    return 0;

}

2018.7.19

巴特西

洛谷 P2824 [HEOI2016/TJOI2016]排序解题报告

P2824 [HEOI2016/TJOI2016]排序

题意：

数据范围：

最新文章

热门文章

巴特西

洛谷 P2824 [HEOI2016/TJOI2016]排序 解题报告

P2824 [HEOI2016/TJOI2016]排序

题意：

数据范围：

最新文章

热门文章

洛谷 P2824 [HEOI2016/TJOI2016]排序解题报告