--------一道 做了好久好久好久好久好久好久好久的题
（洛谷4168）
题意： 给定一个序列 多次询问
每次询问一个区间 求这个区间里的众数
算法必须是在线的
思路：众数不具有区间可加性 于是只能分块了 （事实上分块真的很慢,最后也是卡过去的）
-关于分多少块的问题 实践证明分len=30 是很合适的（我也不知道为什么 是dalao告诉我的 qwq）
对于每个询问[l,r] 设l处于第x块 r处于第y块
那么此区间的众数只可能是 第x+1到第y-1块中间的整块部分的 或是x,y块中包含于询问区间的不足整块部分的
然后采取分块一般套路 ：“大段维护，局部朴素”
此题大段中的答案可以初始化得出
但是“局部朴素”也还是要优化的（不要太朴素了啦）
定义一个vector d[] : d[i]中存第i个数出现过的位置
假设 d[1]={1,4,7,8,9} 那么[3,7]区间内第一个数的出现次数就为 3-2+1=2 这里还要用到二分
还有要注意的是 序列长度为n 但是序列元素可不是1-n之间的数 可能会非常的大 这里还要用到离散化
（代码有一点bug 开O2会RE）
code
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 #include<cmath>
5 #include<cstring>
6 #include<vector>
7 #define yes(i,a,b) for(register int i=a;i<=b;i++)
8 #define M 50100
9 #define N 3000
10 using namespace std;
11 int read()
12 {
13 int x=0,y=1;char c;c=getchar();
14 while(c<'0'||c>'9') {if(c=='-') y=-1;c=getchar();}
15 while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-'0';c=getchar();} return x*y;
16 }
17 int n,m,len,kn,l_ans;
18 int b[M],c[M],id[M],tot[M],f[N][N];
19 vector<int> d[M];
20 struct node {int val,pos;} a[M];
21 bool cmp(node x,node y) {return x.val<y.val;}
22 void init1()
23 {
24 sort(a+1,a+n+1,cmp);int num=0;
25 yes(i,1,n)
26 {
27 if(a[i].val!=a[i-1].val) c[a[i].pos]=++num,b[num]=a[i].val;
28 else c[a[i].pos]=num;
29 }
30 yes(i,1,n) d[c[i]].push_back(i);
31 }
32 void init2(int x)
33 {
34 int maxn=0,aans=0;
35 memset(tot,0,sizeof(tot));
36 yes(i,x,n)
37 {
38 tot[c[i]]++;
39 if(tot[c[i]]>maxn||(tot[c[i]]==maxn&&c[i]<aans))
40 {maxn=tot[c[i]];aans=c[i];}
41 f[id[x]][id[i]]=aans;
42 }
43 }
44 int efl(int x,int y)
45 {
46 int l=0,r=d[x].size()-1,aans=0;
47 while(l<=r)
48 {
49 int mid=(l+r)/2;
50 if(d[x][mid]>=y) aans=mid,r=mid-1;
51 else l=mid+1;
52 }
53 return aans;
54 }
55 int efr(int x,int y)
56 {
57 int l=0,r=d[x].size()-1,aans=0;
58 while(l<=r)
59 {
60 int mid=(l+r)/2;
61 if(d[x][mid]<=y) aans=mid,l=mid+1;
62 else r=mid-1;
63 }
64 return aans;
65 }
66 int query(int x,int y)
67 {
68 if(x>y) swap(x,y);
69 int p=id[x],q=id[y],aans=0,maxn=0;
70 if(q<=p+1)
71 {
72 yes(i,x,y)
73 {
74 int l,r;
75 l=efl(c[i],x);
76 r=efr(c[i],y);
77 if((r-l+1>maxn)||(r-l+1==maxn&&c[i]<aans))
78 {aans=c[i];maxn=r-l+1;}
79 }
80 }
81 else
82 {
83 aans=f[p+1][q-1];maxn=efr(aans,y)-efl(aans,x)+1;
84 yes(i,x,p*len)
85 {
86 int l,r;
87 l=efl(c[i],x);
88 r=efr(c[i],y);
89 if((r-l+1>maxn)||(r-l+1==maxn&&c[i]<aans))
90 {aans=c[i];maxn=r-l+1;}
91 }
92 yes(i,(q-1)*len+1,y)
93 {
94 int l,r;
95 l=efl(c[i],x);
96 r=efr(c[i],y);
97 if((r-l+1>maxn)||(r-l+1==maxn&&c[i]<aans))
98 {aans=c[i];maxn=r-l+1;}
99 }
100 }
101 return aans;
102 }
103 int main()
104 {
105 //freopen("1.in","r",stdin);
106 //freopen("1.out","w",stdout);
107 n=read();m=read();len=30;kn=n/len;
108 yes(i,1,n) a[i].val=read(),a[i].pos=i;
109 yes(i,1,n) yes(j,(i-1)*len+1,i*len) id[j]=i;
110 if(kn*len<n) yes(i,kn*len+1,n) id[i]=kn+1;kn++;
111 init1();
113 yes(i,1,kn) init2((i-1)*len+1);
116 yes(i,1,m)
117 {
118 int l=read(),r=read();
119 l=(l+l_ans-1)%n+1;r=(r+l_ans-1)%n+1;
120 l_ans=b[query(l,r)];
121 printf("%d
",l_ans);
122 }
123 return 0;
124 }