Mr. Frog has an integer sequence of length n, which can be denoted as a1,a2,?,ana1,a2,?,an There are m queries.

In the i-th query, you are given two integers lili and riri. Consider the subsequence ali,ali+1,ali+2,?,ariali,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)kip1(i),p2(i),?,pki(i) (in ascending order, i.e.,p(i)1<p(i)2<?<p(i)kip1(i)<p2(i)<?<pki(i)).

Note that kiki is the number of different integers in this subsequence. You should output p(i)?ki2?p?ki2?(i)for the i-th query.
Input
In the first line of input, there is an integer T (T≤2T≤2) denoting the number of test cases.

Each test case starts with two integers n (n≤2×105n≤2×105) and m (m≤2×105m≤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×105a1,a2,?,an,0≤ai≤2×105).

There are two integers lili and riri 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)li‘,ri‘(1≤li‘≤n,1≤ri‘≤n). As a result, the problem became more exciting.

We can denote the answers as ans1,ans2,?,ansmans1,ans2,?,ansm. Note that for each test case ans0=0ans0=0.

You can get the correct input li,rili,ri from what you read (we denote them as l‘i,r‘ili‘,ri‘)by the following formula:
li=min{(l‘i+ansi?1) mod n+1,(r‘i+ansi?1) mod n+1}
li=min{(li‘+ansi?1) mod n+1,(ri‘+ansi?1) mod n+1}

ri=max{(l‘i+ansi?1) mod n+1,(r‘i+ansi?1) mod n+1}
ri=max{(li‘+ansi?1) mod n+1,(ri‘+ansi?1) mod n+1}
Output
You should output one single line for each test case.

For each test case, output one line “Case #x: p1,p2,?,pmp1,p2,?,pm”, where x is the case number (starting from 1) and p1,p2,?,pmp1,p2,?,pm is the answer.
Sample Input
2
5 2
3 3 1 5 4
2 2
4 4
5 2
2 5 2 1 2
2 3
2 4
Sample Output
Case #1: 3 3
Case #2: 3 1

題意：長(zhǎng)度為n的序列和m次詢問(wèn)，每次詢問(wèn)是l到r之間按每個(gè)數(shù)第一次出現(xiàn)的位置排序，問(wèn)中位數(shù)的位置是什么。
思路：因?yàn)槲覀円涗浢總€(gè)數(shù)第一次出現(xiàn)的位置。之前bzoj有一個(gè)類似的題，bzoj題目的網(wǎng)址
但是這個(gè)題需要記錄第一次出現(xiàn)的位置，所以我們要從后往前遍歷數(shù)組，如果之前出現(xiàn)過(guò)，就將之前的位置清空，在當(dāng)前位置記錄下來(lái)。這個(gè)操作在主席樹里操作。對(duì)于l~r，我們可以算出來(lái)這段區(qū)間里有多少個(gè)數(shù)，然后就在轉(zhuǎn)化成了求區(qū)間l ~r內(nèi)第k個(gè)數(shù)的位置。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=2e5+100; struct node{int l;int r;int sum; }p[maxx*40]; int a[maxx]; int n,m,tot,root[maxx];inline int build(int l,int r) {int cur=++tot;p[cur].sum=0;if(l==r) return cur;int mid=l+r>>1;p[cur].l=build(l,mid);p[cur].r=build(mid+1,r);return cur; } inline int update(int rot,int l,int r,int pos,int v) {int cur=++tot;p[cur]=p[rot];p[cur].sum+=v;if(l==r) return cur;int mid=l+r>>1;if(pos<=mid) p[cur].l=update(p[rot].l,l,mid,pos,v);else p[cur].r=update(p[rot].r,mid+1,r,pos,v);return cur; } inline int queryI(int rot,int l,int r,int L,int R)//求區(qū)間l~r的數(shù)字種類數(shù) {if(l<=L&&R<=r) return p[rot].sum;int mid=L+R>>1;int sum=0;if(l<=mid) sum+=queryI(p[rot].l,l,r,L,mid);if(mid<r) sum+=queryI(p[rot].r,l,r,mid+1,R);return sum; } inline int queryII(int rot,int L,int R,int num)//求第num個(gè)數(shù) {if(L==R) return L;int ret=p[p[rot].l].sum;int mid=L+R>>1;if(num<=ret) return queryII(p[rot].l,L,mid,num);else return queryII(p[rot].r,mid+1,R,num-ret); } int main() {int t,k=0,l,r;scanf("%d",&t);while(t--){tot=0;scanf("%d%d",&n,&m);map<int,int> mp;for(int i=1;i<=n;i++) scanf("%d",&a[i]);root[n+1]=build(1,n);for(int i=n;i>=1;i--){if(mp.find(a[i])==mp.end()) root[i]=update(root[i+1],1,n,i,1);else{int x=update(root[i+1],1,n,mp[a[i]],-1);//x是將之前標(biāo)記消了的版本，第i個(gè)版本在x的基礎(chǔ)上建立起來(lái)root[i]=update(x,1,n,i,1);}mp[a[i]]=i;}printf("Case #%d:",++k);int ans=0;while(m--){scanf("%d%d",&l,&r);l=(l+ans)%n+1;r=(r+ans)%n+1;if(l>r) swap(l,r);int kk=(queryI(root[l],l,r,1,n)+1)>>1;ans=queryII(root[l],1,n,kk);printf(" %d",ans);}printf("\n");}return 0; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的Sequence II HDU - 5919（主席树）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。