1. 首页
2. 主席树
3. 本页

HDU 5919 Sequence II (主席树)

题目链接：点我~~

题意：给定一个序列n，有m次查询，每次查询一个区间[l,r]，求区间中每一种数在区间中第一次出现的位置的中位数，强制在线。

思路：

主席树维护后缀[i,n]，然后对于每次碰到一个数字，就把它以前的位置−1，新位置+1
主席树维护区间不同数字的个数k
然后寻找区间第k/2大呗
因为是维护的后缀，直接找root[l]里的第k/2大出现的位置就行了

当对某版本进行多次单点更新的时候，每次都需要新增一条路径，必须保证不对以往的版本造成影响。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define vecotr vector
typedef vector<int> VI;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int mod=1e9+7;
const double eps=1e-8;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
//LL powmod(LL a,LL b) {LL res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 200010;
const int M = MAXN * 100;
int n,q,tot;
int a[MAXN];
int T[MAXN],lson[M],rson[M],c[M];
int build(int l,int r)
{
    int root = tot++;
    c[root] = 0;
    if(l != r)
    {
        int mid = (l+r)>>1;
        lson[root] = build(l,mid);
        rson[root] = build(mid+1,r);
    }
    return root;
}
int update(int root,int pos,int val)
{
    int newroot = tot++, tmp = newroot;
    c[newroot] = c[root] + val;
    int l = 1, r = n;
    while(l < r)
    {
        int mid = (l+r)>>1;
        if(pos <= mid)
        {
            lson[newroot] = tot++;
            rson[newroot] = rson[root];
            newroot = lson[newroot];
            root = lson[root];
            r = mid;
        }
        else
        {
            rson[newroot] = tot++;
            lson[newroot] = lson[root];
            newroot = rson[newroot];
            root = rson[root];
            l = mid+1;
        }
        c[newroot] = c[root] + val;
    }
    return tmp;
}
int query(int root,int pos)
{
    int ret = 0;
    int l = 1, r = n;
    while(pos < r)
    {
        int mid = (l+r)>>1;
        if(pos <= mid)
        {
            r = mid;
            root = lson[root];
        }
        else
        {
            ret += c[lson[root]];
            root = rson[root];
            l = mid+1;
        }
    }
    return ret + c[root];
}
int finds(int x,int l,int r,int k)
{
    if(l == r) return l;
    int mid = l + r >> 1;
    if(c[lson[x]] >= k) return finds(lson[x],l,mid,k);
    else return finds(rson[x],mid+1,r,k-c[lson[x]]);
}

int ans[MAXN];

int main()
{
    int t;
    scanf("%d",&t);
    int casee=1;
    while(t--)
    {
        scanf("%d%d",&n,&q);
        tot = 0;
        for(int i = 1; i <= n; i++)
            scanf("%d",&a[i]);
        T[n+1] = build(1,n);
        map<int,int>mp;
        for(int i = n; i>= 1; i--)
        {
            if(mp.find(a[i]) == mp.end())
            {
                T[i] = update(T[i+1],i,1);
            }
            else
            {
                int tmp = update(T[i+1],mp[a[i]],-1);
                T[i] = update(tmp,i,1);
            }
            mp[a[i]] = i;
        }
        int last=0;
        int tol=0;
        while(q--)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            l=(l+last)%n+1;
            r=(r+last)%n+1;
            if(r<l) swap(l,r);
            last=query(T[l],r)+1>>1;
            last=finds(T[l],1,n,last);
            ans[tol++]=last;
        }
        printf("Case #%d:",casee++);
        int len=tol;
        for(int i=0; i<tol; ++i)
            printf(" %d",ans[i]);
        puts("");
    }
    return 0;
}

/*
2
5 2
3 3 1 5 4
2 2
4 4
5 2
2 5 2 1 2
2 3
2 4
*/