DDOSvoid's Blog

牛客IOI周赛28-提高组 C 下克上の天邪鬼

发表于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

题目描述

https://ac.nowcoder.com/acm/contest/11246/C

简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在有 $m$ 次询问，每次询问给定两个区间 $[l_1,r_1],[l_2,r_2]$，求满足 $i\in[l_1,r_1],j\in[l_2,r_2],\lfloor\frac{a_i}{2}\rfloor<a_j<a_i$ 的最大的 $a_i+a_j$

$n,m\le 2\times 10^5$

Solution

看到有一个下取整的东西，我们暴力处理，应该肯定会出现一个 $\log$

另外我们注意到答案一定是最大满足条件的 $a_i$，那么我们现在考虑按照从大到小的顺序寻找合法的 $a_i$

首先对于 $[l_1,r_1]$ 的最大值 $v$，我们去查找 $[l_2,r_2]$ 是否有 $[\lfloor\frac v 2\rfloor,v-1]$ 中的数，如果没有，我们去求 $[l_2,r_2]$ 中 $[1,\lfloor\frac{v}{2}\rfloor-1]$ 的最大的数 $w$，然后去查找 $[l_1,r_1]$ 中是否存在 $[w+1,2*w+1]$ 的数字，如果没有那么 $[l_1,r_1]$ 的范围就变成了 $[1,w]$，成功缩小了一半，容易发现只需要进行 $O(\log n)$ 次这样的过程，而我们所需要的操作仅仅是查询区间 $[l,r]$ 中属于区间 $[x,y]$ 的最大的数，这个可以用主席树实现

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

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
#include <iostream>
#define maxn 200010
#define INF 1000000000
using namespace std;

int n, m, a[maxn];

const int N = 1000000000;
#define lc T[i].ch[0]
#define rc T[i].ch[1]
#define Lc T[j].ch[0]
#define Rc T[j].ch[1]
struct Zhuxi {
    int v, ch[2]; 
} T[maxn * 31]; int rt[maxn], top;
void update(int &i, int j, int l, int r, int k, int v) {
    i = ++top; T[i] = T[j]; T[i].v += v; 
    if (l == r) return ; int m = l + r >> 1;
    if (k <= m) update(lc, Lc, l, m, k, v);
    else update(rc, Rc, m + 1, r, k, v);
}

int query(int i, int j, int l, int r, int L, int R) {
    if (l > R || r < L || T[j].v - T[i].v == 0) return 0; 
    if (l == r) return T[j].v - T[i].v > 0 ? l : 0;
    int m = l + r >> 1, v = query(rc, Rc, m + 1, r, L, R);
    if (v) return v;
    else return query(lc, Lc, l, m, L, R); 
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) update(rt[i], rt[i - 1], 1, N, a[i], 1); 
    for (int i = 1; i <= m; ++i) {
        int x1, x2, y1, y2, v = INF, ans = 0; cin >> x1 >> y1 >> x2 >> y2;
        while (v > 1) {
            v = query(rt[x1 - 1], rt[y1], 1, N, 1, v);
            int res = query(rt[x2 - 1], rt[y2], 1, N, v / 2, v - 1);
            if (res) { ans = res + v; break; }
            v = query(rt[x2 - 1], rt[y2], 1, N, 1, v / 2 - 1);
            if (v) res = query(rt[x1 - 1], rt[y1], 1, N, v + 1, 2 * v + 1);
            if (res) { ans = res + v; break; }
        } cout << ans << "\n";
    }
    return 0; 
}