acwing 249

题目链接

题目大意

题目意思很简单，给出一个长度为n的数组、m个查询；每个查询有 l ~ r 查询的是区间里的众数，如果数量相等输出小的那个。

这可怎么做，？
刚开始看到这道题、懵了一会、想不到怎么做；线段树没办法维护或者是我不会维护 感觉 咋咋都不行
于是看了看书上的题解，看不懂啊 只看懂了要用分块；
于是就自己想着用分块写。。。结果我很菜没写出来，（又t又wa）

于是网上找博客看，终于 a 了，
好了不说废话了hhhhhhh

题解：
分块的思想，把这些数分成一块一块 然后暴力
首先这些数1e9 如果要用数组存个数 肯定是要离散化的。
然后 离散化完呢？ 既然已经把他们分块了，那么要查询的那个答案肯定是大段+小段合并得到的
于是想想怎么得到？

看看这个歪歪扭扭的图
大段是d2 小段是d1 - d2
那么这个区间的众数肯定是在d2里的众数和d1 - d2 里的所有数里的（很他妈关键我咋就想不到 ）
于是得维护一个d2 的众数 也就是维护一段连续的大段的众数
这个简单暴力就好
然后 最后知道了答案在那些数里 可是怎么去找答案？
也就是要统计查询的 l ~ r 里那些数的个数。
怎么统计？ for一遍肯定是不行的。
这里也是我所想不到的；
用一个vector[maxn] 二维数组 存每个数字出现的地方，于是这个数字出现的次数就是：upper_bound( vp[x].begin() , vp[x].end() , r ) - lower_bound( vp[x].begin(), vp[ x ].end() , l ) ;
这个很显然，因为vector是有序的。
附上代码：

#include<stdio.h>
#include<algorithm>
#include<set> 
#include<math.h>
#include<vector>
using namespace std;
vector<int> vv;
const int maxn = 4e4+5;
const int N = 805;
vector<int> vp[maxn];
int bj[maxn];
int zs[N][N];
int a[maxn];
int L[maxn];
int R[maxn];
int vis[maxn];
int n;



int temp[maxn];
void init()
{
   
	
	int t = sqrt(1.0 * n * log(n) / log(2));
	int len = t ? n / t : n;
// printf("%d\n",t); 
	for (int i = 1; i <= t; i ++ )
	{
   
		L[i] = (i-1) * len + 1;
		R[i] = i * len;
	}
	if(R[t] < n)
	{
   
		L[t+1] = R[t] + 1;
		R[t+1] = n;
		t++;
	}
	for (int i = 1; i <= t; i ++ )
	{
   
		for (int j = L[i]; j <= R[i]; j ++ )
		{
   
			vis[j] = i;
		}
	}
	for (int i = 1; i <= t; i++ )
	{
   
		int ans = 0;
		int sum = 0;
		for (int j = L[i]; j <= n; j ++ )
		{
   
			temp[bj[j]]++;
			if(sum < temp[bj[j]] || (sum == temp[bj[j]] && bj[j] < ans))
			{
   
				sum = temp[bj[j]];
				ans = bj[j];
			}
			zs[i][vis[j]] = ans;
		}
		for (int j =L[i]; j <= n; j ++ )
		{
   
			temp[bj[j]] = 0;
		}
	}
}
set<int> ss;

int getnum(int l,int r,int x)
{
   
	int s1 = lower_bound(vp[x].begin(),vp[x].end(),l) - vp[x].begin();
	int s2 = upper_bound(vp[x].begin(),vp[x].end(),r) - vp[x].begin() - 1;
	return s2 - s1 + 1;
}
int tt[maxn];
int getans(int l,int r)
{
   
// printf("%d %d\n",l,r);
	int kk = 0;
	int p = vis[l];
	int q = vis[r];
	if(p + 1 <= q - 1)
		tt[kk++] = zs[p+1][q-1];
	for (int i = l; i <= R[p]; i ++) 
	{
   
		tt[kk++] = bj[i];
	}
	for (int i = L[q]; i <= r; i ++ )
	{
   
		tt[kk++] = bj[i];
	}
	int ss = unique(tt,tt+kk) - tt;
	int num = 0;
	int ans = 0;
	for (int i = 0; i < ss; i ++ ) 
	{
   
		int x = tt[i];
		int s = getnum(l,r,x);
// printf("%d %d\n",x,s);
		if(num < s || (num == s && x < ans))
		{
   
			ans = x;
			num = s;
		}
	}
// printf("\n");
	return ans;
}

int main()
{
   
	int m;
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= n; i ++ )
	{
   
		scanf("%d",&a[i]);
		vv.push_back(a[i]);
	}
	sort(vv.begin(),vv.end());
	vv.erase(unique(vv.begin(),vv.end()),vv.end());
	for (int i = 1; i <= n; i ++ )
	{
   
		bj[i] = lower_bound(vv.begin(),vv.end(),a[i]) - vv.begin() + 1;
	}
	for (int i = 1; i <= n; i ++) 
	{
   
		vp[bj[i]].push_back(i);
	}
	init();
	int x = 0; 
	while( m -- )
	{
   
		int l,r;
		scanf("%d%d",&l,&r);
		l = (l + x - 1) % n + 1;
		r = (r + x - 1) % n + 1;
		if(l > r)
			swap(l,r);
		int s = getans(l,r);
		x = vv[s - 1];
		printf("%d\n",x);
	}
	
}