求区间众数
分块
用的蓝书法二做的:预处理每个区间的最大众数,然后二分检查更新答案,同时更新边角的答案,记得分块的数量的是 \(\sqrt{m * log_{2}n}\)
这个代码过不了 acwing 的:https://www.acwing.com/problem/content/251/
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <vector> using namespace std; typedef long long ll; const int maxn = 4e4 + 10; #define endl '\n' int num[maxn], a[maxn]; int L[maxn], R[maxn], pos[maxn]; int id[maxn], cnt[maxn]; int h[1010][1010]; vector<int>b[maxn]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("text.in", "rb", stdin); // freopen("text.out", "wb", stdout); int n, m; cin >> n >> m; for(int i=1; i<=n; i++) {cin >> num[i]; a[i] = num[i];} sort(a + 1, a + 1 + n); int tp = 0, nn = max(1, (int)(n / sqrt(m * log2(n)))); int t = n / nn; a[0] = a[1] - 1; for(int i=1; i<=n; i++) { if(a[i] != a[i-1]) { id[++tp] = a[i]; } } for(int i=1; i<=n; i++) { num[i] = lower_bound(id + 1, id + tp + 1, num[i]) - id; b[num[i]].push_back(i); // cout << num[i] << " "; } // cout << endl; for(int i=1; i<=t; i++) { L[i] = R[i-1] + 1; R[i] = i * nn; // cout << L[i] << " " << R[i] << endl; } // cout << endl << endl; if(R[t] < n) { t++; L[t] = R[t-1] + 1; R[t] = n; } for(int i=1; i<=t; i++) { for(int j=L[i]; j<=R[i]; j++) { pos[j] = i; } } for(int i=1; i<=t; i++) { for(int j=0; j<=tp; j++) cnt[j] = 0; for(int j=i; j<=t; j++) { int x = h[i][j-1]; int y = cnt[x]; for(int k=L[j]; k<=R[j]; k++) { cnt[num[k]]++; if(cnt[num[k]] > y || (cnt[num[k]] == y && num[k] < x)) { x = num[k]; y = cnt[x]; } } h[i][j] = x; } } int ans = 0, way = 0; while(m--) { int x, y; cin >> x >> y; x = (x + ans - 1) % n + 1; y = (y + ans - 1) % n + 1; if(x > y) swap(x, y); // cout << x << " " << y << endl; int tx = pos[x], ty = pos[y]; ans = way = 0; if(tx == ty) { for(int i=x; i<=y; i++) { int temp = upper_bound(b[num[i]].begin(), b[num[i]].end(), y) - lower_bound(b[num[i]].begin(), b[num[i]].end(), x); if(temp > way || (temp == way && num[i] < ans)) { ans = num[i]; way = temp; } } } else { for(int i=x; i<=R[tx]; i++) { int temp = upper_bound(b[num[i]].begin(), b[num[i]].end(), y) - lower_bound(b[num[i]].begin(), b[num[i]].end(), x); if(temp > way || (temp == way && num[i] < ans)) { ans = num[i]; way = temp; } } for(int i=L[ty]; i<=y; i++) { int temp = upper_bound(b[num[i]].begin(), b[num[i]].end(), y) - lower_bound(b[num[i]].begin(), b[num[i]].end(), x); if(temp > way || (temp == way && num[i] < ans)) { ans = num[i]; way = temp; } } if(tx + 1 <= ty - 1) { int now = h[tx+1][ty-1]; int temp = upper_bound(b[now].begin(), b[now].end(), y) - lower_bound(b[now].begin(), b[now].end(), x); if(temp > way || (temp == way && now < ans)) { ans = now; way = temp; } } } ans = id[ans]; cout << ans << endl; } return 0; }