luogu2824 [HEOI2016]排序

记一道不错的二分

题目描述

在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排序分为两种：1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q位置上的数字。

输入输出格式

输入格式：
输入数据的第一行为两个整数n和m。n表示序列的长度，m表示局部排序的次数。1 <= n, m <= 10^5第二行为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
说明

河北省选2016第一天第二题。原题的时限为6s，但是洛谷上是1s，所以洛谷的数据中，对于30%的数据，有 n,m<=1000,对于100%的数据，有 n,m<=30000

思路：

一开始一直在想数据结构直接维护。但因为昨天刚做个比赛有道二分答案，立刻就想出来了。

因为是全排列，可以在1-n里面二分答案。找到答案以后就把原序列里面大于它的赋成1，小于的变成0。这样排序就可以用两个区间覆盖代替。总的效率$O(m \log^2 n)$

代码：

#include <cstdio>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define N 100010
using namespace std;
int inline read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,k,seg[N<<2],mark[N<<2],a[N],p[N][2],opt[N],ton[N];
void pushup(int rt)
{
    seg[rt]=seg[rt<<1]+seg[rt<<1|1];
}
void build(int rt,int l,int r,int x)
{
    seg[rt]=0,mark[rt]=-1;
    if (l==r)
    {
        if (a[l]>x)
            seg[rt]=1;
        return;
    }
    int mid=l+r>>1;
    build(lson,x);
    build(rson,x);
    pushup(rt);
}
void pushdown(int rt,int x)
{
    if (mark[rt]!=-1)
    {
        seg[rt<<1]=mark[rt]*(x-x/2);
        mark[rt<<1]=mark[rt];
        seg[rt<<1|1]=mark[rt]*(x/2);
        mark[rt<<1|1]=mark[rt];
        mark[rt]=-1;
    }
}
void update(int rt,int l,int r,int L,int R,int x)
{
    if (L>R) return;
    if (l>=L && r<=R)
        seg[rt]=x*(r-l+1),mark[rt]=x;
    else
    {
        pushdown(rt,r-l+1);
        int mid=l+r>>1;
        if (mid>=L)
            update(lson,L,R,x);
        if (mid<R)
            update(rson,L,R,x);
        pushup(rt);
    }
}
int query(int rt,int l,int r,int L,int R)
{
    if (L>R) return 0;
    if (l>=L && r<=R)
        return seg[rt];
    else
    {
        pushdown(rt,r-l+1);
        int mid=l+r>>1,ans=0;
        if (mid>=L)
            ans+=query(lson,L,R);
        if (mid<R)
            ans+=query(rson,L,R);
        return ans;
    }
}
main()
{
    n=read(),m=read();
    for (int i=1;i<=n;i++)
        a[i]=read(),ton[a[i]]=i;
    for (int i=1;i<=m;i++)
        opt[i]=read(),p[i][0]=read(),p[i][1]=read();
    scanf("%d",&k);
    int l=1,r=n;
    while(l<=r)
    {
        int mid=l+r>>1;
        int now=mid;
        build(1,1,n,now);
        int pos=mid;
        for (int i=1;i<=m;i++)
            if (!opt[i])
            {
                int cnt=query(1,1,n,p[i][0],p[i][1]);
                update(1,1,n,p[i][0],p[i][1],0);
                update(1,1,n,p[i][1]-cnt+1,p[i][1],1);
                if (p[i][0]<=pos && p[i][1]>=pos)
                    pos=p[i][1]-cnt;
            }
            else
            {
                int cnt=query(1,1,n,p[i][0],p[i][1]);
                update(1,1,n,p[i][0],p[i][1],0);
                update(1,1,n,p[i][0],p[i][0]+cnt-1,1);
                if (p[i][0]<=pos && p[i][1]>=pos)
                    pos=p[i][0]+cnt;
            }
        if (pos==k)
        {
            printf("%d\n",mid);
            return 0;
        }
        int p=query(1,1,n,k,k);
        if (p)
            l=mid+1;
        else
            r=mid-1;
    }
    printf("%d\n",l);
}