HDU 5919 Sequence II （主席树）

爱被打了一巴掌 2022-07-16 07:00 133阅读 0赞

强烈推荐推荐不懂主席树的看一下这篇文章：  
http://www.cnblogs.com/zyf0163/p/4749042.html

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

题目大意：给你一个区间，假设这个区间中有k个数，每个数的位置升序排列为 p1 p2 p3 ->pk，问p\[k/2\]是多少

解题思路：  
（解题思路如果看不懂可以先看一下HDU 3333）

没注意题目范围 应该是不用离散化的 然后这里离散化了一下

从后向前建n颗树，树的结点维护区间内有多少个不同的值，建树时，每遇到一个新点，判断之前是否出现过，若出现过，在之前的位置减1，给新位置加1。  
对于每个询问，先查询出每个区间有多少个不同的值，假设有k个，直接查询区间k/2小就可以了，2/k向上取整。

AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <list>
    #include <map>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <set>
    #include <functional>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    double EPS=1e-10;
    typedef long long LL;
    const int N =200000+5;
    int a[N],b[N],tot,rt[N*40],sum[N*40],ls[N*40],rs[N*40],sz,cas=1,exi[N],n;
    int preans;
    
    void build(int &o,int l,int r)
    {
        o=++tot;
        sum[o]=0;
        if(l==r) return ;
        int m=(l+r)>>1;
        build(ls[o],l,m);
        build(rs[o],m+1,r);
    }
    
    void update(int &o,int l,int r,int last,int p,int add)
    {
        o=++tot;
        sum[o]=sum[last]+add;
        ls[o]=ls[last];
        rs[o]=rs[last];
        if(l==r) return ;
        int m=(l+r)>>1;
        if(p<=m) update(ls[o],l,m,ls[last],p,add);
        else update(rs[o],m+1,r,rs[last],p,add);
    }
    
    
    int query1(int l,int r,int rtt,int L,int R)
    {
        if(L<=l&&r<=R)
        {
            //  cout<<"l = "<<l<<" r ="<<r<<"sum = "<<sum[rtt]<<endl;
            return sum[rtt];
        }
        int m=(l+r)>>1;
        int ans=0;
        if(m>=L) ans+=query1(l,m,ls[rtt],L,R);
        if(m<R) ans+=query1(m+1,r,rs[rtt],L,R);
        return ans;
    
    }
    
    int query(int now,int l,int r,int k)
    {
        int ans=0;
        if(l==r) return l;
        int m=(l+r)>>1;
        int cnt=sum[ls[now]];
        if(k<=cnt) return query(ls[now],l,m,k);
        return query(rs[now],m+1,r,k-cnt);
    }
    
    void solve()
    {
        int l,r;
        RII(l,r);
        int ll=min((l+preans)%n+1,(r+preans)%n+1);
        int rr=max((l+preans)%n+1,(r+preans)%n+1);
       // cout<<"主节点 = "<<sum[rt[rr]]<<endl;
       // cout<<"ll = "<<ll<<"rr = "<<rr<<endl;
        int ans=query1(1,n,rt[ll],ll,rr);
       // cout<<"ans = "<<ans<<endl;
        int ans1=ans/2;
        if(ans%2) ans1++;
        int x=query(rt[ll],1,n,ans1);
        printf(" %d",x);
        preans=x;
    }
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            int q;
            RII(n,q);
            for(int i=1; i<=n; i++) RI(a[i]),b[i]=a[i];
            sort(b+1,b+n+1);
            sz=unique(b+1,b+n+1)-(b+1);
            tot=0;
            build(rt[n+1],1,n);
            for(int i=1; i<=n; i++) a[i]=lower_bound(b+1,b+sz+1,a[i])-b;
            memset(exi,0,sizeof(exi));
            for(int i=n; i>=1; i--)
            {
                if(exi[a[i]])
                {
                    update(rt[i],1,n,rt[i+1],exi[a[i]],-1);
                    update(rt[i],1,n,rt[i],i,1);
                }
                else
                {
                    update(rt[i],1,n,rt[i+1],i,1);
                }
                exi[a[i]]=i;
            }
    
            printf("Case #%d:",cas++);
            preans=0;
            while(q--) solve();
            printf("\n");
        }
        return 0;
    }