【BZOJ 2724】 [Violet 6]蒲公英

2724: [Violet 6]蒲公英Time Limit:40 SecMemory Limit:512 MBSubmit:970Solved:319[Submit][Status][Discuss]Description

Input

修正一下

l = (l_0 + x – 1) mod n + 1, r = (r_0 + x – 1) mod n + 1

Output

Sample Input

6 31 2 3 2 1 2 1 5 3 6 1 5

Sample Output

12 1

HINT

修正下：

n <= 40000, m <= 50000

Source

Vani原创

分块。

首先把n个数分成sqrt(n)块，预处理出每一块的开头到他后面所有位置的答案，，O(n*sqrt(n))。

对于每一个询问(l,r)，我们把它分割成(l,L-1),(L,r)，其中L是一个块的开始。

后者已经预处理过了，前者暴力枚举，用二分法计算他在(l,r)的出现次数，更新答案。

（为了求出现次数，我们需要把a[i]离散化，对于每个a[i]按照位置从左到右的顺序记录下来，然后就可以二分了）

时间复杂度O(m*sqrt(n)*logn+n*sqrt(n))

#include <iostream>#include <cstring>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <vector>#define pb push_back#define M 40005using namespace std;int belong[M],cnt[M],n,m,tot,B,num;vector<int> v[M];struct data{int hash,id;}a[M];struct Ans{int ans,id;}f[205][M];struct Help{int pos,v;}b[M];void read(int &tmp){tmp=0;char ch=getchar();int fu=1;for (;ch<'0'||ch>'9';ch=getchar())if (ch=='-') fu=-1;for (;ch>='0'&&ch<='9';ch=getchar())tmp=tmp*10+ch-'0';tmp*=fu;}void Prepare(){for (int i=1;i<=num;i++){for (int j=(i-1)*B+1;j<=i*B;j++)belong[j]=i;for (int j=1;j<=tot;j++)cnt[j]=0;Ans x;x.ans=0,x.id=0;for (int j=(i-1)*B+1;j<=n;j++){int h=a[j].hash;cnt[h]++;if (cnt[h]>x.ans||(cnt[h]==x.ans&&a[j].id<x.id))x.ans=cnt[h],x.id=a[j].id;f[i][j]=x;}}}bool cmp(Help a,Help b){if (b.v==a.v) return a.pos<b.pos;return a.v<b.v;}int Findd(int k,int l,int r,int w){if (l==r) return l;int m=(l+r)>>1;if (v[k][m]>w&&m-1>=0&&v[k][m-1]>=w) return Findd(k,l,m-1,w);if (v[k][m]<w) return Findd(k,m+1,r,w);return m;}int Findx(int k,int l,int r,int w){if (l==r) return l;int m=(l+r)>>1;if (v[k][m]<w&&m+1<v[k].size()&&v[k][m+1]<=w) return Findx(k,m+1,r,w);if (v[k][m]>w) return Findx(k,l,m-1,w);return m;}int Get(int k,int l,int r){int s=v[k].size();return Findx(k,0,s-1,r)-Findd(k,0,s-1,l)+1;}int Solve(int l,int r){int k=belong[l];if ((k-1)*B+1==l) return f[k][r].id;Ans x=f[k+1][r];for (int i=l;i<=min(k*B,r);i++){int now=Get(a[i].hash,l,r);if (now>x.ans||(now==x.ans&&a[i].id<x.id))x.ans=now,x.id=a[i].id;}return x.id;}int main(){scanf("%d%d",&n,&m);tot=0;for (int i=1;i<=n;i++){read(a[i].id);b[i].v=a[i].id,b[i].pos=i;}sort(b+1,b+1+n,cmp);b[0].v=-10;for (int i=1;i<=n;i++)if (b[i].v==b[i-1].v) a[b[i].pos].hash=tot;else a[b[i].pos].hash=++tot;for (int i=1;i<=n;i++)v[a[i].hash].pb(i);B=sqrt(n);num=(n+B-1)/B;Prepare();int ans=0;while (m–){int l,r;read(l),read(r);l=(l+ans-1)%n+1,r=(r+ans-1)%n+1;if (l>r) swap(l,r);ans=Solve(l,r);printf("%d\n",ans);}return 0;}

感悟：

1.二分写错；

Solve中要注意(l,r)可能不足一块，所以循环到min(k*B,r)

临行之前，面对太多的疑问和不解：