这里只支持查询不支持修改，总的时间复杂度为O（(n+q)*√n）

1 #include
     
        2 #include
      
         3 #include
       
          4 using namespace std;  5 const int maxn=100005;  6 int n,m,blo;  7 int a[maxn],t[maxn],bl[maxn];  8 int cnt[505][maxn],f[505][505];  9 //cnt[i][j]表示[0,i]块上数字j的数量 10 //f[i][j]表示第i块到第j块的众数是几 11 inline long long read() 12 { 13     long long x=0,f=1;char ch=getchar(); 14     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();} 15     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 16     return x*f; 17 } 18 void init() 19 { 20     for(int i=1;i<=bl[n];i++) 21     { 22         for(int j=1;j<=m;j++) 23             cnt[i][j]+=cnt[i-1][j]; 24     } 25     for(int i=1;i<=bl[n];i++) 26     { 27         int num[maxn]; 28         int mode=0; 29         int mx=0; 30         for(int k=1;k<=m;k++) num[k]=0; 31         for(int j=(i-1)*blo+1;j<=n;j++) 32         { 33             num[a[j]]++; 34             if(num[a[j]]>mx||(num[a[j]]==mx&&mode>a[j])) 35             { 36                 mode=a[j]; 37                 mx=num[a[j]]; 38             } 39             f[i][bl[j]]=mode; 40         } 41     } 42 } 43 void force(int l,int r) 44 { 45     int num[maxn]; 46     int mode=0; 47     int mx=0; 48     for(int i=1;i<=m;i++) num[i]=0; 49     for(int i=l;i<=r;i++) 50     { 51         num[a[i]]++; 52         if(num[a[i]]>mx||(num[a[i]]==mx&&mode>a[i])) 53         { 54             mode=a[i]; 55             mx=num[a[i]]; 56         } 57     } 58     printf("%d\n",t[mode]); 59 } 60 void solve(int t1,int t2,int l,int r,int *num,int &mode,int &mx) 61 { 62     for(int i=l;i<=r;i++) 63     { 64         num[a[i]]++; 65         int tmp=num[a[i]]+cnt[t2-1][a[i]]-cnt[t1][a[i]]; 66         if(tmp>mx||(tmp==mx&&a[i]