[bzoj4552][二分][线段树]排序

104 阅读 0 评论 69 点赞

我是靠谱客的博主雪白金鱼，这篇文章主要介绍[bzoj4552][二分][线段树]排序，现在分享给大家，希望可以做个参考。

Description

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

Input

输入数据的第一行为两个整数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

Output

输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第q位置上的数字。

Sample Input

6 3

1 6 2 5 3 4

0 1 4

1 3 6

0 2 4

3

Sample Output

5

题解

神题
二分答案ans，将数列里小于等于ans的设为0，大于ans的设为1
两种操作的话就是相当于在一段里一部分改成0一部分改成1
这个用线段树来维护
最后观察q答案的时候，如果q==0，那么往小的缩范围，并记录答案
否则往大的缩范围
满足二分性

复制代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
struct node
{
    int lc,rc,l,r;
    int z,o;bool lazy;
}tr[210000];int trlen;
void bt(int l,int r)
{
    int now=++trlen;
    tr[now].l=l;tr[now].r=r;
    tr[now].lc=tr[now].rc=-1;
    tr[now].z=tr[now].o=0;tr[now].lazy=false;
    if(l<r)
    {
        int mid=(l+r)/2;
        tr[now].lc=trlen+1;bt(l,mid);
        tr[now].rc=trlen+1;bt(mid+1,r);
    }
}
void lazy(int x)
{
    int lc=tr[x].lc,rc=tr[x].rc;
    if(tr[x].z==(tr[x].r-tr[x].l+1))
    {
        tr[lc].z=tr[lc].r-tr[lc].l+1;tr[lc].o=0;
        tr[rc].z=tr[rc].r-tr[rc].l+1;tr[rc].o=0;
        tr[lc].lazy=tr[rc].lazy=true;
    }
    else
    {
        tr[lc].o=tr[lc].r-tr[lc].l+1;tr[lc].z=0;
        tr[rc].o=tr[rc].r-tr[rc].l+1;tr[rc].z=0;
        tr[lc].lazy=tr[rc].lazy=true;
    }
    tr[x].lazy=false;
}
void ch(int now,int p,int c)
{
    if(tr[now].l==tr[now].r)
    {
        if(c==0)tr[now].z=1,tr[now].o=0;
        else tr[now].o=1,tr[now].z=0;
        return ;
    }
    int lc=tr[now].lc,rc=tr[now].rc;
    int mid=(tr[now].l+tr[now].r)/2;
    if(tr[now].lazy)lazy(now);
    if(p<=mid)ch(lc,p,c);
    else ch(rc,p,c);
    tr[now].z=tr[lc].z+tr[rc].z;
    tr[now].o=tr[lc].o+tr[rc].o;
}
int Z,O;
void findsum(int now,int l,int r)
{
    if(tr[now].l==l && tr[now].r==r)
    {
        Z+=tr[now].z;O+=tr[now].o;
        return ;
    }
    int lc=tr[now].lc,rc=tr[now].rc;
    int mid=(tr[now].l+tr[now].r)/2;
    if(tr[now].lazy)lazy(now);
    if(r<=mid)findsum(lc,l,r);
    else if(mid+1<=l)findsum(rc,l,r);
    else findsum(lc,l,mid),findsum(rc,mid+1,r);
}
void change(int now,int l,int r,int op)
{
    if(tr[now].l==l && tr[now].r==r)
    {
        if(op==0)tr[now].z=tr[now].r-tr[now].l+1,tr[now].o=0;
        else tr[now].o=tr[now].r-tr[now].l+1,tr[now].z=0;
        tr[now].lazy=true;
        return ;
    }
    int lc=tr[now].lc,rc=tr[now].rc;
    int mid=(tr[now].l+tr[now].r)/2;
    if(tr[now].lazy)lazy(now);
    if(r<=mid)change(lc,l,r,op);
    else if(mid+1<=l)change(rc,l,r,op);
    else change(lc,l,mid,op),change(rc,mid+1,r,op);
    tr[now].z=tr[lc].z+tr[rc].z;
    tr[now].o=tr[lc].o+tr[rc].o;
}
int fd(int now,int p)
{
    if(tr[now].l==tr[now].r)
    {
        if(tr[now].z==0)return 1;
        return 0;
    }
    int lc=tr[now].lc,rc=tr[now].rc;
    int mid=(tr[now].l+tr[now].r)/2;
    if(tr[now].lazy)lazy(now);
    if(p<=mid)return fd(lc,p);
    else return fd(rc,p);
}
struct ask
{
    int l,r,op;
}A[110000];
int n,m,a[110000],q;
bool check(int p)
{
    for(int i=1;i<=n;i++)
    {
        if(a[i]>p)ch(1,i,1);
        else ch(1,i,0);
    }
    for(int i=1;i<=m;i++)
    {
        Z=O=0;findsum(1,A[i].l,A[i].r);
        if(A[i].op==0)
        {
            if(Z>0)change(1,A[i].l,A[i].l+Z-1,0);
            if(Z<A[i].r-A[i].l+1)change(1,A[i].l+Z,A[i].r,1);
        }
        else
        {
            if(O>0)change(1,A[i].l,A[i].l+O-1,1);
            if(O<A[i].r-A[i].l+1)change(1,A[i].l+O,A[i].r,0);
        }
    }
    int col=fd(1,q);
    if(col==0)return true;
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    trlen=0;bt(1,n);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&A[i].op,&A[i].l,&A[i].r);
    scanf("%d",&q);
    int l=1,r=n,ans;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid)){ans=mid;r=mid-1;}
        else l=mid+1;
    }
    printf("%dn",ans);
    return 0;
}

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
struct node
{
    int lc,rc,l,r;
    int z,o;bool lazy;
}tr[210000];int trlen;
void bt(int l,int r)
{
    int now=++trlen;
    tr[now].l=l;tr[now].r=r;
    tr[now].lc=tr[now].rc=-1;
    tr[now].z=tr[now].o=0;tr[now].lazy=false;
    if(l<r)
    {
        int mid=(l+r)/2;
        tr[now].lc=trlen+1;bt(l,mid);
        tr[now].rc=trlen+1;bt(mid+1,r);
    }
}
void lazy(int x)
{
    int lc=tr[x].lc,rc=tr[x].rc;
    if(tr[x].z==(tr[x].r-tr[x].l+1))
    {
        tr[lc].z=tr[lc].r-tr[lc].l+1;tr[lc].o=0;
        tr[rc].z=tr[rc].r-tr[rc].l+1;tr[rc].o=0;
        tr[lc].lazy=tr[rc].lazy=true;
    }
    else
    {
        tr[lc].o=tr[lc].r-tr[lc].l+1;tr[lc].z=0;
        tr[rc].o=tr[rc].r-tr[rc].l+1;tr[rc].z=0;
        tr[lc].lazy=tr[rc].lazy=true;
    }
    tr[x].lazy=false;
}
void ch(int now,int p,int c)
{
    if(tr[now].l==tr[now].r)
    {
        if(c==0)tr[now].z=1,tr[now].o=0;
        else tr[now].o=1,tr[now].z=0;
        return ;
    }
    int lc=tr[now].lc,rc=tr[now].rc;
    int mid=(tr[now].l+tr[now].r)/2;
    if(tr[now].lazy)lazy(now);
    if(p<=mid)ch(lc,p,c);
    else ch(rc,p,c);
    tr[now].z=tr[lc].z+tr[rc].z;
    tr[now].o=tr[lc].o+tr[rc].o;
}
int Z,O;
void findsum(int now,int l,int r)
{
    if(tr[now].l==l && tr[now].r==r)
    {
        Z+=tr[now].z;O+=tr[now].o;
        return ;
    }
    int lc=tr[now].lc,rc=tr[now].rc;
    int mid=(tr[now].l+tr[now].r)/2;
    if(tr[now].lazy)lazy(now);
    if(r<=mid)findsum(lc,l,r);
    else if(mid+1<=l)findsum(rc,l,r);
    else findsum(lc,l,mid),findsum(rc,mid+1,r);
}
void change(int now,int l,int r,int op)
{
    if(tr[now].l==l && tr[now].r==r)
    {
        if(op==0)tr[now].z=tr[now].r-tr[now].l+1,tr[now].o=0;
        else tr[now].o=tr[now].r-tr[now].l+1,tr[now].z=0;
        tr[now].lazy=true;
        return ;
    }
    int lc=tr[now].lc,rc=tr[now].rc;
    int mid=(tr[now].l+tr[now].r)/2;
    if(tr[now].lazy)lazy(now);
    if(r<=mid)change(lc,l,r,op);
    else if(mid+1<=l)change(rc,l,r,op);
    else change(lc,l,mid,op),change(rc,mid+1,r,op);
    tr[now].z=tr[lc].z+tr[rc].z;
    tr[now].o=tr[lc].o+tr[rc].o;
}
int fd(int now,int p)
{
    if(tr[now].l==tr[now].r)
    {
        if(tr[now].z==0)return 1;
        return 0;
    }
    int lc=tr[now].lc,rc=tr[now].rc;
    int mid=(tr[now].l+tr[now].r)/2;
    if(tr[now].lazy)lazy(now);
    if(p<=mid)return fd(lc,p);
    else return fd(rc,p);
}
struct ask
{
    int l,r,op;
}A[110000];
int n,m,a[110000],q;
bool check(int p)
{
    for(int i=1;i<=n;i++)
    {
        if(a[i]>p)ch(1,i,1);
        else ch(1,i,0);
    }
    for(int i=1;i<=m;i++)
    {
        Z=O=0;findsum(1,A[i].l,A[i].r);
        if(A[i].op==0)
        {
            if(Z>0)change(1,A[i].l,A[i].l+Z-1,0);
            if(Z<A[i].r-A[i].l+1)change(1,A[i].l+Z,A[i].r,1);
        }
        else
        {
            if(O>0)change(1,A[i].l,A[i].l+O-1,1);
            if(O<A[i].r-A[i].l+1)change(1,A[i].l+O,A[i].r,0);
        }
    }
    int col=fd(1,q);
    if(col==0)return true;
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    trlen=0;bt(1,n);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&A[i].op,&A[i].l,&A[i].r);
    scanf("%d",&q);
    int l=1,r=n,ans;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid)){ans=mid;r=mid-1;}
        else l=mid+1;
    }
    printf("%dn",ans);
    return 0;
}