首页 > 代码库 > HDU 5919 Sequence II（主席树+逆序思想）
HDU 5919 Sequence II（主席树+逆序思想）
Sequence II
Time Limit: 9000/4500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1422 Accepted Submission(s): 362
Problem Description
Mr. 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.
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.
Input
In 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:
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}
Output
You 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.
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 Output
Case #1: 3 3Case #2: 3 1
Hint
题目链接：HDU 5919
区间内的求和+第K小的结合题，难点就在用倒序的方式维护第一次出现的位置，每一颗树都是维护原序列i~n的后缀，从后往前更新的时候把每一个位置都更新掉，这样第一次出现的位置就是最新的位置，然后统计的时候直接统计L~n即可，因为在p序列中L~R与L~n是等效的，后面多出现的无任何影响。
代码：
#include <stdio.h>#include <iostream>#include <algorithm>#include <cstdlib>#include <sstream>#include <cstring>#include <bitset>#include <string>#include <deque>#include <stack>#include <cmath>#include <queue>#include <set>#include <map>using namespace std;#define INF 0x3f3f3f3f#define CLR(arr,val) memset(arr,val,sizeof(arr))#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)typedef pair<int,int> pii;typedef long long LL;const double PI=acos(-1.0);const int N=2e5+7;struct seg{ int lson,rson; int cnt; inline void init() { lson=rson=cnt=0; }};seg T[N*40];int root[N],tot;int arr[N],ans[N],pre[N];void init(int n){ CLR(root,0); tot=0; T[n+1].init(); ans[0]=0; CLR(pre,-1);}inline void update(int &cur,int ori,int l,int r,int pos,int v){ cur=++tot; T[cur]=T[ori]; T[cur].cnt+=v; if(l==r) return ; int mid=MID(l,r); if(pos<=mid) update(T[cur].lson,T[ori].lson,l,mid,pos,v); else update(T[cur].rson,T[ori].rson,mid+1,r,pos,v);}int query(int S,int E,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr) return T[E].cnt-T[S].cnt; else { int mid=MID(l,r); if(qr<=mid) return query(T[S].lson,T[E].lson,l,mid,ql,qr); else if(ql>mid) return query(T[S].rson,T[E].rson,mid+1,r,ql,qr); else return query(T[S].lson,T[E].lson,l,mid,ql,mid)+query(T[S].rson,T[E].rson,mid+1,r,mid+1,qr); }}int findkth(int S,int E,int l,int r,int k){ if(l==r) return l; else { int cnt=T[T[E].lson].cnt-T[T[S].lson].cnt; int mid=MID(l,r); if(k<=cnt) return findkth(T[S].lson,T[E].lson,l,mid,k); else return findkth(T[S].rson,T[E].rson,mid+1,r,k-cnt); }}int main(void){ int tcase,n,m,i,l,r,L,R; scanf("%d",&tcase); for (int q=1; q<=tcase; ++q) { scanf("%d%d",&n,&m); init(n); for (i=1; i<=n; ++i) scanf("%d",&arr[i]); int temp_rt=0; for (i=1; i<=1; ++i) { if(pre[arr[i]]==-1) update(root[i],root[i+1],1,n,i,1); else { update(temp_rt,root[i+1],1,n,pre[arr[i]],-1); update(root[i],temp_rt,1,n,i,1); } pre[arr[i]]=i; } for (i=1; i<=m; ++i) { scanf("%d%d",&l,&r); L=(l+ans[i-1])%n+1; R=(r+ans[i-1])%n+1; if(L>R) swap(L,R); int D=query(root[n+1],root[L],1,n,L,R); ans[i]=findkth(root[n+1],root[L],1,n,(D+1)/2); } printf("Case #%d:",q); for (i=1; i<=m; ++i) printf(" %d",ans[i]); putchar(‘\n‘); } return 0;}HDU 5919 Sequence II（主席树+逆序思想）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。