Codeforces484 E. Sign on Fence 主席树+线段树维护连续1区间+二分

传送门：https://codeforces.com/contest/484/problem/E

鏖战3小时，终于…

题意

给一个序列a，m次查询，l,r,w，查询[l,r]中所有连续w个元素最小值的最大值。

思路

查找最值，想到二分，但是要求所有[l,r]中连续w个元素区间中的最小值的最大值。

首先二分的是答案，但是h有1e9之多，二分的常数较大，所以我们可以将序列排序，然后二分下标。

假设枚举的下标为mid，则在一个区间中至少有w个元素比mid大。 则合法，ans=mid，r=mid+1，否则l=mid+1。

但是我们怎么check这个区间呢？ 设比mid大的为1，反之为0，则我们要求是是否存在最长的连续1区间长度$\ge$ w。

这一部分可以用线段树处理，就是处理suml,sumr,sum等等。自行百度。

但是不可能每次check都要建立一颗线段树啊，不仅MLE还会TLE。

这时候就需要主席树这个黑科技，将序列从大到小排列后正向建立主席树，也就是创建每一个不同的版本。

而我们二分得到的mid，就可以直接在root[mid]这个版本进行处理即可。

所以总流程为：

  • $序列从小到达排序建立主席树$
  • $每个版本的线段树维护最长连续1区间长度$
  • $对于每次询问，二分答案下标，查询时候存在query\ge w，然后处理l和r的走向。$
  • $输出a[ans].x$

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

typedef long long ll;

const int N = 2e5 + 10;

struct node {
    int x, id;
}a[N];

bool cmp(node a, node b) {
    return a.x == b.x ? a.id > b.id : a.x > b.x;
}

struct HJTTree {
    int l, r;
    int suml, sumr, sum;
}t[N * 40];
int root[N], cnt;

inline void push_up(int u, int l, int r) {
    int mid = (l + r) / 2;
    t[u].suml = t[t[u].l].suml;
    if(t[t[u].l].suml == mid - l + 1) t[u].suml += t[t[u].r].suml;
    t[u].sumr = t[t[u].r].sumr;
    if(t[t[u].r].sumr == r - mid) t[u].sumr += t[t[u].l].sumr;
    t[u].sum = max(max(t[t[u].l].sum, t[t[u].r].sum), t[t[u].l].sumr + t[t[u].r].suml);
}

void insert(int pre, int &now, int l, int r, int p) {
    t[now = ++cnt] = t[pre];
    if(l == r) {
        t[now].sum = t[now].suml = t[now].sumr = 1;
        return ;
    }
    int m = (l + r) / 2;
    if(p <= m) insert(t[pre].l, t[now].l, l, m, p);
    else insert(t[pre].r, t[now].r, m + 1, r, p);
    push_up(now, l, r);
}

int query(int u, int ql, int qr, int l, int r) {
    if(l > r) return 0;
    if(ql == l && r == qr) return t[u].sum;
    int ans = 0;
    int m = (l + r) / 2;
    if(qr <= m) ans = max(ans, query(t[u].l, ql, qr, l, m));
    else if(ql > m) ans = max(ans, query(t[u].r, ql, qr, m + 1, r));
    else {
        ans = max(query(t[u].l, ql, m, l, m), query(t[u].r, m + 1, qr, m + 1, r));
        // 左儿子的右区间、右儿子的左区间---合并
        ans = max(ans, min(m - ql + 1, t[t[u].l].sumr) + min(qr - m, t[t[u].r].suml));
    }
    return ans;
}

void solve()  {
    int n; cin >> n;
    for(int i = 1;i <= n; i++) cin >> a[i].x, a[i].id = i;
    sort(a + 1, a + n + 1, cmp);
    for(int i = 1;i <= n; i++) insert(root[i - 1], root[i], 1, n, a[i].id);
    int m; cin >> m;
    while(m--) {
        int ql, qr, w; cin >> ql >> qr >> w;
        int l = 1, r = n, ans = n;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(query(root[mid], ql, qr, 1, n) >= w) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        cout << a[ans].x << endl;
    }
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/05/07/codeforces484-e-sign-on-fence/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！