分块

分块

BZOJ 2724

在线维护区间的众数。

ac code

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
int maxn,m,n,tot,T,mode[1000][1000],last[40010],
a[40010],ord[40010],L[1000],R[1000],cnt[40010];
vector<int> plc[40010];
vector<int>::iterator i1,i2;
int main()
{
int i,j,k,p,q,x,y,z,K,ans,l,r,ll,rr,ans_cnt,xx;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
scanf("%d",&a[i]),ord[i]=a[i];
sort(ord+1,ord+n+1);
maxn=unique(ord+1,ord+n+1)-ord-1;
for (i=1;i<=n;i++)
a[i]=lower_bound(ord+1,ord+maxn+1,a[i])-ord;
tot=sqrt(n*log(n)/log(2));
T=n/tot;
for (i=1;i<=tot;i++)
{
L[i]=R[i-1]+1;
if (i==tot) R[i]=n;
else R[i]=L[i]+T-1;
}
for (i=1;i<=tot;i++)
{
memset(cnt,0,sizeof(cnt));
for (j=i;j<=tot;j++)
{
mode[i][j]=mode[i][j-1];
for (k=L[j];k<=R[j];k++)
{
cnt[a[k]]++;
if (cnt[a[k]]>cnt[mode[i][j]]||
(cnt[a[k]]==cnt[mode[i][j]]&&a[k]<mode[i][j]))
mode[i][j]=a[k];
}
}
}
for (i=1;i<=n;i++)
plc[a[i]].push_back(i);
ans=0;
for (K=1;K<=m;K++)
{
scanf("%d%d",&l,&r);
l=(l+ans-1)%n+1;
r=(r+ans-1)%n+1;
if (l>r) swap(l,r);
ll=1;
while (ll<=tot&&L[ll]<l) ll++;
rr=tot;
while (rr&&R[rr]>r) rr--;
if (ll>rr)
{
ans=0;
ans_cnt=-1;
for (i=l;i<=r;i++)
{
i1=lower_bound(plc[a[i]].begin(),plc[a[i]].end(),l);
i2=upper_bound(plc[a[i]].begin(),plc[a[i]].end(),r);
xx=i2-i1;
if (xx>ans_cnt||(xx==ans_cnt&&a[i]<ans))
{
ans=a[i];
ans_cnt=xx;
}
}
ans=ord[ans];
printf("%d\n",ans);
continue;
}
ans=mode[ll][rr];
i1=lower_bound(plc[ans].begin(),plc[ans].end(),l);
i2=upper_bound(plc[ans].begin(),plc[ans].end(),r);
ans_cnt=i2-i1;
for (i=l;i<L[ll];i++)
{
i1=lower_bound(plc[a[i]].begin(),plc[a[i]].end(),l);
i2=upper_bound(plc[a[i]].begin(),plc[a[i]].end(),r);
xx=i2-i1;
if (xx>ans_cnt||(xx==ans_cnt&&a[i]<ans))
{
ans=a[i];
ans_cnt=xx;
}
}
for (i=R[rr]+1;i<=r;i++)
{
i1=lower_bound(plc[a[i]].begin(),plc[a[i]].end(),l);
i2=upper_bound(plc[a[i]].begin(),plc[a[i]].end(),r);
xx=i2-i1;
if (xx>ans_cnt||(xx==ans_cnt&&a[i]<ans))
{
ans=a[i];
ans_cnt=xx;
}
}
ans=ord[ans];
printf("%d\n",ans);
}
}

未解决的问题

文章目录
  1. 1. BZOJ 2724
    1. 1.1. ac code
  2. 2. 未解决的问题
{{ live2d() }}