更好的阅读体验

原题 - 【FJOI2016】神秘数

如果只有一次全局询问，可以排序之后扫一遍数组，每次和比较，更新答案，直到不能更新为止

区间询问不能排序，但是如果不排序的话，进行上述操作，最多扫次就能得出答案

考虑每次更新时，可以更新的数一定比上一次更新时的大(否则在上一次更新就计入里了)，于是我们最多会更新次

于是我们就有了一个主席树的做法去优化找小于某个值的做法，复杂度

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

#define ub(x) (upper_bound(b + 1, b + n + 1, x) - b - 1)

using namespace std;

const int N = 8e7 + 10, M = 2e6 + 10, inf = 0x3f3f3f3f;

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

int n, m, cnt, a[N], b[N], ls[N], rs[N], rt[N];

long long sum[N];

void insert(int &x, int y, int l, int r, int t) {
    x = ++cnt; ls[x] = ls[y]; rs[x] = rs[y]; sum[x] = sum[y] + b[t];
    if (l == r) return; int mid = l + r >> 1;
    if (mid >= t) insert(ls[x], ls[y], l, mid, t);
    else insert(rs[x], rs[y], mid + 1, r, t);
}

long long query(int x, int y, int l, int r, int ln, int rn) {
    if (l > r) return 0; if (ln <= l && r <= rn) return sum[y] - sum[x];
    int mid = l + r >> 1;
    if (mid >= rn) return query(ls[x], ls[y], l, mid, ln, rn);
    if (mid + 1 <= ln) return query(rs[x], rs[y], mid + 1, r, ln, rn);
    return query(ls[x], ls[y], l, mid, ln, rn) + query(rs[x], rs[y], mid + 1, r, ln, rn);
}

int main() {
    n = read(); m = read();
    for (int i = 1; i <= n; i++) a[i] = read(), b[i] = a[i];
    sort(b + 1, b + n + 1); int t = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(b + 1, b + t + 1, a[i]) - b; insert(rt[i], rt[i - 1], 0, t, a[i]);
    }
    n = t;
    for (int i = 1; i <= m; i++) {
        int l = read(), r = read();
        long long ans = 0, t = query(rt[l - 1], rt[r], 0, n, 0, ub(ans + 1));
        while (t > ans) ans = t, t = query(rt[l - 1], rt[r], 0, n, 0, ub(ans + 1));
        printf("%lld\n", ans + 1);
    }
    return 0;
}