題目大意：有$n(n\leqslant5\times10^5)$個數(shù)，$m(m\leqslant5\times10^5)$個詢問，每個詢問問區(qū)間$[l,r]$中眾數(shù)的出現(xiàn)次數(shù)

題解：分塊，設(shè)塊大小為$S$，先可以預(yù)處理出兩兩塊之間的眾數(shù)出現(xiàn)次數(shù)，復(fù)雜度$O(\Big(\dfrac n S\Big)n)$。詢問時先把答案設(shè)成整塊內(nèi)的答案，然后對兩邊剩下的最多$2S$個元素進行討論。

難點在如何快速求出一個元素在區(qū)間內(nèi)出現(xiàn)次數(shù)，先想到的是主席樹，但是多了一個$\log_2$，并過不去。可以把每種數(shù)出現(xiàn)的位置用$vector$存下來，并且對每個數(shù)存一個它在$vector$中的位置，第$i$個數(shù)的位置是$ret_i$，假設(shè)現(xiàn)在的答案為$ans$，正在處理左邊的多余元素，處理到第$i$個，可以看這個數(shù)值的$vector$中，第$ret_i+ans$位是否小于$r$，若小于，則這個數(shù)至少出現(xiàn)了$ans+1$次，更新答案。右邊也是類似的。

發(fā)現(xiàn)$ans$最多自增$2S$次，所以一次查詢的復(fù)雜度是$O(2S)$的，總復(fù)雜度為$O(2Sm+\Big(\dfrac n S\Big)n)$，當(dāng)$S$略小于$\sqrt n$時最優(yōu)（其實是我不怎么算）

卡點：$Ynoi$當(dāng)然卡常啦

?

C++ Code：

#include <algorithm> #include <cstdio> #include <cctype> #include <vector>namespace std {struct istream { #define M (1 << 24 | 3)char buf[M], *ch = buf - 1;inline istream() { #ifndef ONLINE_JUDGEfreopen("input.txt", "r", stdin); #endiffread(buf, 1, M, stdin);}inline istream& operator >> (int &x) {while (isspace(*++ch));for (x = *ch & 15; isdigit(*++ch); ) x = x * 10 + (*ch & 15);return *this;} #undef M} cin;struct ostream { #define M (1 << 24 | 3)char buf[M], *ch = buf - 1;int w;inline ostream& operator << (int x) {if (!x) {*++ch = '0';return *this;}for (w = 1; w <= x; w *= 10);for (w /= 10; w; w /= 10) *++ch = (x / w) ^ 48, x %= w;return *this;}inline ostream& operator << (const char x) {*++ch = x; return *this;}inline ostream& operator << (const char *x) {while (*x) *this << *x++;return *this;}inline ~ostream() { #ifndef ONLINE_JUDGEfreopen("output.txt", "w", stdout); #endiffwrite(buf, 1, ch - buf + 1, stdout);} #undef M} cout; }#define maxn 500010 const int BSZ = 610, BNUM = maxn / BSZ + 10;int cnt[maxn]; int MAX[BNUM][BNUM]; int L[maxn], R[maxn], bel[maxn];int n, m, Bnum; int w[maxn], v[maxn];std::vector<int> list[maxn]; int ret[maxn]; int main() {std::cin >> n >> m;for (int i = 1; i <= n; i++) {std::cin >> w[i];v[i] = w[i];bel[i] = (i - 1) / BSZ + 1;}const int tot = (std::sort(v + 1, v + n + 1), std::unique(v + 1, v + n + 1) - v - 1);for (int i = 1; i <= n; i++) {w[i] = std::lower_bound(v + 1, v + tot + 1, w[i]) - v;ret[i] = list[w[i]].size();list[w[i]].push_back(i);}Bnum = bel[n];for (int i = 1; i <= Bnum; i++) {L[i] = (i - 1) * BSZ, R[i] = L[i] + BSZ - 1;}L[1] = 1, R[Bnum] = n;for (int i = 1; i <= Bnum; i++) {__builtin_memset(cnt, 0, sizeof cnt);int Max = 0, now = i;for (int j = L[i]; j <= n; j++) {cnt[w[j]]++;Max = std::max(Max, cnt[w[j]]);if (j == R[now]) {MAX[i][now] = Max;now++;}}}int ans = 0;while (m --> 0) {int l, r;std::cin >> l >> r;l ^= ans, r ^= ans;const int lb = bel[l], rb = bel[r];ans = 0;if (lb == rb) {for (int i = l; i <= r; i++) {const int W = w[i], sz = list[W].size(), pos = ret[i];while (pos + ans < sz && list[W][pos + ans] <= r) ans++;}} else {if (lb + 1 < rb) ans = MAX[lb + 1][rb - 1];for (int i = l; i <= R[lb]; i++) {const int W = w[i], sz = list[W].size(), pos = ret[i];while (pos + ans < sz && list[W][pos + ans] <= r) ans++;}for (int i = L[rb]; i <= r; i++) {const int W = w[i], pos = ret[i];while (pos >= ans && list[W][pos - ans] >= l) ans++;}}std::cout << ans << '\n';}return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/Memory-of-winter/p/10126812.html

總結(jié)

以上是生活随笔為你收集整理的[洛谷P5048][Ynoi2019模拟赛]Yuno loves sqrt technology III的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。