灼眼的夏娜 @ 2019-09-22 14:39:08
有哪位大佬帮忙看看这份代码哪里有问题
#include<bits/stdc++.h>
#define R register
using namespace std;
const int N = 40005;
int n,m,num,x,cnt,len;
int b[N],tag[N],a[N],ll[N],rr[N],ton[N];
int sum[300][N],p[300][300];
inline int query(int l,int r) {
R int now = 0,fr = tag[l],to = tag[r];
if(to - fr <= 1) {
for(R int i = l;i <= r;++ i) ton[a[i]]++;
for(R int i = l;i <= r;++ i)
if(ton[a[i]] + (a[i] < now) > ton[now])
now = a[i];
for(R int i = l;i <= r;++ i) ton[a[i]] = 0;
return now;
}
for(R int i = l;i <= rr[fr];++ i) ton[a[i]] ++;
for(R int i = ll[to];i <= r;++ i) ton[a[i]] ++;
-- to;
now = p[fr + 1][to];
for(R int i = l;i <= rr[fr];++ i)
if(sum[to][now] - sum[fr][now] + ton[now] < sum[to][a[i]] + (a[i] < now) - sum[fr][a[i]] + ton[a[i]])
now = a[i];
for(R int i = ll[to + 1];i <= r;++ i)
if(sum[to][now] - sum[fr][now] + ton[now] < sum[to][a[i]] + (a[i] < now) - sum[fr][a[i]] + ton[a[i]])
now = a[i];
++ to;
for(R int i = l;i <= rr[fr];++ i) ton[a[i]] = 0;
for(R int i = ll[to];i <= r;++ i) ton[a[i]] = 0;
return now;
}
inline void init() {
for(R int i = 1;i <= num;++ i) {
for(R int j = ll[i];j <= rr[i];++ j) sum[i][a[j]] ++;
for(R int j = 1;j <= cnt;++ j) sum[i][j] += sum[i - 1][j];
}
for(R int i = 1;i <= num;++ i)
for(R int j = i;j <= num;++ j) {
R int now = p[i][j - 1];
for(R int k = ll[j];k <= rr[j];++ k) {
if(sum[j][a[k]] - sum[i - 1][a[k]] + (a[k] < now) > sum[j][now] - sum[i - 1][now])
now = a[k];
}
p[i][j] = now;
}
}
int main() {
// freopen("violet.in","r",stdin);
// freopen("violet.out","w",stdout);
scanf("%d%d",&n,&m);
len = sqrt(n);
for(R int i = 1;i <= n;++ i) {
scanf("%d",&a[i]);
tag[i] = (i - 1) / len + 1;
b[i] = a[i];
}
sort(b + 1,b + n + 1);
cnt = unique(b + 1,b + n + 1) - b - 1;
for(R int i = 1;i <= n;++ i) a[i] = lower_bound(b + 1,b + cnt + 1,a[i]) - b;
if(len * len == n) num = len;
else num = len + 1;
for(R int i = 1;i <= num;++ i) {
ll[i] = (i - 1) * len + 1;
rr[i] = min(n,i * len);
}
init();
int X = 0;
for(R int i = 1,l,r;i <= m;++ i) {
scanf("%d%d",&l,&r);
l = (l + X - 1) % n + 1,r = (r + X - 1) % n + 1;
if(l > r) swap(l,r);
x = query(l,r);
printf("%d\n", X = b[x]);
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
by BinDir0 @ 2019-09-22 15:24:07
@灼眼的夏娜 哇一千多组
by BinDir0 @ 2019-09-22 15:24:22
窝拍了两百多组就放弃了
by 言和YanHe @ 2019-10-07 08:50:25
@恨妹不成穹 我拍几十组就放弃了/xyx/baojin(
by BinDir0 @ 2019-10-07 15:28:52
@HFOI菠萝 /xyx