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

作者: wjyyy 分类: 二分,线段树,解题报告 发布时间: 2018-07-19 19:08

点击量:30

 

   特别新颖的思路?

 

题目描述

在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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */