1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
#include <bits/stdc++.h>
#define mp make_pair
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define lowbit(x) ((x)&(-(x)))
#define cls(x) memset(x,0,sizeof(x))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif
using namespace std;
mt19937 rnd(19260817);
const int inf=0x3f3f3f3f;
typedef long long LL;
typedef pair<int,int> pii;
template<typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {if (ch=='-') flag=true;ch=getchar();}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template<typename T,typename U>
inline void read(T &x,U &y){read(x);read(y);}
template<typename T,typename U,typename V>
inline void read(T &x,U &y,V &z){read(x);read(y);read(z);}
const int maxn=200001,maxvalue=200000;
struct node
{
node *l,*r;
int value;
node():l(0),r(0),value(0){}
node(node *ll,node *rr):l(ll),r(rr),value((ll?ll->value:0)+(rr?rr->value:0)){}
node(int vv):l(0),r(0),value(vv){}
};
node *root[maxn];
char memorypool[maxn*sizeof(node)*36];//1 char=1 byte
char *memorypoolptr=memorypool;
inline void* myalloc(size_t size)
{
return (memorypoolptr+=size)-size;
}
#define newnode new (myalloc(sizeof(node))) node
node* insert(node *x,int k,int L=1,int R=maxvalue)
{
if (L==R) return newnode(x?x->value+1:1);
int mid=(L+R)>>1;
if (k<=mid) return newnode(insert(x?x->l:0,k,L,mid),x?x->r:0);
else return newnode(x?x->l:0,insert(x?x->r:0,k,mid+1,R));
}
node* erase(node *x,int k,int L=1,int R=maxvalue)
{
if (L==R) return nullptr;
int mid=(L+R)>>1;
if (k<=mid) return newnode(erase(x->l,k,L,mid),x->r);
else return newnode(x->l,erase(x->r,k,mid+1,R));
}
int kth(node *x,int k,int L=1,int R=maxvalue)
{
if (L==R) return L;
int mid=(L+R)>>1;
if (k<=(x->l?x->l->value:0)) return kth(x->l,k,L,mid);
else return kth(x->r,k-(x->l?x->l->value:0),mid+1,R);
}
int kth(node *x,node *y,int k,int L=1,int R=maxvalue)
{
if (L==R) return L;
if (!x) return kth(y,k,L,R);
int mid=(L+R)>>1,temp=(y->l?y->l->value:0)-(x->l?x->l->value:0);
if (k<=temp) return kth(x->l,y->l,k,L,mid);
else return kth(x->r,y->r,k-temp,mid+1,R);
}
int T,n,m,a[maxn],last[maxn],ans[maxn];
void clear()
{
memset(memorypool,0,sizeof(memorypool));
memorypoolptr=memorypool;
}
int main()
{
cout<<sizeof(int)<<endl;
cout<<((maxn*sizeof(node)*36)>>10)<<endl;
read(T);
rep(kase,1,T)
{
printf("Case #%d:",kase);
memset(last,0,sizeof(last));
read(n,m);
rep(i,1,n) read(a[i]);
root[n+1]=newnode();
per(i,n,1)
{
root[i]=last[a[i]]?erase(root[i+1],last[a[i]]):root[i+1];
root[i]=insert(root[i],i);
last[a[i]]=i;
}
int lastans=0;
rep(i,1,m)
{
int l,r;
read(l,r);
l=(l+lastans)%n+1,r=(r+lastans)%n+1;
if (l>r) swap(l,r);
int num=root[l]->value-root[r+1]->value;
ans[i]=(lastans=kth(root[r+1],root[l],(num+1)/2));
}
rep(i,1,m) printf(" %d",ans[i]);
putchar('\n');
clear();
}
return 0;
}
|