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.

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:

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.

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

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