离散化分块 在线查询区间众数由于a_i范围是1e9的,记录a_i出现的次数不方便直接用数组记录但是一共有n个数我们就可以把它们排序去重把a_i映射为在n个数中排第几这样映射后的值域就小于n了我们就能直接用数组记录了这就是离散化将长度为 n 的数组分块每块长度为 Bsqrt(n)比如[0,B),[B,2*b)...[k*B,n)对于所查询的区间 [l ,r] 设l位于块bl, r位于块br,|-------------------p1----------------p2---------------------|| ------l-------------|-------------------|-----------r----------|其中p1 (bl1)*B,p2 br*B-1该区间的众数只可能为在 $[l,p1) ∪ (p2,r]$内出现的数 和 块 $[bl1,br-1]$的众数之间因为在加[l,p1) ∪ (p2,r]内出现的数的时候才会改变 块 [bl1,br-1]的众数当bl和br位于同一个块或相邻块为了方便些代码就直接暴力复杂度最大$2*sqrt(n)$否则就是在cnt数组中只维护[l,p1) ∪ (p2,r]内出现的数 和 块 [bl1,br-1]的众数,这些数字最多也是sqrt(n)级别的在遍历l-p_1和p_2-r用vis数组判断是否已经加了某个数在[p1,p2]中的出现次数p1-p2所有数出现的次数用前缀和维护这样总复杂度就是O(nlog(n)(nq)*sqrt(n))ac代码如下:#includebits/stdc.h using namespace std; #define ull signed long long // #define int long long #define CINT \ // cinT; void solve(){ int n,q;cinnq; vectorint a(n); for(int i 0;in;i){ cina[i]; } vectorint b a; // 离散化 sort(b.begin(),b.end()); b.erase(unique(b.begin(),b.end()),b.end()); for(int i 0;in;i){ a[i] lower_bound(b.begin(),b.end(),a[i])-b.begin(); } int B sqrt(n); // 前缀和,存前i块各个数字出现的次数 vectorvectorint pre((n-1)/B1,vectorint (b.size())); for(int i 0;in;iB){ if(i!0) pre[i/B] pre[i/B-1]; for(int j i;jmin(n,iB);j){ pre[i/B][a[j]]; } } // f[i][j]表示第i块到第j块的众数 vectorvectorint f((n-1)/B1,vectorint ((n-1)/B1)); vectorint cnt(b.size()),vis(b.size()); for(int i 0;i(n-1)/B;i){ int p 0,mx 0; fill(cnt.begin(),cnt.end(),0); for(int j i;j(n-1)/B;j){ for(int k j*B;kmin(n,j*BB);k){ cnt[a[k]]; if(cnt[a[k]]mx || (cnt[a[k]]mx and a[k]p)){ p a[k]; mx cnt[a[k]]; } } f[i][j] p; } } fill(cnt.begin(),cnt.end(),0); auto upd [](int num,int p,int mx,int bl,int br){ if(!vis[num]){ //判断指定在中间区间的出现次数是否已经被加过 vis[num] 1; cnt[num] pre[br-1][num]-pre[bl][num]; } if(cnt[num]mx || (cnt[num]mx and nump)){ p num; mx cnt[num]; } }; int x 0; while(q--){ int l,r;cinlr; l (lx-1)%n1;r (rx-1)%n1; l--,r--; if(lr) swap(l,r); int bl l/B,br r/B; int p 0,mx 0; if(br-bl1){ //区间长度小于2*sqrt(n)直接暴力 for(int i l;ir;i){ cnt[a[i]]; if(cnt[a[i]]mx || (cnt[a[i]]mx and a[i]p)){ p a[i]; mx cnt[a[i]]; } } for(int i l;ir;i){ cnt[a[i]] 0; } }else{ for(int i l;i(bl1)*B;i){ cnt[a[i]]; upd(a[i],p,mx,bl,br); } for(int i br*B;ir;i){ cnt[a[i]]; upd(a[i],p,mx,bl,br); } upd(f[bl1][br-1],p,mx,bl,br); // 还原操作 for(int i l;i(bl1)*B;i) cnt[a[i]] vis[a[i]] 0; for(int i br*B;ir;i) cnt[a[i]] vis[a[i]] 0; cnt[f[bl1][br-1]] vis[f[bl1][br-1]] 0; } x b[p]; coutb[p]\n; } } signed main(){ std::cin.tie(nullptr)-sync_with_stdio(false); int T 1; CINT; while(T--) solve(); return 0;