hdu 5919 Sequence II(主席樹)

2019-11-08 02:29:26

字體：大中小

來源：轉載

供稿：網友

Sequence II

Time Limit: 9000/4500 MS (java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 1600 Accepted Submission(s): 405PRoblem DescriptionMr. Frog has an integer sequence of length n, which can be denoted as a1,a2,?,an There are m queries.In the i-th query, you are given two integers li and ri. Consider the subsequence ali,ali+1,ali+2,?,ari.We can denote the positions(the positions according to the original sequence) where an integer appears first in this subsequence as p(i)1,p(i)2,?,p(i)ki (in ascending order, i.e.,p(i)1<p(i)2<?<p(i)ki).Note that ki is the number of different integers in this subsequence. You should output p(i)?ki2?for the i-th query. InputIn the first line of input, there is an integer T (T≤2) denoting the number of test cases.Each test case starts with two integers n (n≤2×105) and m (m≤2×105). There are n integers in the next line, which indicate the integers in the sequence(i.e., a1,a2,?,an,0≤ai≤2×105).There are two integers li and ri in the following m lines.However, Mr. Frog thought that this problem was too young too simple so he became angry. He modified each query to l‘i,r‘i(1≤l‘i≤n,1≤r‘i≤n). As a result, the problem became more exciting.We can denote the answers as ans1,ans2,?,ansm. Note that for each test case ans0=0.You can get the correct input li,ri from what you read (we denote them as l‘i,r‘i)by the following formula:li=min{(l‘i+ansi?1) mod n+1,(r‘i+ansi?1) mod n+1}ri=max{(l‘i+ansi?1) mod n+1,(r‘i+ansi?1) mod n+1} OutputYou should output one single line for each test case.For each test case, output one line “Case #x: p1,p2,?,pm”, where x is the case number (starting from 1) and p1,p2,?,pm is the answer. Sample Input

25 23 3 1 5 42 24 45 22 5 2 1 22 32 4 Sample OutputCase #1: 3 3Case #2: 3 1Hint  Source2016中國大學生程序設計競賽（長春）-重現賽 
題意：有長度為n的序列，強制在線詢問[l,r] 這段區間中所有不同數出現的第一個位置，按照位置從小到大排完序以后的中間（向上取整）的那個位置是多少？即把各個數字在這個區間中第一次出現的位置記作 p1,p2,?,pk ，滿足 p1<p2<?<pk ，求 p?k2? 
學完主席樹就想過來把這題過了，拖到了現在。這是我參加的第一場區預賽-長春賽站現場賽的題，當時因為不會這道而沒進銀牌區。這題也是類似spoj-dquery(感覺這題是主席樹精髓啊==)，其實會dquery這道題非常容易。#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<queue>#include<stack>#include<map>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define fi first#define se secondtypedef vector<int> VI;typedef long long ll;typedef pair<int,int> PII;const int inf=0x3fffffff;const ll mod=1000000007;const int maxn=2e5+100;struct node{    int l,r,sum;}T[maxn*40];int root[maxn];int cnt;void update(int l,int r,int& x,int y,int pos,int val){    T[++cnt]=T[y],x=cnt,T[x].sum+=val;    if(l==r) return;    int m=(l+r)/2;    if(pos<=m) update(l,m,T[x].l,T[y].l,pos,val);    else update(m+1,r,T[x].r,T[y].r,pos,val);}int query(int l,int r,int x,int pos){    if(l==r) return T[x].sum;    int m=(l+r)/2;    if(pos<=m) return query(l,m,T[x].l,pos);    else return T[T[x].l].sum+query(m+1,r,T[x].r,pos);}int query1(int l,int r,int x,int k){    if(l==r) return l;    int m=(l+r)/2;    if(k>T[T[x].l].sum) return query1(m+1,r,T[x].r,k-T[T[x].l].sum);    else return query1(l,m,T[x].l,k);}int a[maxn];map<int,int> mp;int main(){    int cas;    scanf("%d",&cas);    int kase=0;    while(cas--)    {        cnt=0;        int n,m;        scanf("%d%d",&n,&m);        memset(T,0,sizeof(T));        memset(root,0,sizeof(root));        mp.clear();        rep(i,1,n+1) scanf("%d",&a[i]);        int ans=0,l,r;        per(i,1,n+1)        {            if(mp.find(a[i])==mp.end())            {                mp[a[i]]=i;                update(1,n,root[i],root[i+1],i,1);            }            else            {                update(1,n,root[i],root[i+1],mp[a[i]],-1);                update(1,n,root[i],root[i],i,1);                mp[a[i]]=i;            }        }        printf("Case #%d: ",++kase);        while(m--)        {            scanf("%d%d",&l,&r);            l=(l+ans)%n+1,r=(r+ans)%n+1;            if(l>r) swap(l,r);            int k=query(1,n,root[l],r);            k=(k+1)/2;            ans=query1(1,n,root[l],k);            printf("%d",ans);            if(m) printf(" ");        }        puts("");    }    return 0;}