题目描述
在乡下的小路旁种着许多蒲公英，而我们的问题正是与这些蒲公英有关。
为了简化起见，我们把所有的蒲公英看成一个长度为n的序列((a_1,a_2..a_n))，其中 (a_i)为一个正整数，表示第i棵蒲公英的种类编号。
而每次询问一个区间 [l,r]，你需要回答区间里出现次数最多的是哪种蒲公英，如果有若干种蒲公英出现次数相同，则输出种类编号最小的那个。
注意，你的算法必须是在线的
Solution
分块
但是要维护些什么呢？
假设我们已经对原序列进行了分块，对于一个询问([l,r]),我们所寻求的答案很大概率出现在中间的完整的块中，否则，它就一定在两边离散的数中出现过，而这些数是不超过(2 sqrt n)的。
所以，我们只要维护一个 (ans[i][j])表示第i块到第j块的答案，这个初始化时(O(n sqrt n))的。
还有就是每个数的出现次数，(num[x][i])表示数x在前i块出现的次数
不过，如果打得不够优美的话是要TLE的。。。
Code
#include<bits/stdc++.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
#define MN 40005
int N,M,col[MN],fcol[MN],tt[MN],tot;
int T,pos[MN],a[205][205],num[MN][205],L[MN],R[MN];
inline void init()
{
register int i,j;
std::sort(tt+1,tt+tot+1);
tot=std::unique(tt+1,tt+tot+1)-tt-1;
for(i=1;i<=N;++i)
{
int p=col[i];
col[i]=std::lower_bound(tt+1,tt+tot+1,col[i])-tt;
fcol[col[i]]=p;
}
for(i=N;i>=1;--i)
{
if(pos[i]==pos[i-1]) continue;
L[pos[i]]=i;
register int ans=0,bl=pos[i];
for(j=i;j<=N;++j)
{
num[col[j]][bl]++;
if(num[col[j]][bl]>num[ans][bl]) ans=col[j];
if(num[col[j]][bl]==num[ans][bl]&&col[j]<ans) ans=col[j];
if(pos[j]!=pos[j+1]) R[pos[j]]=j,a[pos[i]][pos[j]]=ans;
}
}
memset(num,0,sizeof num);
for(i=1;i<=N;++i)
{
num[col[i]][pos[i]]++;
if(pos[i]!=pos[i+1]&&i!=N)
for(j=1;j<=tot;++j) num[j][pos[i]+1]=num[j][pos[i]];
}
}
int tmp[MN];
bool vis[MN];
inline int query(int l,int r)
{
memset(tmp,0,sizeof tmp);
memset(vis,0,sizeof vis);
register int i,ll,rr,ans=0;
ll=pos[l]+(l!=L[pos[l]]);
rr=pos[r]-(r!=R[pos[r]]);
if(l!=L[pos[l]])
for(i=l;i<=R[pos[l]];++i)
{
tmp[col[i]]++;
if(!vis[col[i]]) vis[col[i]]=true,tmp[col[i]]+=num[col[i]][rr]-num[col[i]][ll-1];
if(tmp[col[i]]>tmp[ans]||(tmp[ans]==tmp[col[i]]&&col[i]<ans)) ans=col[i];
}
if(r!=R[pos[r]])
for(i=L[pos[r]];i<=r;++i)
{
tmp[col[i]]++;
if(!vis[col[i]]) vis[col[i]]=true,tmp[col[i]]+=num[col[i]][rr]-num[col[i]][ll-1];
if(tmp[col[i]]>tmp[ans]||(tmp[ans]==tmp[col[i]]&&col[i]<ans)) ans=col[i];
}
register int o=a[ll][rr],numo=num[o][rr]-num[o][ll-1];
// printf("ll=%d rr=%d o=%d
",ll,rr,o);
if(!vis[o]&&(numo>tmp[ans]||(numo==tmp[ans]&&o<ans))) ans=o;
return fcol[ans];
}
int main()
{
// freopen("testdata.in","r",stdin);
// freopen("tesedata.out","w",stdout);
N=read();M=read();
register int i;T=(int)(sqrt(N));
for(i=1;i<=N;++i) col[i]=read(),pos[i]=(i-1)/T+1,tt[++tot]=col[i];
init();
int l,r,x=0;
// L=(l0-1+x) mod n +1,R = (r0-1 + x ) mod n +1
while(M--)
{
l=read();r=read();
l=(l-1+x)%N+1,r=(r-1+x)%N+1;
if(l>r) std::swap(l,r);
// printf("%d %d
",l,r);
x=query(l,r);
printf("%d
",x);
}
return 0;
}
那么，分块还有什么用呢
其实，有些时候，我们可以通过只维护块的信息来省省空间
比如求多维偏序的问题，我们考虑对每一维分别排序，然后分块，每个块维护一个下标集合表示该维比这个块小的所有下标
那么按照分块的老套路，对于每个数查询该维比自己小的数的集合是(O(n sqrt n))的
剩下的就是求每个维的集合的并了?如果你回bitset，它可以做到 (O(n^2 k/32)) k是维度数量。。。
Blog来自PaperCloud，未经允许，请勿转载，TKS！