題目背景

親愛的哥哥：

你在那個城市里面過得好嗎？

我在家里面最近很開心呢。昨天晚上奶奶給我講了那個叫「絕望」的大壞蛋的故事的說！它把人們的房子和田地搞壞，還有好多小朋友也被它殺掉了。我覺得把那么可怕的怪物召喚出來的那個壞蛋也很壞呢。不過奶奶說他是很難受的時候才做出這樣的事的……

最近村子里長出了一大片一大片的蒲公英。一刮風，這些蒲公英就能飄到好遠的地方了呢。我覺得要是它們能飄到那個城市里面，讓哥哥看看就好了呢！

哥哥你要快點回來哦！

愛你的妹妹 $Violet$

$Azure$ 讀完這封信之后微笑了一下。

“蒲公英嗎……”

題目描述

在鄉(xiāng)下的小路旁種著許多蒲公英，而我們的問題正是與這些蒲公英有關(guān)。

為了簡化起見，我們把所有的蒲公英看成一個長度為n的序列 $a_1,a_2..a_n$，其中$a_i$為一個正整數(shù)，表示第$i$棵蒲公英的種類編號。

而每次詢問一個區(qū)間 $[l,r]$，你需要回答區(qū)間里出現(xiàn)次數(shù)最多的是哪種蒲公英，如果有若干種蒲公英出現(xiàn)次數(shù)相同，則輸出種類編號最小的那個。

注意，你的算法必須是在線的

輸入格式

第一行兩個整數(shù) $n,m$ ，表示有$n$株蒲公英，$m$ 次詢問。

接下來一行$n$個空格分隔的整數(shù)$a_i$表示，蒲公英的種類

再接下來$m$行每行兩個整數(shù)$l_0,r_0$我們令上次詢問的結(jié)果為 $x$（如果這是第一次詢問， 則 $x=0$）。

令 $l=(l_0+x?1)\mathrm{m}\mathrm{o}\mathrm{d}n+1,r=(r_0+x?1)\mathrm{m}\mathrm{o}\mathrm{d}n+1$如果$l>r$，則交換$l,r$ 。

最終的詢問區(qū)間為$[l,r]$。

輸出格式

輸出$m$行。每行一個整數(shù)，表示每次詢問的結(jié)果。

輸入輸出樣例

輸入 #1

6 3 1 2 3 2 1 2 1 5 3 6 1 5

輸出 #1

1 2 1

說明/提示

對于 20% 的數(shù)據(jù)，保證 $1\le n,m\le 3000$

對于 100% 的數(shù)據(jù)，保證 $1\le n\le 40000,1\le m\le 50000,1\le a_i\le 10^9$

解法一

• 為什么快讀要比$scanf$慢啊啊啊啊
• $scanf$
• $read$
• 定義$c[i][j][k]$表示從第$i$個塊到第$j$個塊數(shù)字$k$出現(xiàn)的次數(shù)，$f[i][j][0]$表示區(qū)間數(shù)字最多的出現(xiàn)次數(shù)，$f[i][j][1]$表示區(qū)間眾數(shù)。
• 對于每次詢問直接按照分塊的思想，對于$[l,L)$和$(r,R]$樸素掃描累加次數(shù)更新答案，詢問后減少次數(shù)復原數(shù)組即可。

$code1$

#include <bits/stdc++.h> using namespace std; const int maxn = 4e4 + 100; const int maxm = 37; template <class T> inline void read(T &s) {s = 0; T w = 1, ch = getchar(); while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }s *= w; } int n, m, tot, t; int a[maxn], b[maxn], L[maxn], R[maxn], pos[maxn], now[2]; int c[maxm][maxm][maxn], f[maxm][maxm][2]; inline void discretize() {memcpy(b, a, sizeof(b)); sort(b + 1, b + n + 1); tot = unique(b + 1, b + n + 1) - b - 1; for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b; }inline void work(int x, int y, int num) {++c[x][y][num]; if (c[x][y][num] > now[0] || (c[x][y][num] == now[0] && num < now[1])) {now[0] = c[x][y][num]; now[1] = num; } }int query(int l, int r) {int p = pos[l], q = pos[r]; int x = 0, y = 0; if (p + 1 <= q - 1) x = p + 1, y = q -1; memcpy(now, f[x][y], sizeof(now)); if (p == q) {for (int i = l; i <= r; ++i) work(x, y, a[i]); for (int i = l; i <= r; ++i) --c[x][y][a[i]]; }else {for (int i = l; i <= R[p]; ++i) work(x, y, a[i]); for (int i = L[q]; i <= r; ++i) work(x, y, a[i]); for (int i = l; i <= R[p]; ++i) --c[x][y][a[i]]; for (int i = L[q]; i <= r; ++i) --c[x][y][a[i]]; }return b[now[1]]; }int main() {// freopen("1.in", "r", stdin); read(n), read(m); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); discretize(); t = pow(double(n), (double)1 / 3); int len = t ? n / t : n; for (int i = 1; i <= t; ++i) {L[i] = (i - 1) * len + 1; R[i] = i * len; }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; memset(f, 0, sizeof(f)); memset(c, 0, sizeof(c)); for (int i = 1; i <= t; ++i) {for (int j = i; j <= t; ++j) {for (int k = L[i]; k <= R[j]; ++k) ++c[i][j][a[k]]; for (int k = 1; k <= tot; ++k) {if (c[i][j][k] > f[i][j][0]) {f[i][j][0] = c[i][j][k]; f[i][j][1] = k; }}}}int x = 0; while (m--) {int l, r; 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); }return 0; }

總結(jié)

以上是生活随笔為你收集整理的[Violet]蒲公英（分块）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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