「TJOI2016/HEOI2016」排序

发表于 | | 阅读次数:
字数统计: 695 字

Description

题目链接：BZOJ 4552

对一个长度为 $n$ 的排列 $a$ 进行 $m$ 次局部排序：

  • 0 l r：将区间 $[l,r]$ 中的数字进行升序排序。
  • 1 l r：将区间 $[l,r]$ 中的数字进行降序排列。

操作结束后，需要求出 $a_p$ 的值。

数据范围：$1\le n,m\le 10^5$

Solution

这题直接进行模拟排序一定超时，所以我们考虑如何在较快的时间内完成排序。

对最后 $a_q$ 的值 $x$ 进行二分，令 $v_i=[a_i>x]$。此时问题转化为了判定性问题：求最后 $a_q$ 的值和 $x$ 的大小关系。

对于一个 $01$ 序列，我们可以使用线段树在 $O(\log n)$ 的时间内进行模拟排序（区间查询和覆盖）。

时间复杂度：$O(m\log^2 n)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
#include <cstdio>
#define lson rt<<1
#define rson rt<<1|1
const int N=1e5+5;
int n,m,pos,a[N],ll[N],rr[N],opt[N],seg[N<<2],tag[N<<2],v[N];

void update(int rt,int l,int r,int val) {
    seg[rt]=val*(r-l+1);
    tag[rt]=val;
}
void pushup(int rt) {
    seg[rt]=seg[lson]+seg[rson];
}
void pushdown(int rt,int l,int r) {
    if(tag[rt]==-1) return;
    int mid=(l+r)>>1;
    update(lson,l,mid,tag[rt]);
    update(rson,mid+1,r,tag[rt]);
    tag[rt]=-1;
}
void build(int rt,int l,int r) {
    tag[rt]=-1;
    if(l==r) {
        seg[rt]=v[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    pushup(rt);
}
void modify(int x,int y,int rt,int l,int r,int val) {
    if(x>y) return;
    if(x<=l&&r<=y) {
        update(rt,l,r,val);
        return;
    }
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    if(x<=mid) modify(x,y,lson,l,mid,val);
    if(mid<y) modify(x,y,rson,mid+1,r,val);
    pushup(rt);
}
int query(int x,int y,int rt,int l,int r) {
    if(x<=l&&r<=y) return seg[rt];
    pushdown(rt,l,r);
    int mid=(l+r)>>1,res=0;
    if(x<=mid) res+=query(x,y,lson,l,mid);
    if(mid<y) res+=query(x,y,rson,mid+1,r);
    return res;
}
int check(int x) {
    for(int i=1;i<=n;++i) v[i]=(a[i]>x);
    build(1,1,n);
    for(int i=1;i<=m;++i) {
        int l=ll[i],r=rr[i],o=opt[i];
        int cnt1=query(l,r,1,1,n),cnt0=r-l+1-cnt1;
        if(o) {
            modify(l,l+cnt1-1,1,1,n,1);
            modify(l+cnt1,r,1,1,n,0);
        } else {
            modify(l,l+cnt0-1,1,1,n,0);
            modify(l+cnt0,r,1,1,n,1);
        }
    }
    return query(pos,pos,1,1,n);
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=1;i<=m;++i) scanf("%d%d%d",&opt[i],&ll[i],&rr[i]);
    scanf("%d",&pos);
    int l=1,r=n,ans;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(check(mid)) l=mid+1;
        else ans=mid,r=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}
0%