ICPC2021昆明M-暴力+主席树

题目大意:

给你一个序列。每次询问一个区间 每个数选或不选 最小的不能被加出来的值。

题目思路:

考虑暴力:排序后若某个前缀和 < 下一个数 - 1 就停。

如果将值域归桶，然后再对其预处理前缀和。容易证明我们能够在lognlogn的复杂度内暴力二分出来.

容易将这个过程放到主席树上进行.然后记得对数据离散化
复杂度：$O(nlognlogn)$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define vi vector<int>
#define vll vector<ll>
#define fi first
#define se second
#define mid ((l + r) >> 1)
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
ll a[maxn] , b[maxn];
int rt[maxn] , ls[maxn << 5] , rs[maxn << 5] , cnt;
ll s[maxn << 5];
ll dist[maxn] , tot;
void pushup (int t){
    
    s[t] = s[ls[t]] + s[rs[t]];
}
int add (int t , int l , int r , int p , int c){
    
    int now = ++cnt;
    ls[now] = ls[t];
    rs[now] = rs[t];
    s[now] = s[t];
    if (l == r){
    
        s[now] += c;
        return now;
    }
    if (p <= mid)
        ls[now] = add(ls[now] , l , mid , p , c);
    else
        rs[now] = add(rs[now] , mid + 1, r , p , c);
    pushup(now);
    return now;
}
ll ask (int t , int l , int r , int L , int R){
    
    if (!t) return 0;
    if (L <= l && r <= R) return s[t];
    ll ans = 0;
    if (L <= mid) ans += ask(ls[t] , l , mid , L , R);
    if (R > mid) ans += ask(rs[t] , mid + 1 , r , L , R);
    return ans;
}
ll getR (ll x){
    
    ll g = upper_bound(dist + 1 , dist + 1 + tot , x) - dist;
    g--;
    return g;
}

ll getL (ll x){
    
    ll g = lower_bound(dist + 1 , dist + 1 + tot , x) - dist;
    return g;
}
ll calc (int l , int r , ll x , ll y){
    
    x = getL(x);
    y = getR(y);
    if (x > y) return -1;
    ll a = ask(rt[r] , 1 , tot , x , y);
    ll b = ask(rt[l - 1] , 1 , tot , x , y);
    return a - b;
}

int main()
{
    
    int n , m; scanf("%d%d" , &n , &m);
    for (int i = 1 ; i <= n ; i++) {
    
        scanf("%lld" , a + i);
        dist[++tot] = a[i];
    }
    sort(dist + 1 , dist + 1 + tot);
    tot = unique(dist + 1 , dist + 1 + tot ) - dist - 1;
    for (int i = 1 ; i <= n ; i++){
    
        b[i] = lower_bound(dist + 1 ,dist + 1 + tot , a[i]) - dist;
        rt[i] = add(rt[i - 1] , 1 , tot , b[i] , a[i]);
    }
    ll ans = 0;
    for (int i = 1 ; i <= m ; i++){
    
        int nl , nr; scanf("%d%d" , &nl , &nr);
        int l = min((nl + ans) % n + 1 , (nr + ans) % n + 1);
        int r = max((nl + ans) % n + 1 , (nr + ans) % n + 1);
        ll now = 0;
        vector<ll> g;
        int ok = true;
        int yy = 0;
        while (1){
    
           // cout << "now this range can be made:" << 0 << " " << now << endl;
            yy++;
            assert(yy <= 100);
            now = calc(l , r , 1 , now + 1);
            if (now == -1){
    
                ok = false;
                break;
            }
            if (g.size() && g.back() == now) break;
            g.push_back(now);
        }
        if (!ok){
    
            printf("%lld\n" , 1);
            continue;
        }
        ans = g.back() + 1;
        printf("%lld\n" , ans);
    }
    return 0;
}