bzoj2724 [Violet 6]蒲公英 分块

蒲公英 分块"/>

bzoj2724 [Violet 6]蒲公英 分块

Description

求区间众数，强制在线

Code

一开始yy了一个分块线段树合并的sb做法。。

如果不强制在线的话可以回滚莫队，强制在线考虑分块暴力
先离散。分块中常用的技巧是对块做各种前缀和。本题我们记s[i,j]表示前i块j出现的次数，记r[i,j]为i到j块的答案
对于询问[l,r]，我们把在两侧零散出现的数字在中间整块中出现的次数塞进桶里（绕

看图，我们把红色部分出现的数字在蓝色部分中出现的次数塞进一个桶里面，显然只有红色部分的数字出现次数会发生变化
这样我们就可以在修改的时候顺便求答案了
一开始非常sb地把离散的序号输出了gg

Code

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#define rep(i,st,ed) for (register int i=st;i<=ed;++i)
#define fill(x,t) memset(x,t,sizeof(x))const int N=40005;int bel[N],st[N],ed[N],a[N];
int cnt[205][N],rec[205][205],b[N];
int wjp[N];int read() {int x=0,v=1; char ch=getchar();for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());return x*v;
}int main(void) {int n=read(),m=read();int B=sqrt(n);rep(i,1,n) {a[i]=b[i]=read();bel[i]=(i-1)/B+1;if (!st[bel[i]]) st[bel[i]]=i;ed[bel[i]]=i;}std:: sort(b+1,b+n+1);int size=std:: unique(b+1,b+n+1)-b-1;rep(i,1,n) a[i]=std:: lower_bound(b+1,b+size+1,a[i])-b;rep(i,1,bel[n]) {rep(j,st[i],ed[i]) cnt[i][a[j]]++;rep(j,1,n) cnt[i][j]+=cnt[i-1][j];}rep(i,1,bel[n]) {rep(k,st[i],ed[i]) {if (cnt[i][a[k]]-cnt[i-1][a[k]]>cnt[i][rec[i][i]]-cnt[i-1][rec[i][i]]) {rec[i][i]=a[k];} else if (cnt[i][a[k]]-cnt[i-1][a[k]]==cnt[i][rec[i][i]]-cnt[i-1][rec[i][i]]&&a[k]<rec[i][i]) {rec[i][i]=a[k];}}rep(j,i+1,bel[n]) {rec[i][j]=rec[i][j-1];rep(k,st[j],ed[j]) {if (cnt[j][a[k]]-cnt[i-1][a[k]]>cnt[j][rec[i][j]]-cnt[i-1][rec[i][j]]) {rec[i][j]=a[k];} else if (cnt[j][a[k]]-cnt[i-1][a[k]]==cnt[j][rec[i][j]]-cnt[i-1][rec[i][j]]&&a[k]<rec[i][j]) {rec[i][j]=a[k];}}}}for (int lastans=0;m--;) {int x=read(),y=read();int l=(x+lastans-1)%n+1,r=(y+lastans-1)%n+1;if (r<l) std:: swap(l,r);lastans=0;int bl=bel[l],br=bel[r];if (br-bl<=1) {rep(i,l,r) {++wjp[a[i]];if (wjp[a[i]]>wjp[lastans]) lastans=a[i];else if (wjp[a[i]]==wjp[lastans]&&a[i]<lastans) lastans=a[i];}rep(i,l,r) wjp[a[i]]=0;lastans=b[lastans];printf("%d\n", lastans);} else {rep(i,l,ed[bl]) wjp[a[i]]=cnt[br-1][a[i]]-cnt[bl][a[i]];rep(i,st[br],r) wjp[a[i]]=cnt[br-1][a[i]]-cnt[bl][a[i]];lastans=rec[bl+1][br-1];wjp[lastans]=cnt[br-1][lastans]-cnt[bl][lastans];rep(i,l,ed[bl]) {++wjp[a[i]];if (wjp[a[i]]>wjp[lastans]) lastans=a[i];else if (wjp[a[i]]==wjp[lastans]&&a[i]<lastans) lastans=a[i];}rep(i,st[br],r) {++wjp[a[i]];if (wjp[a[i]]>wjp[lastans]) lastans=a[i];else if (wjp[a[i]]==wjp[lastans]&&a[i]<lastans) lastans=a[i];}lastans=b[lastans];printf("%d\n", lastans);rep(i,l,ed[bl]) wjp[a[i]]=0;rep(i,st[br],r) wjp[a[i]]=0;wjp[rec[bl+1][br-1]]=0;}}return 0;
}