洛谷傳送門

BZOJ傳送門

題目背景

親愛的哥哥：

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

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

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

哥哥你要快點回來哦！

愛你的妹妹 Violet

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

“蒲公英嗎……”

題目描述

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

為了簡化起見，我們把所有的蒲公英看成一個長度為nn的序列 (a1,a2..an)(a1,a2..an) ，其中 aiai 為一個正整數，表示第ii棵蒲公英的種類編號。

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

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

輸入輸出格式

輸入格式：

第一行兩個整數 n,mn,m ，表示有nn株蒲公英，mm 次詢問。

接下來一行nn個空格分隔的整數 aiai ，表示蒲公英的種類

再接下來 mm 行每行兩個整數 l0,r0l0,r0 ，我們令上次詢問的結果為 xx（如果這是第一次詢問， 則 x=0x=0）。

令 l=(l0+x?1)modn+1,r=(r0+x?1)modn+1l=(l0+x?1)modn+1,r=(r0+x?1)modn+1 ，如果 l>rl>r，則交換 l,rl,r 。

最終的詢問區間為[l,r][l,r]。

輸出格式：

輸出mm 行。每行一個整數，表示每次詢問的結果。

輸入輸出樣例

輸入樣例#1：

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

輸出樣例#1：

1 2 1

說明

對于 20% 的數據，保證 1≤n,m≤30001≤n,m≤3000 。

對于 100% 的數據，保證 1≤n≤40000,1≤m≤50000,1≤ai≤1091≤n≤40000,1≤m≤50000,1≤ai≤109 。

解題分析

這道題和作詩這道題很像， 處理方式也大致相同， 就不廢話了…

不過aiai的范圍很大， 需要先離散化一下。

#include <cstdio> #include <cstring> #include <cstdlib> #include <cctype> #include <algorithm> #include <cmath> #define R register #define IN inline #define gc getchar() #define W while #define MX 50500 template <class T> IN void in(T &x) {x = 0; R char c = gc;for (; !isdigit(c); c = gc);for (; isdigit(c); c = gc)x = (x << 1) + (x << 3) + c - 48; } int bel[MX], dat[MX], cpy[MX], sum[230][MX], ans[230][230], cnt[MX]; int dot, q, ctyp, lastans, dif, siz, bd; IN int query(R int lef, R int rig) {if(lef > rig) std::swap(lef, rig);int l = bel[lef], r = bel[rig];if(r - l <= 1){for (R int i = lef; i <= rig; ++i){++cnt[dat[i]];if(cnt[dat[i]] > cnt[lastans] || (cnt[dat[i]] == cnt[lastans] && dat[i] < lastans)) lastans = dat[i];}for (R int i = lef; i <= rig; ++i) --cnt[dat[i]];return lastans = cpy[lastans];}lastans = ans[l + 1][r - 1];int lb = l * siz, buf, tar;for (R int i = lef; i <= lb; ++i){++cnt[dat[i]];tar = cnt[lastans] + sum[r - 1][lastans] - sum[l][lastans];buf = cnt[dat[i]] + sum[r - 1][dat[i]] - sum[l][dat[i]];if(buf > tar || (buf == tar && dat[i] < lastans)) lastans = dat[i];}for (R int i = (r - 1) * siz + 1; i <= rig; ++i){++cnt[dat[i]];tar = cnt[lastans] + sum[r - 1][lastans] - sum[l][lastans];buf = cnt[dat[i]] + sum[r - 1][dat[i]] - sum[l][dat[i]];if(buf > tar || (buf == tar && dat[i] < lastans)) lastans = dat[i];}for (R int i = lef; i <= lb; ++i) --cnt[dat[i]];for (R int i = (r - 1) * siz + 1; i <= rig; ++i) --cnt[dat[i]];return lastans = cpy[lastans]; } int main(void) {int a, b, res;in(dot), in(q); siz = std::sqrt(dot) + 1;for (R int i = 1; i <= dot; ++i) in(dat[i]), cpy[i] = dat[i];std::sort(cpy + 1, cpy + 1 + dot);dif = std::unique(cpy + 1, cpy + 1 + dot) - cpy - 1;for (R int i = 1; i <= dot; ++i)//離散化{dat[i] = std::lower_bound(cpy + 1, cpy + 1 + dif, dat[i]) - cpy;bel[i] = (i - 1) / siz + 1;++sum[bel[i]][dat[i]];} bd = bel[dot];for (R int i = 1; i <= dif; ++i)for (R int j = 1; j <= bd; ++j) sum[j][i] += sum[j - 1][i];for (R int i = 1; i <= bd; ++i){res = 0;for (R int j = (i - 1) * siz + 1; j <= dot; ++j){++cnt[dat[j]];if(cnt[dat[j]] > cnt[res] || (cnt[dat[j]] == cnt[res] && dat[j] < res)) res = dat[j];ans[i][bel[j]] = res;}for (R int j = (i - 1) * siz + 1; j <= dot; ++j) --cnt[dat[j]];}W (q--){in(a), in(b);a = (a + lastans - 1) % dot + 1, b = (b + lastans - 1) % dot + 1;lastans = 0; printf("%d\n", query(a, b));} }

總結

以上是生活随笔為你收集整理的[Luogu P4168] [BZOJ 2724] [Violet]蒲公英的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。