Mintind @ 2019-08-15 09:03:14
RE了十六个点,下下数据来看好像输入有问题,可是看了半天啥也没看出来!!!
大佬们帮帮我QAQ
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
const int N = 40005, T = 1005;
int a[N], b[N], pos[N], f[T][T], v1[N];
//b用来离散化,a[i]原序列中i位置的数在b中下标
//f[i][j]为第i块到第j块的众数,L[i]是第i块左端点下标
int n, m, t, block, num;
std::vector<int> v[N];
int max(int a, int b)
{
return a > b ? a : b;
}
int count(int l, int r, int x)
{
if(!x) return 0;
l = std::lower_bound(v[x].begin(), v[x].end(), l) - v[x].begin();
r = std::upper_bound(v[x].begin(), v[x].end(), r) - v[x].begin();
//r是第一个 >= r 的数 ,符合条件的范围是[l, r)
return r - l;
}
void init()
{
for(int i = 1; i <= pos[n]; ++i)
{
memset(v1, 0, sizeof(v1));
int ans = 0;
for(int j = (i - 1) * block + 1; j <= n; ++j)
{
v1[a[j]]++;
if(v1[a[j]] > ans || (v1[a[j]] == ans && b[a[j]] < f[i][pos[j]]))
{
ans = v1[a[j]];
f[i][pos[j]] = b[a[j]];
}
}
}
}
int query(int l, int r)
{
int p = pos[l], q = pos[r];
int mx = f[p + 1][q - 1], ans = count(l, r, a[mx]);
//ans不能直接等于a[mx]在p+1块到q-1块出现的次数
//printf("l %d r %d\n", l, r);
if(p == q)
{
for(int i = l; i <= r; ++i)
{
int x = count(l, r, a[i]);
if(x > ans || (x == ans && b[a[i]] < mx))
{
ans = x;
mx = b[a[i]];
}
}
}
else
{
for(int i = l; i <= p * block; i++)
{
int x = count(l, r, a[i]);
if(x > ans || (x == ans && b[a[i]] < mx))
{
ans = x;
mx = b[a[i]];
}
}
for(int i = (q - 1) * block + 1; i <= r; ++i)
{
int x = count(l, r, a[i]);
if(x > ans || (x == ans && b[a[i]] < mx))
{
ans = x;
mx = b[a[i]];
}
}
}
return mx;
}
int main(){
//freopen("testdata.in", "r", stdin);
scanf("%d%d", &n, &m);
block = max(1, n / sqrt((double)m * log2(n)));
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
b[i] = a[i];
pos[i] = (i - 1) / block + 1;
}
std::sort(b + 1, b + n + 1);
num = std::unique(b + 1, b + n + 1) - b - 1;
for(int i = 1; i <= n; ++i)
{
a[i] = std::lower_bound(b + 1, b + num + 1, a[i]) - b;
v[a[i]].push_back(i);
}
init();
int l, r, x = 0;
while(m--)
{
scanf("%d%d", &l, &r);
//printf("m %d %d %d\n", m, l, r);
l = (l + x - 1) % n + 1;
r = (r + x - 1) % n + 1;
if(l > r) std::swap(l, r);
x = query(l, r);
printf("%d\n", x);
}
return 0;
}
by sc84bbs @ 2019-08-15 09:11:36
不,RE不求
by danefishhh @ 2019-10-21 14:57:08
@flxziq 您的vector排序了吗
by danefishhh @ 2019-10-21 15:06:07
@flxziq 它本来就是有序的...当我没说...
by danefishhh @ 2019-10-21 15:09:07
@flxziq 不过如果您过了的话能否帮我看看我的问题呢..谢谢