題目背景

親愛(ài)的哥哥：

你在那個(gè)城市里面過(guò)得好嗎？

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

最近村子里長(zhǎng)出了一大片一大片的蒲公英。一刮風(fēng)，這些蒲公英就能飄到好遠(yuǎn)的地方了呢。我覺(jué)得要是它們能飄到那個(gè)城市里面，讓哥哥看看就好了呢！

哥哥你要快點(diǎn)回來(lái)哦！

愛(ài)你的妹妹 Violet

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

“蒲公英嗎……”

題目描述

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

為了簡(jiǎn)化起見(jiàn)，我們把所有的蒲公英看成一個(gè)長(zhǎng)度為n的序列?(a_1,a_2..a_n)(a1?,a2?..an?)?，其中?a_iai??為一個(gè)正整數(shù)，表示第i棵蒲公英的種類編號(hào)。

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

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

輸入輸出格式

輸入格式：

?

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

接下來(lái)一行n個(gè)空格分隔的整數(shù)?a_iai??，表示蒲公英的種類

再接下來(lái)m 行每行兩個(gè)整數(shù)?l_0,r_0l0?,r0??，我們令上次詢問(wèn)的結(jié)果為 x（如果這是第一次詢問(wèn)， 則 x=0）。

令?l=(l_0+x-1)\bmod n + 1,r=(r_0+x-1) \bmod n + 1l=(l0?+x?1)modn+1,r=(r0?+x?1)modn+1?，如果 l>r，則交換 l,r 。

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

?

輸出格式：

?

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

?

輸入輸出樣例

輸入樣例#1：?復(fù)制 6 3 1 2 3 2 1 2 1 5 3 6 1 5 輸出樣例#1：?復(fù)制 1 2 1

說(shuō)明

對(duì)于 20% 的數(shù)據(jù)，保證?1\le n,m \le 30001≤n,m≤3000?。

對(duì)于 100% 的數(shù)據(jù)，保證?1\le n \le 40000,1\le m \le 50000,1\le a_i \le 10^91≤n≤40000,1≤m≤50000,1≤ai?≤109?。

題解：

考慮分塊，每次詢問(wèn)的答案為詢問(wèn)區(qū)間內(nèi)所有完整的塊的眾數(shù)或者散塊中出現(xiàn)過(guò)的數(shù)

對(duì)于每一個(gè)數(shù)，先離散化，開(kāi)個(gè)vector存下每個(gè)數(shù)在序列中出現(xiàn)的位置，然后預(yù)處理出f[i][j]，表示第i個(gè)塊到第j個(gè)塊的眾數(shù)，對(duì)于每次詢問(wèn)，考察散塊中的每個(gè)數(shù)及相應(yīng)的f[i][j]，即在vector中二分查找對(duì)應(yīng)的數(shù)在詢問(wèn)區(qū)間內(nèi)最近和最遠(yuǎn)的出現(xiàn)位置，其在vetcor中的位置相減加1即為其在詢問(wèn)區(qū)間中的出現(xiàn)次數(shù)

另外這題不吸氧氣過(guò)不去......

?

#include<bits/stdc++.h> using namespace std; int n,m,sz,tot; int arr[40005],tp[40005],f[205][205],idx[40005],cnt[40005],val[40005]; vector<int>pos[40005]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline int disc(int a) {return lower_bound(tp+1,tp+1+n,a)-tp; } inline void pre_work(int k) {int mx=0,num;memset(cnt,0,sizeof(cnt));for(register int i=(k-1)*sz+1;i<=n;i++){cnt[arr[i]]++;if(mx<=cnt[arr[i]]){if(mx==cnt[arr[i]]){if(num>arr[i])num=arr[i];}else{mx=cnt[arr[i]];num=arr[i];} }f[k][idx[i]]=num; } } inline int find(int l,int r,int p) {return upper_bound(pos[p].begin(),pos[p].end(),r)-lower_bound(pos[p].begin(),pos[p].end(),l); } inline int query(int l,int r) {int ret,mx=0;if(idx[l]==idx[r]){for(register int i=l;i<=r;i++){int t=find(l,r,arr[i]);if(mx<=t){if(mx==t){if(val[arr[i]]<ret)ret=val[arr[i]];}else{mx=t;ret=val[arr[i]];} }}}else{for(register int i=l;i<=idx[l]*sz;i++){ int t=find(l,r,arr[i]);if(mx<=t){if(mx==t){if(val[arr[i]]<ret)ret=val[arr[i]];}else{mx=t;ret=val[arr[i]];} }}for(register int i=(idx[r]-1)*sz+1;i<=r;i++){int t=find(l,r,arr[i]);if(mx<=t){if(mx==t){if(val[arr[i]]<ret)ret=val[arr[i]];}else{mx=t;ret=val[arr[i]];} }}if(idx[l]+1<=idx[r]-1){int t=find(l,r,f[idx[l]+1][idx[r]-1]);if(mx<=t){if(mx==t){if(val[f[idx[l]+1][idx[r]-1]]<ret)ret=val[f[idx[l]+1][idx[r]-1]];}else{mx=t;ret=val[f[idx[l]+1][idx[r]-1]];} }} }return ret; } int main() {n=read();m=read();sz=(int)sqrt(n);for(register int i=1;i<=n;i++){arr[i]=read();tp[i]=arr[i];idx[i]=(i-1)/sz+1;}sort(tp+1,tp+1+n);for(register int i=1;i<=n;i++){int r=disc(arr[i]);val[r]=arr[i];arr[i]=r;pos[r].push_back(i);}tot=(n-1)/sz+1;for(register int i=1;i<=tot;i++)pre_work(i);int x=0; for(register int i=1;i<=m;i++){int a,b;a=read();b=read();a=(a+x-1)%n+1;b=(b+x-1)%n+1;x=query((a<b?a:b),(a>b?a:b));printf("%d\n",x);} return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/nanjolno/p/9344868.html

總結(jié)

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

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