HDU 5919 Sequence II（主席树）题解

r囧r小猫 2021-12-20 04:53 215阅读 0赞

题意：有A1 ~ An组成的数组，给你l r，L = min((l + ans\[i - 1\]) % n + 1, (r + ans\[i - 1\]) % n + 1)，R = max((l + ans\[i - 1\]) % n + 1, (r + ans\[i - 1\]) % n + 1)，你先需要的到L，R区间有k个不同的数字，然后问你L，R区间第（k + 1）/ 2个不同的数字下标是多少？

思路：显然是个在线询问。

我们之前已经会用主席树求区间内有多少不同数字了：从左到右把每个数字的位置存进每个操作的线段树，如果之前这个数已经出现，就在当前这棵线段树中删掉之前出现的位置，以保证每个数字出现的唯一性。显然每个区间保存的是某个数字最右边出现的位置。

但是这里显然我们不能去直接求第（k + 1）/ 2个不同的数字下标，因为我这里要求的是最早出现第（k + 1）/ 2个数的位置。那我直接从n往1建主席树，那我就变成了每个区间保存的是某个数字最左边出现的位置，显然我第i棵树并没有保存i前面的位置，那我就可以直接求i到后面任意位置的区间的第p个不相同数出现的位置。

代码：

#include<cmath>
    #include<set>
    #include<map>
    #include<queue>
    #include<cstdio>
    #include<vector>
    #include<cstring>
    #include <iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    const int maxn = 2e5 + 10;
    const int M = maxn * 30;
    const ull seed = 131;
    const int INF = 0x3f3f3f3f;
    const int MOD = 1000000007;
    int a[maxn], root[maxn], tot;
    int n, q;
    struct node{
        int lson, rson;
        int sum;
    }T[maxn * 40];
    int fa[maxn], ans[maxn];
    void init(){
        tot = 0;
        memset(fa, -1, sizeof(fa));
        memset(T, 0, sizeof(T));
    }
    void update(int l, int r, int &now, int pre, int pos, int v){
        T[++tot] = T[pre], now = tot;
        T[now].sum += v;
        if(l == r) return;
        int m = (l + r) >> 1;
        if(pos <= m)
            update(l, m, T[now].lson, T[pre].lson, pos, v);
        else
            update(m + 1, r, T[now].rson, T[pre].rson, pos, v);
    }
    int query1(int l, int r, int L, int R, int now){
        if(L <= l && R >= r){
            return T[now].sum;
        }
        int m = (l + r) >> 1, sum = 0;
        if(L <= m)
            sum += query1(l, m, L, R, T[now].lson);
        if(R > m)
            sum += query1(m + 1, r, L, R, T[now].rson);
        return sum;
    }
    int query2(int l, int r, int now, int k){
        if(l == r) return l;
        int m = (l + r) >> 1;
        int sum = T[T[now].lson].sum;
        if(sum >= k)
            return query2(l, m, T[now].lson, k);
        else
            return query2(m + 1, r, T[now].rson, k - sum);
    }
    int main(){
        int ca = 1, t;
        scanf("%d" ,&t);
        while(t--){
            init();
            scanf("%d%d", &n, &q);
            root[n + 1] = 0;
            for(int i = 1; i <= n; i++)
                scanf("%d", &a[i]);
            for(int i = n; i >= 1; i--){
                if(fa[a[i]] == -1){
                    update(1, n, root[i], root[i + 1], i, 1);
                    fa[a[i]] = i;
                }
                else{
                    update(1, n, root[i], root[i + 1], i, 1);
                    update(1, n, root[i], root[i], fa[a[i]], -1);
                    fa[a[i]] = i;
                }
            }
            ans[0] = 0;
            for(int i = 1; i <= q; i++){
                int l, r, L, R, k;
                scanf("%d%d", &l, &r);
                L = min((l + ans[i - 1]) % n + 1, (r + ans[i - 1]) % n + 1);
                R = max((l + ans[i - 1]) % n + 1, (r + ans[i - 1]) % n + 1);
                k = query1(1, n, L, R, root[L]);
                ans[i] = query2(1, n, root[L], (k + 1) / 2);
            }
            printf("Case #%d:", ca++);
            for(int i = 1 ; i <= q; i++)
                printf(" %d", ans[i]);
            printf("\n");
        }
    
        return 0;
    }

转载于:https://www.cnblogs.com/KirinSB/p/10786248.html