2021ICPC昆明 M.Stone Games

题目链接
题目描述

There are $n$ piles of stones, the $i$-th of which contains $s_i$ stones. The tiles are numbered from $1$ to $n$. Rika and Satoko are playing a game on it.

During each round of the game, Rika chooses some piles from all $n$ piles. Let denote the set of all chosen piles as $S$. Satoko then writes a non-negative integer $x$. If Rika takes some piles from $S$ with the number of stones among all the taken piles equal to $x$, she wins the game, while otherwise (Rika cannot find such piles) Satoko wins the game. Note that each tile can be taken at most once during a round, and it is possible that Rika does not pick up any tile (when $x=0$).

There are $Q$ rounds of game in total, and for the $i$-th round of game Rika will let $S$ be the set of all piles with index between $l_i$ and $r_i$ . For each round, Satoko wonders the minimum integer $x$ she can write to win the game. As you are a master of programming, it is your turn to solve the problem!

输入描述:
The first line of input contains two integers $n$ and $Q$, where $n(1\le n\le 10^6)$ is the number of tiles and $Q(1\le Q\le 10^5)$ is the number of the rounds of the games.

The second line contains $n$ integers $s_1,...,s_n$ , the $i$-th of which, $s_i(1\le s_i\le 10^9)$ , indicates the number of stones in the tile with index $i$.

Satoko wants you to compute the answers immediately after Rika chooses the interval, so she uses the following method to encrypt the input. The $i$-th of the next $Q$ lines contains two integers $l_i^{\prime },r_i^{\prime }(1\le l_i^{\prime },r_i^{\prime }\le n)$ . The chosen index range for the $i$-th round, $l_i,r_i$ , can be computed by the following formula:

l i = min ? { ( l i ′ + a n s i ? 1 ) ? m o d ? n + 1 , ( r i ′ + a n s i ? 1 ) ? m o d ? n + 1 } l_i = \min\{ (l_i'+ans_{i-1}) \bmod n+1, (r_i'+ans_{i-1}) \bmod n+1 \} li?=min{(li′?+ansi?1?)modn+1,(ri′?+ansi?1?)modn+1}

r i = max ? { ( l i ′ + a n s i ? 1 ) ? m o d ? n + 1 , ( r i ′ + a n s i ? 1 ) ? m o d ? n + 1 } r_i = \max\{ (l_i'+ans_{i-1}) \bmod n+1, (r_i'+ans_{i-1}) \bmod n+1 \} ri?=max{(li′?+ansi?1?)modn+1,(ri′?+ansi?1?)modn+1}

where $an{s}_i$ denotes the answer for the $i$-th round of the game (and thus $an{s}_{i?1}$ is the answer for the previous round). You can assume that $an{s}_0=0$ . It is clear that under the given constraints, $1\le l_i\le r_i\le n$ holds.

输出描述:
Output $Q$ lines, the $i$-th of which contains a single integer $an{s}_i$ , denoting the minimum integer $x$ Satoko can choose to win the $i$-th round of the game.
示例1
输入

5 5
1 4 2 1 6
1 3
2 1
2 4
1 4
3 4

输出

8
15
4
9
4

说明
In the example above, the actual query intervals are $[2,4]$, $[1,5]$, $[3,5]$, $[1,4]$ and $[3,4]$.

比赛时因为算错复杂度没有写
比赛时原话：能不能暴力加？好像不能，如果数字都是 $2$ 的幂次，则需要加 $O(n)$ 次。（？？）
假设当先区间中的数可以合成 $[1,x]$ 中的数，则对于剩余未参与合成的数，大小为 $[1,x+1]$ 的数总和为 $sum$ ，如果参与合成，则可合成的数范围可拓宽为 $[1,x+sum]$ 。最坏情况为数字均为 $2$ 的幂次且不重复的情况，这样的话每次只能将区间中的一个数加入，但是 $s_i$ 最大为 $10^9$，因此最坏情况需要加 ${\log }_{2}10^9$ 次，采用可持久化权值线段树维护区间中不大于某个数的和，然后暴力往答案上累加，直到答案不再变化，则答案加 $1$ 即为最终结果。 时间复杂度为 $O(Q\log 10^9\log n)$ 。

#include<bits/stdc++.h>

using namespace std;
const int N = 1e6 + 10;

struct CMT {
    int seq[N << 1], rt[N], tot, m;
    struct {
        int l, r;
        long long sum;
    } t[N << 5];

    inline void init(int *a, int n) {
        memcpy(seq + 1, a + 1, sizeof(int) * n);
        for (int i = 1; i <= n; i++)seq[n + i] = seq[i] + 1;
        sort(seq + 1, seq + 2 * n + 1);
        m = unique(seq + 1, seq + 2 * n + 1) - seq - 1;
        for (int i = 1; i <= n; ++i)
            rt[i] = update(rt[i - 1], 1, m, lower_bound(seq + 1, seq + 1 + m, a[i]) - seq);
    }

    int update(int p, int l, int r, int x) {
        int dir = ++tot;
        t[dir] = t[p], t[dir].sum += seq[x];
        if (l == r)return dir;
        int mid = (l + r) >> 1;
        x <= mid ? (t[dir].l = update(t[dir].l, l, mid, x)) : (t[dir].r = update(t[dir].r, mid + 1, r, x));
        return dir;
    }

    long long ask(int u, int v, int l, int r, int x) {
        if (r <= x)return t[v].sum - t[u].sum;
        int mid = (l + r) >> 1;
        return ask(t[u].l, t[v].l, l, mid, x) + (x > mid ? ask(t[u].r, t[v].r, mid + 1, r, x) : 0);
    }

    inline long long solve(int l, int r, long long x) {
        x = upper_bound(seq + 1, seq + 1 + m, x) - seq - 1;
        return x ? ask(rt[l - 1], rt[r], 1, m, x) : 0;
    }
} C;

int n, q, a[N];
long long ans;

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
    C.init(a, n);
    while (q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        l = (l + ans) % n + 1, r = (r + ans) % n + 1;
        if (l > r)swap(l, r);
        ans = 0;
        while (true) {
            long long d = C.solve(l, r, ans + 1) - ans;
            if (!d)break;
            ans += d;
        }
        printf("%lld\n", ++ans);
    }
    return 0;
}