A - Sequence II HDU - 5919 （主席树两大基础应用）

亦凉 2023-06-16 10:36 9阅读 0赞

[![知识共享许可协议][80x15.png]][80x15.png 1]  
本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可。

题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=5919

题意： 给一个区间，经过上一次的值运算后新得到一个区间。问这个区间里面有多少个不同的数，个数记为k。然后将这个区间不同的数进行排序，输出第k/2个的在区间第一次出现的下标。

分析：  
主席树两大基本应用的结合。1，求区间第k大。2，求区间不同个数。  
因为他这是要求输出在区间第一次出现的位置，所以我们应该从后往前进行建树。  
这题建树并非按照每个位置的值进行建树，反而是按照每个位置的下标进行维护。同时为了避免重复，开了一个fa数组，如果有重复的出现，就把以i这个位置的线段树的fa\[a\[i\]\]的值减去即可。  
每个结点维护的是区间内不同的个数。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    
    const int N = 200010;
    int T;
    int n,m;
    int a[200100];
    int root[N],lson[N * 40],rson[N * 40];
    int sum[N * 40],top;
    int fa[N];
    
    void init()
    {
        top = 0;
        memset(sum,0,sizeof(sum));
        memset(root,0,sizeof(root));
        memset(lson,0,sizeof(lson));
        memset(rson,0,sizeof(rson));
        for(int i = 0; i < N; i ++)
            fa[i] = -1;
    }
    void Update(int l,int r,int &now,int last,int pos,int x)
    {
        now = ++ top;
        lson[now] = lson[last];
        rson[now] = rson[last];
        sum[now] = sum[last] + x;
        if(l == r) return ;
        int mid = (l + r) >> 1;
        if(pos <= mid) Update(l,mid,lson[now],lson[last],pos,x);
        else Update(mid + 1,r,rson[now],rson[last],pos,x);
    }
    
    int Query(int rt,int L,int R,int l,int r)
    {
        if(l <= L && r >= R) return sum[rt];
        int mid = (L + R) >> 1;
        int ans = 0;
        if(l <= mid) ans += Query(lson[rt],L,mid,l,r);
        if(r > mid) ans += Query(rson[rt],mid + 1,R,l,r);
        return ans;
    }
    
    int getpos(int rt,int l,int r,int k)
    {
        if(l == r) return l;
        int ans = sum[lson[rt]];
        int mid = (l + r) >> 1;
        if(ans >= k) return getpos(lson[rt],l,mid,k);
        else return getpos(rson[rt],mid + 1,r,k - ans);
    }
    int main()
    {
        scanf("%d",&T);
        int Case = 1;
        while(T --)
        {
            init();
            scanf("%d%d",&n,&m);
            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);
                else
                {
                    Update(1,n,root[i],root[i + 1],fa[a[i]],-1);
                    Update(1,n,root[i],root[i],i,1);
                }
                fa[a[i]] = i;
            }
            int ans = 0;
            printf("Case #%d:",Case ++);
            while(m --)
            {
                int l,r;
                scanf("%d%d",&l,&r);
                l = (l + ans) % n + 1;
                r = (r + ans) % n + 1;
                if(l > r) swap(l,r);
                int k = (Query(root[l],1,n,l,r) + 1) >> 1;
                printf(" %d",ans = getpos(root[l],1,n,k));
            }
            printf("\n");
        }
    }

[80x15.png]: https://i.creativecommons.org/l/by-sa/4.0/80x15.png
[80x15.png 1]: http://creativecommons.org/licenses/by-sa/4.0/