[ICPC2020昆明M] Stone Games

[ICPC2020昆明M] Stone Games - 线段树

Description

给定长度为 (n) 的序列，(q) 次询问，每次询问给出 (L,R)，问 ([L,R]) 中选择一个子集求和，无法凑出的最小数是多少。询问强制在线。

Solution

我们让所有数升序进来，假设当前能 (s) 以下的数都可以表示，现在进来了个 (x)，如果 (x le s+1)，那么 (s leftarrow x+s)，否则 (s) 保持不变

这个过程本质上是将 (s) 替换为所有不大于 (s+1) 的数的和

对于每次询问我们暴力模拟 (s) 增长的过程，因此我们需要的是 (O(log n)) 次的对某个下标区间的值域前缀求和，用可持久化线段树维护即可

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int N = 1000005;
const int M = 32000005;
const int OO = 1e9 + 10;
 
int n, m, s[N];
 
signed ch[M][2], root[N];
int sum[M], ind;
 
void pushup(int p)
{
    sum[p] = sum[ch[p][0]] + sum[ch[p][1]];
}
 
void modify(signed &p, signed q, int l, int r, int pos, int key)
{
    p = ++ind;
    sum[p] = sum[q];
    ch[p][0] = ch[q][0];
    ch[p][1] = ch[q][1];
 
    if (l == r)
    {
        sum[p] += key;
    }
    else
    {
        if (pos <= (l + r) / 2)
            modify(ch[p][0], ch[q][0], l, (l + r) / 2, pos, key);
        else
            modify(ch[p][1], ch[q][1], (l + r) / 2 + 1, r, pos, key);
        pushup(p);
    }
}
 
int query(int p, int l, int r, int ql, int qr)
{
    if (p == 0 || l > qr || r < ql)
        return 0;
    if (l >= ql && r <= qr)
        return sum[p];
    return query(ch[p][0], l, (l + r) / 2, ql, qr) + query(ch[p][1], (l + r) / 2 + 1, r, ql, qr);
}
 
signed main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> s[i];
 
    root[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        modify(root[i], root[i - 1], 1, OO, s[i], s[i]);
    }
 
    int lastans = 0;
 
    for (int i = 1; i <= m; i++)
    {
        int l1, r1;
        cin >> l1 >> r1;
        int l = (l1 + lastans) % n + 1;
        int r = (r1 + lastans) % n + 1;
        if (l > r)
            swap(l, r);
        int x = -1, y = 0;
        while (x != y)
        {
            x = y;
            y = query(root[r], 1, OO, 1, x + 1) - query(root[l - 1], 1, OO, 1, x + 1);
        }
        cout << (lastans = x + 1) << endl;
    }
}