bzoj 4552[Tjoi2016&Heoi2016]排序 题解【二分答案】【线段树】

点击量：179

   特别新颖的思路？

目录

题目描述

在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排序分为两种：

 

1:(0,l,r)表示将区间[l,r]的数字升序排序

 

2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q位置上的数字。

 

输入输出格式

输入格式：

输入数据的第一行为两个整数n和m。n表示序列的长度，m表示局部排序的次数。第二行为n个整数，表示1到n的一个全排列。接下来输入m行，每一行有三个整数op,l,r,op为0代表升序排序，op为1代表降序排序, l,r表示排序的区间。最后输入一个整数q，q表示排序完之后询问的位置, 1<=q<=n。1<=n<=10^5，1<=m<=10^5。

 

输出格式：

输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第q位置上的数字。

 

输入输出样例

输入样例#1：

6 3

1 6 2 5 3 4

0 1 4

1 3 6

0 2 4

3

输出样例#1：

5

题解：

   这样的题很难想到二分答案吧，不过感觉上至少要维护一棵线段树。

   这道题的方法就是二分答案，因为给出了1~n的一个排列，所以我们可以二分q位置上的数是多少(设为x)。此时对于排序我们只关心一个数是大于x还是小于x，因为我们只需要检验当前位置上的数是否是x就可以了。

   对于大于x的数，把它在线段树在中的值置为1，对于小于等于x的数，把它在线段树中的值置为0。这样在区间排序时，我们只管排0/1，也就是先查询区间中有多少个1(假设为y)，然后把区间置0，如果是升序，就把最右边y个置为1，否则把最左边y个置1。要特别注意的一点是，当区间没有1时，继续无脑修改会出问题，也就是出现r<l的情况，这里要特判。

  因为我们在上述过程中对0和1排序了，所以我们就知道第i位是0还是1了，如果第i位是1，说明下界，也就是当前的检验值大了，把q号位的数值也变成了1；如果第i位是0，则可能就是检验值，把上界控制在这里。

Code：

#include<cstdio>
#include<cstring>
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define Mid (t[k].l+t[k].r>>1)
struct node//线段树维护区间覆盖型修改
{
    int l,r,v,lazy;
    node(int l,int r,int v)
    {
        this->l=l;
        this->r=r;
        this->v=v;
        lazy=-1;
    }
    node(int l,int r)
    {
        this->l=l;
        this->r=r;
        v=0;
        lazy=-1;
    }
    node()
    {
        v=0,lazy-1;
    }
}t[410000];
int a[101000],h[101000];//a是01关系，h是原数组
void build(int k,int l,int r)
{
    if(l==r)
    {
        t[k]=node(l,r,a[l]);
        return;
    }
    t[k]=node(l,r);
    build(ls,l,mid);
    build(rs,mid+1,r);
    t[k].v=t[ls].v+t[rs].v;
}
void pushdown(int k)
{
    int x=t[k].lazy;
    if(x==-1)
        return;
    t[ls].v=(t[ls].r-t[ls].l+1)*x;
    t[rs].v=(t[rs].r-t[rs].l+1)*x;
    t[ls].lazy=x;
    t[rs].lazy=x;
    t[k].lazy=-1;
    return;
}
void change(int k,int l,int r,int x)//把l到r的区间改为x
{
    if(l==t[k].l&&r==t[k].r)
    {
        t[k].v=(r-l+1)*x;
        t[k].lazy=x;
        return;
    }
    pushdown(k);
    if(r<=Mid)
        change(ls,l,r,x);
    else if(l>Mid)
        change(rs,l,r,x);
    else
    {
        change(ls,l,Mid,x);
        change(rs,Mid+1,r,x);
    }
    t[k].v=t[ls].v+t[rs].v;
    return;
}
int ask(int k,int l,int r)
{
    if(t[k].l==l&&t[k].r==r)
        return t[k].v;
    pushdown(k);
    if(r<=Mid)
        return ask(ls,l,r);
    else if(l>Mid)
        return ask(rs,l,r);
    else
        return ask(ls,l,Mid)+ask(rs,Mid+1,r);
}
int op[101000],from[101000],to[101000],n,m,q;
bool check(int x)
{
    for(int i=1;i<=n;i++)
        if(h[i]>x)
            a[i]=1;
        else
            a[i]=0;
    build(1,1,n);
    for(int i=1;i<=m;i++)
        if(op[i]==0)//升序
        {
            int tmp=ask(1,from[i],to[i]);
            change(1,from[i],to[i],0);
            if(tmp>0)
                change(1,to[i]-tmp+1,to[i],1);
        }
        else
        {
            int tmp=ask(1,from[i],to[i]);
            change(1,from[i],to[i],0);
            if(tmp>0)
                change(1,from[i],from[i]+tmp-1,1);
        }
    return ask(1,q,q);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&h[i]);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&op[i],&from[i],&to[i]);
    scanf("%d",&q);
    int L=1,R=n,mId;
    while(L<R)
    {
        mId=(L+R>>1);
        if(check(mId))//小于等于mId的数置为0
            L=mId+1;
        else
            R=mId;
    }
    printf("%d\n",L);
    return 0;
}