oj4408 [Fjoi 2016]神秘数 & bzoj4299 Codechef FRBSUM 主席树+二分+贪心

题解

考虑如果直接给一个序列要求出它的神秘数应该怎么做。3366857976

对于第

如果

但是为了防止在第一种情况中的新的

那么这个时候如果遇到第二种情况其实就可以直接结束了。

考虑这个做法如何支持区间多组询问。

很容易发现，我们最后取的答案一定是把整段区间排序完以后的结果的一个前缀和的值

于是我们可以得到一个思路：

对于目前的前缀和

重复这个过程就可以了。

可以发现

维护的话使用主席树维护，可以方便地查询出来每一个区间的小于等于某个值的数的和。

时间复杂度

#include<bits/stdc++.h>

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back

template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}
template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;

template<typename I> inline void read(I &x) {
    int f = 0, c;
    while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
    x = c & 15;
    while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
    f ? x = -x : 0;
}

const int N = 1e5 + 7;

int n, m, dis, nod;
int a[N], b[N], rt[N];

struct Node { int lc, rc, val, sum; } t[N * 18];

inline void ins(int &o, int p, int L, int R, int x) {
    t[o = ++nod] = t[p], ++t[o].val, t[o].sum += b[x];
    if (L == R) return;
    int M = (L + R) >> 1;
    if (x <= M) ins(t[o].lc, t[p].lc, L, M, x);
    else ins(t[o].rc, t[p].rc, M + 1, R, x);
}
inline int qsum(int o, int p, int L, int R, int l, int r) {
    if (l > r) return 0;
    if (l <= L && R <= r) return t[o].sum - t[p].sum;
    int M = (L + R) >> 1;
    if (r <= M) return qsum(t[o].lc, t[p].lc, L, M, l, r);
    if (l > M) return qsum(t[o].rc, t[p].rc, M + 1, R, l, r);
    return qsum(t[o].lc, t[p].lc, L, M, l, r) + qsum(t[o].rc, t[p].rc, M + 1, R, l, r);
}

inline int get(int x) { return std::upper_bound(b + 1, b + dis + 1, x) - b - 1; }
inline void lsh() {
    std::sort(b + 1, b + n + 1);
    dis = std::unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; ++i) a[i] = get(a[i]);
}

inline void work() {
    lsh();
    b[++dis] = (1ll << 31) - 1;
    for (int i = 1; i <= n; ++i) ins(rt[i], rt[i - 1], 1, dis, a[i]);
    read(m);
    while (m--) {
        int l, r;
        read(l), read(r);
        if (l > r) std::swap(l, r);
        int s = 1, tmp;
        while ((tmp = qsum(rt[r], rt[l - 1], 1, dis, 1, get(s))) >= s) s = tmp + 1;
        printf("%d\n", s);
    }
}

inline void init() {
    read(n);
    for (int i = 1; i <= n; ++i) read(a[i]), b[i] = a[i];
}

int main() {
#ifdef hzhkk
    freopen("hkk.in", "r", stdin);
#endif
    init();
    work();
    fclose(stdin), fclose(stdout);
    return 0;

oj4408 [Fjoi 2016]神秘数 & bzoj4299 Codechef FRBSUM 主席树+二分+贪心

题解

相关推荐