2021ICPC昆明 M.Stone Games

題目鏈接
題目描述

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

During each round of the game, Rika chooses some piles from all n n n piles. Let denote the set of all chosen piles as S S S. Satoko then writes a non-negative integer x x x. If Rika takes some piles from S S S with the number of stones among all the taken piles equal to x x 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 x=0 x=0).

There are Q Q Q rounds of game in total, and for the i i i-th round of game Rika will let S S S be the set of all piles with index between l i l_i li? and r i r_i ri? . For each round, Satoko wonders the minimum integer x x 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 n n and Q Q Q, where n ( 1 ≤ n ≤ 1 0 6 ) n(1\leq n\leq 10^6) n(1≤n≤106) is the number of tiles and Q ( 1 ≤ Q ≤ 1 0 5 ) Q(1\leq Q\leq 10^5) Q(1≤Q≤105) is the number of the rounds of the games.

The second line contains n n n integers s 1 , . . . , s n s_1,...,s_n s1?,...,sn? , the i i i-th of which, s i ( 1 ≤ s i ≤ 1 0 9 ) s_i(1\leq s_i\leq 10^9) si?(1≤si?≤109) , indicates the number of stones in the tile with index i i 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 i i-th of the next Q Q Q lines contains two integers l i ′ , r i ′ ( 1 ≤ l i ′ , r i ′ ≤ n ) l_i',r_i'(1\leq l_i', r_i'\leq n) li′?,ri′?(1≤li′?,ri′?≤n) . The chosen index range for the i i i-th round, l i , r i l_i,r_i li?,ri? , 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 a n s i ans_i ansi? denotes the answer for the i i i-th round of the game (and thus a n s i ? 1 ans_{i-1} ansi?1? is the answer for the previous round). You can assume that a n s 0 = 0 ans_0=0 ans0?=0 . It is clear that under the given constraints, 1 ≤ l i ≤ r i ≤ n 1\leq l_i\leq r_i\leq n 1≤li?≤ri?≤n holds.

輸出描述:
Output Q Q Q lines, the i i i-th of which contains a single integer a n s i ans_i ansi? , denoting the minimum integer x x x Satoko can choose to win the i i 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 ] [2,4] [2,4], [ 1 , 5 ] [1,5] [1,5], [ 3 , 5 ] [3,5] [3,5], [ 1 , 4 ] [1,4] [1,4] and [ 3 , 4 ] [3,4] [3,4].

比賽時因為算錯復雜度沒有寫
比賽時原話：能不能暴力加？好像不能，如果數字都是 2 2 2 的冪次，則需要加 O ( n ) O(n) O(n) 次，（？？）
假設當先區間中的數可以合成 [ 1 , x ] [1,x] [1,x] 中的數，則對于剩余未參與合成的數，大小為 [ 1 , x + 1 ] [1,x+1] [1,x+1] 的數總和為 s u m sum sum ，如果參與合成，則可合成的數范圍可拓寬為 [ 1 , x + s u m ] [1,x+sum] [1,x+sum] ，最壞情況為數字均為 2 2 2 的冪次且不重復的情況，這樣的話每次只能將區間中的一個數加入，但是 s i s_i si? 最大為 1 0 9 10^9 109，因此最壞情況需要加 log ? 2 1 0 9 \log_210^9 log2?109 次，采用可持久化權值線段樹維護區間中不大于某個數的和，然后暴力往答案上累加，直到答案不再變化，則答案加 1 1 1 即為最終結果， 時間復雜度為 O ( Q log ? 1 0 9 log ? n ) O(Q\log10^9\log n) O(Qlog109logn) ，

#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;
}