洛谷2824 [HEOI2016/TJOI2016]排序

题意

给出一个 $1..n(\le 10^5)$ 的全排列，有 $m(\le 10^5)$ 次操作，每次把 $[l,r]$ 中的数升序或降序排列。最后询问第 $q$ 个数是多少。

题解

只有最后一次询问，所以可以把操作离线处理。

先考虑对一个 $0/1$ 串进行操作。升序排序就是把所有的 $1$ 挪到后面，降序就是挪到前面，可以用线段树解决。

可以二分答案 $mid$ ，然后将 $< mid$ 的数改成 $0$ ，$\geq mid$ 的数改成 $1$ 进行操作。最后第 $q$ 个数必须要 $\geq mid$ ，即为 $1$ ，才可能满足答案，所以满足单调性。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=100005;
struct Tree {
    int left,right,sum,delta;
} tree[N<<2];
struct node {
    int a,b,c;
} q[N];
bool w[N];
int n,m,k,a,b,c,s[N];

inline void pushup(int x) { tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum; }

inline void pushdown(int x)
{
    tree[x<<1].sum=tree[x].delta*(tree[x<<1].right-tree[x<<1].left);
    tree[x<<1|1].sum=tree[x].delta*(tree[x<<1|1].right-tree[x<<1|1].left);
    tree[x<<1].delta=tree[x<<1|1].delta=tree[x].delta;
    tree[x].delta=-1;
}

void build(int x,int l,int r)
{
    tree[x].left=l;
    tree[x].right=r;
    tree[x].delta=-1;
    if (r-l==1) tree[x].sum=w[l];
    else
    {
        int mid=(l+r)>>1;
        build(x<<1,l,mid);
        build(x<<1|1,mid,r);
        pushup(x);
    }
}

void update(int x,int l,int r,int delta)
{
    if (l==r) return;
    if (l<=tree[x].left && r>=tree[x].right)
    {
        tree[x].sum=delta*(tree[x].right-tree[x].left);
        tree[x].delta=delta;
    }
    else
    {
        if (tree[x].delta!=-1) pushdown(x);
        int mid=(tree[x].left+tree[x].right)>>1;
        if (l<mid) update(x<<1,l,r,delta);
        if (r>mid) update(x<<1|1,l,r,delta);
        pushup(x);
    }
}

int query(int x,int l,int r)
{
    if (l<=tree[x].left && r>=tree[x].right) return tree[x].sum;
    else
    {
        if (tree[x].delta!=-1) pushdown(x);
        int mid=(tree[x].left+tree[x].right)>>1,ans=0;
        if (l<mid) ans+=query(x<<1,l,r);
        if (r>mid) ans+=query(x<<1|1,l,r);
        return ans;
    }
}

inline bool check(int mid)
{
    for (int i=1;i<=n;i++) w[i]=s[i]>=mid;
    build(1,1,n+1);
    for (int i=1;i<=m;i++)
    {
        int cur=query(1,q[i].b,q[i].c+1); //1 的个数
        if (q[i].a)
        {
            update(1,q[i].b,q[i].b+cur,1); //把 1 挪到前面
            update(1,q[i].b+cur,q[i].c+1,0);
        }
        else
        {
            update(1,q[i].b,q[i].c+1-cur,0);
            update(1,q[i].c+1-cur,q[i].c+1,1);
        }
    }
    return query(1,k,k+1);
}

signed main()
{
    n=read(); m=read();
    int mx=0;
    for (int i=1;i<=n;i++) s[i]=read();
    for (int i=1;i<=m;i++) q[i].a=read(),q[i].b=read(),q[i].c=read();
    k=read();
    int l=0,r=n;
    while (l<r)
    {
        int mid=(l+r+1)>>1;
        if (check(mid)) l=mid;
        else r=mid-1;
    }
    return !printf("%d",l);
}