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;}