题目分析

付费题哈哈。题意就是求区间众数，由于区间众数无法快速合并，所以不能使用传统的数据结构如线段树等。

这时分块就能派上很大的用场。将序列分成$\sqrt{n}+$块，每块大小$\sqrt{n}+$，通过预处理得到cnt[i][j], ans[i][j]分别表示i在前j块中出现的次数，和第i块到第j块的众数是多少。

那么查询时我们就得到了至多$\sqrt{n}$个连续的块，和至多$2\sqrt{n}$个零散的元素，对于零散的元素，暴力，对于连续的块，直接使用预处理。

code

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std; const int N = 4e4 + 5, oo = 0x7fffffff;int n, m, S;int val[N], num[N], len;int blk[N], bl[300], br[300], blkCnt, sum[N];int ans[300][300], cnt[N][300]; int read(){ int i=0,f=1;char ch; for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar()); if(ch=='-') {f=-1;ch=getchar();} for(;ch>='0'&&ch<='9';ch=getchar()) i=(i<<3)+(i<<1)+(ch^48); return f*i;} inline void wr(int x){ if(x < 0) putchar('-'), x = -x; if(x > 9) wr(x / 10); putchar(x % 10 + '0');} inline void disc_init(){ sort(num + 1, num + len + 1); len = unique(num + 1, num + len + 1) - (num + 1); for(int i = 1; i <= n; i++) val[i] = lower_bound(num + 1, num + len + 1, val[i]) - num;// for(int i = 1; i <= n; i++) cout<
            
             <
             
               maxx) maxx = ret, cur = val[k]; else if(ret == maxx && val[k] < cur) cur = val[k]; } ans[i][j] = cur; } }} inline int query(int l, int r){ if(l > r) swap(l, r); int blk_L = blk[l] + 1, blk_R = blk[r] - 1; if(bl[blk_L - 1] == l) blk_L--; if(br[blk_R + 1] == r) blk_R++; if(blk_L > blk_R){ int sum[N] = { 0}, maxx = -oo, ret = oo; for(int i = l; i <= r; i++){ int c = ++sum[val[i]]; if(c > maxx) maxx = c, ret = val[i]; else if(c == maxx && val[i] < ret) ret = val[i]; } return ret; } int ret = ans[blk_L][blk_R], sum[N] = { 0}, ret_cnt = cnt[ret][blk_R] - cnt[ret][blk_L - 1]; for(int i = l; i < bl[blk_L]; i++){ int c; if(sum[val[i]]) c = ++sum[val[i]]; else{ sum[val[i]] = cnt[val[i]][blk_R] - cnt[val[i]][blk_L - 1]; c = ++sum[val[i]]; } if(c > ret_cnt) ret = val[i], ret_cnt = c; else if(c == ret_cnt && val[i] < ret) ret = val[i]; } for(int i = br[blk_R] + 1; i <= r; i++){ int c; if(sum[val[i]]) c = ++sum[val[i]]; else{ sum[val[i]] = cnt[val[i]][blk_R] - cnt[val[i]][blk_L - 1]; c = ++sum[val[i]]; } if(c > ret_cnt) ret = val[i], ret_cnt = c; else if(c == ret_cnt && val[i] < ret) ret = val[i]; } return ret;} int main(){ //freopen("h.in","r",stdin); n = read(), m = read(); S = 400; for(int i = 1; i <= n; i++) val[i] = num[++len] = read(); disc_init(); initBlk(); initData(); int ans = 0; for(int i = 1; i <= m; i++){ int l = read(), r = read(); l = (l + ans - 1) % n + 1, r = (r + ans - 1) % n + 1; wr(ans = num[query(l, r)]), putchar('\n'); } return 0;}