kma_093 @ 2019-07-10 10:18:05
标题不重要
求哪位dalao帮忙看看QAQ调一天多了，和题解第一篇思路差不多
orzorzorz感激不尽
#include<bits/stdc++.h>
#define N (100000 + 5)
#define int long long
using namespace std;
inline int read() {
int cnt = 0, f = 1; char c = getchar();
while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}
while (isdigit(c)) {cnt = (cnt << 3) + (cnt << 1) + c - '0'; c = getchar();}
return cnt * f;
}
int n, a[N], b[N], q, t, tmp = 10000000, gmax, m;
int L[N], R[N], pos[N], s[1005][1005], p[1005][1005], num[N];
int ans, l, r;
int B[N];
void Discretize () {
sort (b + 1, b + n + 1);
q = unique(b + 1, b + n + 1) - b - 1;
for (register int i = 1; i <= n; i++)
a[i] = lower_bound(b + 1, b + q + 1, a[i]) - b;
}
void pre_work() {
t = sqrt(n);
for (register int i = 1; i <= t; i++) {
L[i] = (i - 1) * t + 1;
R[i] = i * t;
}
if (R[t] < n) {
++t;
L[t] = R[t - 1] + 1;
R[t] = n;
}
for (register int i = 1; i <= t; i++)
for (register int j = L[i]; j <= R[i]; j++) pos[j] = i;
for (register int i = 1; i <= t; i++) {
for (register int j = 1; j <= n; j++) s[i][j] = s[i - 1][j];
for (register int j = L[i]; j <= R[i]; j++)
s[i][a[j]]++;
}
for (register int i = 1; i <= t; i++) {
memset(B, 0, sizeof(B));
tmp = 10000000, gmax = 0;
for (register int j = 1; j <= t; j++) {
for (register int k = L[j]; k <= R[j]; k++) {
B[a[k]]++;
if (B[a[k]] >= gmax) {
// cout<<"###"<<tmp<<"###"<<a[k]<<endl;
if (B[a[k]] > gmax) tmp = a[k];
else if (tmp > a[k]) tmp = a[k];
gmax = B[a[k]];
}
}
p[i][j] = tmp;
// cout<<"i = "<<i<<" j = "<<j<<" p[i][j] = "<<p[i][j]<<endl;
}
}
}
int query(int l, int r) {
memset(B, 0, sizeof(B));
int ans = 100000, tmp = 0;
int x = pos[l], y = pos[r];
if (x == y) {
for (register int i = l; i <= r; i++) {
B[a[i]]++;
if (B[a[i]] >= B[ans] && a[i] < ans) ans = a[i];
}
} else {
for (register int i = l; i <= R[x]; i++)
B[a[i]] += (s[y - 1][a[i]] - s[x][a[i]]);
for (register int i = L[y]; i <= r; i++)
B[a[i]] += (s[y - 1][a[i]] - s[x][a[i]]);
for (register int i = l; i <= R[x]; i++) {
B[a[i]]++;
if (B[a[i]] > B[ans]) ans = a[i];
else if (B[a[i]] == B[ans] && a[i] < ans) ans = a[i];
}
for (register int i = L[y]; i <= r; i++) {
B[a[i]]++;
// cout<<B[a[i]]<<endl;
if (B[a[i]] > B[ans]) ans = a[i];
else if (B[a[i]] == B[ans] && a[i] < ans) ans = a[i];
}
// cout<<B[ans];
tmp = p[x + 1][y - 1];
// cout<<"nmsl "<<tmp<<endl;
if ((s[y - 1][tmp] - s[x][tmp] >= B[ans]) && tmp < ans) ans = tmp;
}
return b[ans];
}
signed main() {
// freopen("1.in","r",stdin);
n = read(), m = read();
for (register int i = 1; i <= n; i++) a[i] = b[i] = read();
Discretize();
pre_work();
ans = 0;
for (register int i = 1; i <= m; i++){
l = read(); r = read();
l = (l + ans - 1) % n + 1, r = (r + ans - 1) % n + 1;
if (l > r) swap(l, r);
// cout<<l<<" "<<r<<endl;
ans = query(l, r);
printf("%lld\n", ans);
}
return 0;
}by yijan @ 2019-07-10 10:25:28
学OI的妹子都这么暴力吗
没事写大分块
by S_S_H @ 2019-07-10 10:26:14
我感觉我看不懂 太复杂了 这题没这么恶心
by skydogli @ 2019-07-10 10:26:30
听我的，放弃分块，逃离苦海
by kma_093 @ 2019-07-10 10:37:24
现在不T了QAQ但是经过一通魔改发现过不去样例了QAQ
by kma_093 @ 2019-07-10 10:55:18
魔改之后的↓
#include<bits/stdc++.h>
#define N (100000 + 5)
#define int long long
using namespace std;
inline int read() {
int cnt = 0, f = 1; char c = getchar();
while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}
while (isdigit(c)) {cnt = (cnt << 3) + (cnt << 1) + c - '0'; c = getchar();}
return cnt * f;
}
int n, a[N], b[N], q, t, tmp = 10000000, gmax, m;
int L[N], R[N], pos[N], s[1005][1005], p[1005][1005], num[N];
int ans, l, r;
int B[N];
void Discretize () {
sort (b + 1, b + n + 1);
q = unique(b + 1, b + n + 1) - b - 1;
for (register int i = 1; i <= n; i++)
a[i] = lower_bound(b + 1, b + q + 1, a[i]) - b;
}
void pre_work() {
t = sqrt(n) + log(n)/log(2);
// t = sqrt(m * log(n));
for (register int i = 1; i <= t; ++i) {
L[i] = (i - 1) * t + 1;
R[i] = i * t;
}
if (R[t] < n) {
++t;
L[t] = R[t - 1] + 1;
R[t] = n;
}
for (register int i = 1; i <= t; ++i)
for (register int j = L[i]; j <= R[i]; j++) pos[j] = i;
for (register int i = 1; i <= t; ++i) {
for (register int j = 1; j <= n; j++) s[i][j] = s[i - 1][j];
for (register int j = L[i]; j <= R[i]; ++j)
s[i][a[j]]++;
}
for (register int i = 1; i <= t; i++) {
memset(B, 0, sizeof(B));
tmp = 10000000, gmax = 0;
for (register int j = 1; j <= t; ++j) {
for (register int k = L[j]; k <= R[j]; ++k) {
B[a[k]]++;
if (B[a[k]] >= gmax) {
if (B[a[k]] > gmax) tmp = a[k];
else if (tmp > a[k]) tmp = a[k];
gmax = B[a[k]];
}
}
p[i][j] = tmp;
}
}
}
int query(int l, int r) {
memset(B, 0, sizeof(B));
int ans = 100000, tmp = 0;
int x = pos[l], y = pos[r];
if (x == y) {
for (register int i = l; i <= r; ++i) {
++B[a[i]];
// if (B[a[i]] >= B[ans] && a[i] < ans) ans = a[i];
if (B[a[i]] > B[ans]) ans = a[i];
else if (B[a[i]] == B[ans] && a[i] < ans) ans = a[i];
}
} else {
for (register int i = l; i <= R[x]; ++i)
B[a[i]] += (s[y - 1][a[i]] - s[x][a[i]]);
for (register int i = L[y]; i <= r; ++i)
B[a[i]] += (s[y - 1][a[i]] - s[x][a[i]]);
for (register int i = l; i <= R[x]; ++i) {
++B[a[i]];
if (B[a[i]] > B[ans]) ans = a[i];
else if (B[a[i]] == B[ans] && a[i] < ans) ans = a[i];
}
for (register int i = L[y]; i <= r; ++i) {
++B[a[i]];
// cout<<B[a[i]]<<endl;
if (B[a[i]] > B[ans]) ans = a[i];
else if (B[a[i]] == B[ans] && a[i] < ans) ans = a[i];
}
// cout<<B[ans];
tmp = p[x + 1][y - 1];
// cout<<"nmsl "<<tmp<<endl;
if (s[y - 1][tmp] - s[x][tmp] > B[ans]) ans = tmp;
else if ((s[y - 1][tmp] - s[x][tmp] >= B[ans]) && tmp < ans) ans = tmp;
}
return b[ans];
}
signed main() {
// freopen("1.in","r",stdin);
n = read(), m = read();
for (register int i = 1; i <= n; ++i) a[i] = b[i] = read();
Discretize();
pre_work();
ans = 0;
for (register int i = 1; i <= m; ++i){
l = read(); r = read();
l = (l + ans - 1) % n + 1, r = (r + ans - 1) % n + 1;
if (l > r) swap(l, r);
// cout<<l<<" "<<r<<endl;
ans = query(l, r);
printf("%lld\n", ans);
}
return 0;
}by EarringYYR @ 2019-07-10 11:37:17
刚学OI就打分块的妹子，太暴力了
by kma_093 @ 2019-07-10 16:37:43
A过了
感谢同机房的@gigo_64 @sslz_fsy @wlj_55 查错orzorzorzorz
s和p第二维开小了，然后query的地方应该写
if(y - x <= 1)此贴终结，orzorzorz