排序

Time Limit: 60 Sec Memory Limit: 256 MB

Description

在2016年，佳媛姐姐喜欢上了数字序列。

因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。

这个难题是这样子的：

给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排序分为两种：

1: (0,l,r)表示将区间[l,r]的数字升序排序

2: (1,l,r)表示将区间[l,r]的数字降序排序

最后询问第q位置上的数字。

Input

输入数据的第一行为两个整数n和m。

n表示序列的长度，m表示局部排序的次数。

第二行为n个整数，表示1到n的一个全排列。

接下来输入m行，每一行有三个整数op, l, r,

op为0代表升序排序，op为1代表降序排序, l, r 表示排序的区间。

最后输入一个整数q，q表示排序完之后询问的位置。

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

HINT

1 <= n <= 10^5，1 <= m <= 10^5, 1 <= q <= n。

Solution

我们先考虑如果权值很小的话怎么做，显然可以对每个权值开一个线段树维护在哪些位置出现过。

那么排序显然就是覆盖连续的一段。只要知道某一区间有几个这个权值即可。

但是这样显然是过不了的，于是我们考虑二分答案，把val >= mid的设为1，其余的设为0。

这样就把权值变成了0/1，那么显然我们按照以上操作，如果Q位置上是1说明mid<=Ans，还可以更大一点，否则说明mid>Ans。

只要支持区间求和以及区间覆盖0/1即可。

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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 400005;
const int MOD = 1e9 + 7;

int get()
{
    int res = 1, Q = 1; char c;
    while( (c = getchar()) < 48 || c > 57)
        if(c == '-') Q = -1;
    if(Q) res = c - 48;
    while( (c = getchar()) >= 48 && c <= 57)
        res = res * 10 + c - 48;
    return res * Q;
}

int n, m, Q;
int a[ONE];
int res, now;

struct power
{
    struct point
    {
        int val, tag;
    }Node[ONE];

    void Build(int i, int l, int r)
    {
        Node[i].tag = -1;
        if(l == r) return;
        int mid = l + r >> 1;
        Build(i << 1, l, mid);
        Build(i << 1 | 1, mid + 1, r);
    }

    int pushdown(int i, int l, int r)
    {
        int mid = l + r >> 1;
        if(Node[i].tag != -1)
        {
            Node[i << 1].tag = Node[i].tag;
            Node[i << 1].val = Node[i].tag * (mid - l + 1);
            Node[i << 1 | 1].tag = Node[i].tag;
            Node[i << 1 | 1].val = Node[i].tag * (r - (mid + 1) + 1);
            Node[i].tag = -1;
        }
    }

    void Update(int i, int l, int r, int L, int R, int x)
    {
        if(L > R) return;
        if(L <= l && r <= R)
        {
            Node[i].tag = x;
            Node[i].val = x * (r - l + 1);
            return;
        }
        pushdown(i, l, r);
        int mid = l + r >> 1;
        if(L <= mid) Update(i << 1, l, mid, L, R, x);
        if(mid + 1 <= R) Update(i << 1 | 1, mid + 1, r, L, R, x);
        Node[i].val = Node[i << 1].val + Node[i << 1 | 1].val;
    }

    void Query(int i, int l, int r, int L, int R)
    {
        if(L > R) return;
        if(L <= l && r <= R)
        {
            res += Node[i].val;
            return;
        }
        pushdown(i, l, r);
        int mid = l + r >> 1;
        if(L <= mid) Query(i << 1, l, mid, L, R);
        if(mid + 1 <= R) Query(i << 1 | 1, mid + 1, r, L, R);
    }
}C[2];

struct operate
{
    int l, r, x;
}oper[ONE];

void Modify(int id, int Left, int Right)
{
    res = 0;
    C[id].Query(1, 1, n, Left, Right);
    C[id].Update(1, 1, n, Left, Right, 0);
    C[id].Update(1, 1, n, now, now + res - 1, 1);
    now += res;
}

int Check(int mid)
{
    for(int i = 0; i <= 1; i++)
        C[i].Node[1].tag = 0;

    for(int i = 1; i <= n; i++)
        C[a[i] >= mid].Update(1, 1, n, i, i, 1);

    for(int i = 1; i <= m; i++)
    {
        now = oper[i].l;
        if(oper[i].x == 0) for(int id = 0; id <= 1; id++) Modify(id, oper[i].l, oper[i].r);
        if(oper[i].x == 1) for(int id = 1; id >= 0; id--) Modify(id, oper[i].l, oper[i].r);
    }

    res = 0, C[1].Query(1, 1, n, Q, Q);
    return res;
}

int main()
{
    n = get();  m = get();
    for(int i = 1; i <= n; i++)
        a[i] = get();
    for(int i = 1; i <= m; i++)
        oper[i].x = get(), oper[i].l = get(), oper[i].r = get();

    Q = get();
    int l = 1, r = n;
    while(l < r - 1)
    {
        int mid = l + r >> 1;
        if(Check(mid)) l = mid;
        else r = mid;
    }

    if(Check(r)) printf("%d", r);
    else printf("%d", l);
}