E 仓鼠与珂朵莉

E 仓鼠与珂朵莉

主席树 + 启发式合并思想

题意：

给你一个长度为n的数组， 每次操作选择一个区间 然后问 选择一个数 然就出 再这个区间的次数的乘积。

题解：

如果给你一个区间 对于暴力的求法一般是枚举每个数， 再去查找这个数出现了几次，然后算出最大的贡献。

这样对于每次询问都是 的复杂度。

如果我们每次只找 出现一次 且最大的数， 出现两次且最大的数， 出现三次且最大的数…………

假设已经知道看出现一次且最大的数， 出现两次且最大的数…………

那么枚举的时间复杂度为 大概是 左右，但是这样有个问题？

如何找到出现一次且最大的数， 出现两次且最大数？

我想了很久好像没有可行的方法。

但是， 仔细想一下， 你会发现， 如果最大值出现了 次也就意味着小于 次的就不用再找，那么也就意味着

找 第一个比 最大值小 且 出现次数大于 次的数。

那么这样每次的复杂度就是 （表示最大值出现的次数 表示第一个比最大小的数出现的次数…………）

每次寻找都比之前的大，是不是启发式合并的复杂度啊， 哦好像是的

那么怎么找到这个每个数出现的次数呢？

这里可以用到主席树了

主席树没法确定单个数字出现的个数只能求出这个区间有多少个数， 当这个区间的总个数都小于 那么肯定没有单点信息大于 ， 在维护一个每个数 在 区间出现的 重要程度的最大值， 如果区间重要程度的最大值都小于 直接找的答案也就没用必要再找， 这样两个限制大概率保证了每个数出现的个数了。

所以总共的时间复杂度为

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 7;

typedef long long ll;
struct hjt{
    int l, r, cnt;
    ll sum;
}tree[40 * N];


vector<ll> g;
int get_id(int x) {
    return lower_bound(g.begin(), g.end(), x) - g.begin() + 1;
}

ll a[N], n, q, b[N];
int rt[N], top = 1;

#define m (l + r) / 2

void update(int pos, int l, int r, int last, int &now) {
    now = top++;
    tree[now] = tree[last];
    tree[now].cnt++;
    if (l == r) {
        tree[now].sum += g[l - 1];
        return;
    }
    if (pos <= m) update(pos, l, m, tree[now].l, tree[now].l);
    else update(pos, m + 1, r, tree[last].r, tree[now].r);
    tree[now].sum = max(tree[tree[now].l].sum, tree[tree[now].r].sum);
}

ll mx = 0;
ll ans = 0;

void query(int last, int now, int l, int r) {
    if (l == r) {
        ll su = tree[now].cnt - tree[last].cnt;
        ll va = tree[now].sum - tree[last].sum;
        mx = max(mx, 1ll*su);
        ans = max(ans, va);
        return;
    }
    int sumr = tree[tree[now].r].cnt - tree[tree[last].r].cnt;
    int suml = tree[tree[now].l].cnt - tree[tree[last].l].cnt;

    if (sumr > mx && ans < tree[tree[now].r].sum) {
        query(tree[last].r, tree[now].r, m + 1, r);
    }
    if (suml > mx && ans < tree[tree[now].l].sum) {
        query(tree[last].l, tree[now].l, l, m);
    }

}


int main() {
    scanf("%lld %lld", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        g.push_back(a[i]);
    }
    sort(g.begin(), g.end());
    g.erase(unique(g.begin(), g.end()));

    for (int i = 1; i <= n; i++) {
        b[i] = get_id(a[i]);
    }
    int maxn = g.size();
    for (int i = 1; i <= n; i++) {
        update(b[i], 1, maxn, rt[i - 1], rt[i]);
    }
    ll last = 0;
    while (q--) {
        ll l, r;
        scanf("%lld %lld", &l, &r);
        l = (l ^ last) % n + 1;
        r = (r ^ last) % n + 1;
        if (l > r) swap(l, r);
        ans = 0; mx = 0;
        query(rt[l - 1], rt[r], 1, maxn);
        printf("%lld\n", ans);
        last = ans;

    }


}