P2824 [HEOI2016/TJOI2016] 排序

· · 题解

P2824 [HEOI2016/TJOI2016] 排序

很巧妙的思路。最终求的是一个位置上的值，考虑一个暴力的思路，因为是排列所以可以考虑枚举答案是哪个，然后关注答案这个数的位置变化，如果经过所有操作后这个数的位置就是所求的q，那它就是答案。

所以我们可以发现，计算答案不需要知道每个数字的位置，只需要知道我们所枚举的数的最终位置就好了，但好像不排序就无法维护它的位置，又很矛盾。

考虑如何使一些不同大小的数在某种情况下等价，这样排序的意义就是针对我们所求的数字的了，在意义上不冗余后，还要把这个意义设计得足够广泛以使尽量多的元素等价，这样就方便排序了。

注意到当我们枚举答案时，所有大于这个数的其他数是同一个意义，而所有小于它的数也是同一个意义，所以把大于它的数全换成1，小于它的数全换成-1，自己是0，可以很大程度上缩减排序成本，但依旧需要枚举。

其实只差一点，因为对于只有0，1的序列的排序是简单的，可以用线段树很轻松维护，这提示我们能不能把当前枚举的答案和0或1等价，使排序简化。

这里假设和1等价，等价了的话我们关注的最终意义本来是所枚举的数的最终位置，因为我们不再知道这个数的具体位置，所以我们真正知道的是\ge这个数的所有数载最后的分布位置，而如果我们枚举的数\le最终答案，那么所求位置q上的数一定是1，这么一看，居然有了单调性，果断二分，check函数模拟以某个值为键值将所有数划分为两个意义（0,1）后模拟所有排序操作，最后返回q上值是否为1，是就往上继续二分。

复杂度O(n\log^2{n})

#include<bits/stdc++.h>
using namespace std;
#define IR(u,l,r) l<=tree[u].l&&tree[u].r<=r
#define MAXN 100010
struct node{
    int l,r;
    int val,tag;
}tree[MAXN<<2];
int n,m,q,a[MAXN],p[MAXN];
void pushup(int u)
{
    tree[u].val=tree[u*2].val+tree[u*2+1].val;
}
void maketag(int u,int x)
{
    tree[u].val=(tree[u].r-tree[u].l+1)*x;
    tree[u].tag=x;
}
void pushdown(int u)
{
    if(tree[u].tag==-1)
        return;
    maketag(u*2,tree[u].tag);
    maketag(u*2+1,tree[u].tag);
    tree[u].tag=-1;
}
void build(int u,int l,int r)
{
    tree[u].l=l,tree[u].r=r;
    tree[u].tag=-1;
    if(l==r){
        tree[u].val=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    pushup(u);
}
void update(int u,int l,int r,int x)
{
    if(l>r)return;
    if(IR(u,l,r))
        maketag(u,x);
    else{
        pushdown(u);
        int mid=(tree[u].l+tree[u].r)/2;
        if(l<=mid)update(u*2,l,r,x);
        if(r>mid)update(u*2+1,l,r,x);
        pushup(u);
    }
}
int query(int u,int l,int r)
{
    if(IR(u,l,r))
        return tree[u].val;
    else{
        pushdown(u);
        int mid=(tree[u].l+tree[u].r)/2;
        int ans=0;
        if(l<=mid)ans+=query(u*2,l,r);
        if(r>mid)ans+=query(u*2+1,l,r);
        return ans;
    }
}
int l[MAXN],r[MAXN],opt[MAXN];
int check(int x)
{
    for(int i=1;i<=n;i++)
        a[i]=p[i]>=x;
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int sum=query(1,l[i],r[i]);
        if(opt[i]==0){
            update(1,l[i],r[i]-sum,0);
            update(1,r[i]-sum+1,r[i],1);
        }else{
            update(1,l[i],l[i]+sum-1,1);
            update(1,l[i]+sum,r[i],0);
        }
    }
    return query(1,q,q);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&p[i]);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&opt[i],&l[i],&r[i]);
    scanf("%d",&q);
    int l=1,r=n,ans=0;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid))
            ans=mid,l=mid+1;
        else r=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}