【題目描述】

給出一個(gè)長為 n 的數(shù)列，以及 n 個(gè)操作，操作涉及詢問區(qū)間的最小眾數(shù)。

【輸入格式】

第一行輸入一個(gè)數(shù)字 n。

第二行輸入 n?個(gè)數(shù)字，第 i 個(gè)數(shù)字為 ai，以空格隔開。

接下來輸入 n 行詢問，每行輸入兩個(gè)數(shù)字 l、r，以空格隔開。

表示先查詢位于 [l,r] 的數(shù)字的眾數(shù)。

【輸出格式】

對于每次詢問，輸出一行一個(gè)數(shù)字表示答案。

【樣例】

樣例輸入
4
1 2 2 4
1 2
1 4
2 4
3 4

樣例輸出
1
2
2
2

【數(shù)據(jù)范圍與提示】

對于 100%?的數(shù)據(jù)，1<=n<=100000,-2^31<=other,ans<=2^31-1。

【源代碼】

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 10000+7; const int N = 100000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std;int n; int block,sum;//block為塊的長度,sum為塊的個(gè)數(shù) int a[N];//存放數(shù)列元素 int pos[N];//pos記錄第i個(gè)元素在第幾個(gè)塊中 int val[N];//記錄編號為i的原值 int num[N];//記錄眾數(shù) bool vis[N];//標(biāo)記數(shù)組 int maxx[2000+5][2000+5]; int tot;//記錄第幾個(gè)出現(xiàn)的數(shù) map<int,int> mp;//用于將序列轉(zhuǎn)換為編號 vector<int> V[N];//存儲編號相同時(shí)為原來的第幾個(gè)值，用于二分求眾數(shù) void init(int x){//預(yù)處理每塊間的眾數(shù)memset(num,0,sizeof(num));int modeNum=0,id=0;for(int i=(x-1)*block+1;i<=n;i++){num[a[i]]++;if(num[a[i]]>modeNum || (num[a[i]]==modeNum&&val[a[i]]<val[id])){//尋找最小眾數(shù)modeNum=num[a[i]];//更新眾數(shù)數(shù)量id=a[i];//記錄最小眾數(shù)的編號}maxx[x][pos[i]]=id;//記錄第i塊間的最小眾數(shù)編號} } int dich(int L,int R,int x){//二分找眾數(shù)return upper_bound(V[x].begin(),V[x].end(),R)-lower_bound(V[x].begin(),V[x].end(),L); } int query(int L,int R){memset(vis,false,sizeof(vis));int res=maxx[pos[L]+1][pos[R]-1];//中間一整塊的眾數(shù)int modeNum=dich(L,R,res);vis[res]=true;for(int i=L;i<=min(pos[L]*block,R);i++){//左邊的邊角料if(!vis[a[i]]){vis[a[i]]=true;int temp=dich(L,R,a[i]);if(temp>modeNum || (temp==modeNum&&val[a[i]]<val[res])){//尋找最小眾數(shù)modeNum=temp;//更新眾數(shù)數(shù)量res=a[i];//更新答案}}}if(pos[L]!=pos[R]){//存在右區(qū)間才遍歷，防止重復(fù)計(jì)算for(int i=(pos[R]-1)*block+1;i<=R;i++){//右邊的邊角料if(!vis[a[i]]){vis[a[i]]=true;int temp=dich(L,R,a[i]);if(temp>modeNum || (temp==modeNum&&val[a[i]]<val[res])){//尋找最小眾數(shù)modeNum=temp;//更新眾數(shù)數(shù)量res=a[i];//更新答案}}}}return val[res]; } int main(){scanf("%d",&n);block=80;//塊的長度sum=n/block;//塊個(gè)數(shù)if(n%block)sum++;for(int i=1;i<=n;i++){scanf("%d",&a[i]);pos[i]=(i-1)/block+1;//第i個(gè)元素在第幾塊中if(mp[a[i]]==0){mp[a[i]]=++tot;val[tot]=a[i];//保存原始值}a[i]=mp[a[i]];//保存為編號V[a[i]].push_back(i);}for(int i=1;i<=sum;i++)//預(yù)處理每塊間的眾數(shù)init(i);for(int i=1;i<=n;i++){int left,right;scanf("%d%d",&left,&right);printf("%d\n",query(left,right));}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的数列分块入门 9（LibreOj-6285）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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