题目描述

给出一个长为 nnn 的数列，以及 nnn 个操作，操作涉及询问区间的最小众数。

输入格式

第一行输入一个数字 nnn。

第二行输入 nnn 个数字，第 i 个数字为 aia_iai​，以空格隔开。

接下来输入 nnn 行询问，每行输入两个数字 lll、rrr，以空格隔开。

表示查询位于 [l,r][l,r][l,r] 的数字的众数。

输出格式

对于每次询问，输出一行一个数字表示答案。

样例

样例输入

41 2 2 41 21 42 43 4

样例输出

1222

数据范围与提示

对于 100% 100\%100% 的数据，1≤n≤100000,−231≤others 1 \leq n \leq 100000, -2^{31} \leq \mathrm{others}1≤n≤100000,−231≤others、ans≤231−1 \mathrm{ans} \leq 2^{31}-1ans≤231−1。

1 #include
          
             2 using namespace std;   3 #define F(i,a,b) for(int i=a;i<=b;i++)   4 #define D(i,a,b) for(int i=a;i>=b;i--)   5 #define ms(i,a)  memset(a,i,sizeof(a))   6 #define st(x)   ( (x-1)*B+1)   7 #define ed(x)   ( min(n, x*B))      8 #define bl(x)   ( (x-1)/B+1)   9 #define sum(x)  ( (n-1)/B+1)   10  11 int inline read(){ 12     int x=0 ;char c=getchar();  13     while (c<'0' || c>'9') c=getchar();  14     while (c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();  15     return x;  16 } 17  18 int const maxn=100003;  19  20 int n,m,B,cnt[maxn][401],v[401][401],num[401][401];  21 int a[maxn],b[maxn],c[maxn],tmp[maxn];   22  23 int query(int l,int r){ 24     int x=bl(l);  25     int y=bl(r);  26     int V,NUM=0;   27     if(x+1<=y-1){ 28         V=v[x+1][y-1];  29         NUM=num[x+1][y-1];   30     } 31     int s,e;  32     tmp[0]=0;   33     if(x==y){ 34         F(i,l,r) { 35             tmp[++tmp[0]]=a[i];  36             c[a[i]]++;  37         } 38     }else { 39         s=l;e=ed(x);   40         F(i,s,e) { 41             tmp[++tmp[0]]=a[i];   42             c[a[i]]++;   43         } 44         s=st(y);e=r;   45         F(i,s,e){ 46             tmp[++tmp[0]]=a[i];  47             c[a[i]]++;   48         } 49     } 50     F(i,1,tmp[0]) { 51         int t=x+1<=y-1?  cnt[tmp[i]][y-1]-cnt[tmp[i]][x]: 0;   52         if(c[tmp[i]]+t>NUM || ( c[tmp[i]]+t ==NUM  && V> tmp[i])) { 53             V=tmp[i]; NUM=c[tmp[i]]+t;   54         } 55     } 56     F(i,1,tmp[0])  c[tmp[i]]=0;   57     return V;   58 } 59  60 int main(){ 61     n=read();  62     //m=read(); 63     m=n;   64     F(i,1,n) a[i]=b[i]=read();  65     sort(b+1,b+n+1);  66     int k=unique(b+1,b+n+1)-b-1;  67     F(i,1,n) a[i]=lower_bound(b+1,b+k+1,a[i])-b;  68     B=(int)sqrt(n);  69     int t=sum(n);   70     F(i,1,t) { 71         ms(0,c);   72         int s=st(i);  73         int e=ed(i);  74         F(j,s,e) c[a[j]]++; 75         F(j,1,k) cnt[j][i]=cnt[j][i-1]+c[j];   76     } 77     F(i,1,t){ 78         ms(0,c);    79         F(j,i,t){ 80             int V=v[i][j-1];  81             int NUM=num[i][j-1];   82             int s=st(j);  83             int e=ed(j);   84             F(p,s,e){ 85                 c[a[p]]++ ;  86                 if (c[a[p]]> NUM || (NUM==c[a[p]] && a[p] < V)) { 87                     V=a[p]; NUM=c[a[p]];   88                 } 89             } 90             v[i][j]=V;  91             num[i][j]=NUM; 92         } 93     } 94     int x=0;  95     ms(0,c);   96     while (m--){ 97         int l=read();  98         int r=read();  99         x=1; 100         //l=(l+x-1+n) % n+1;  101         //r=(r+x-1+n) % n+1;102         if(l>r) swap(l,r); 103         printf("%d\n",x=b[query(l,r)]);104     }105     return 0;  106 }