题目 ： 链接 ：https://loj.ac/problem/6285
题意：给出一个长为 n的数列，以及 n个操作，操作涉及询问区间的最小众数。
思路：虽然这不是一道 回滚莫队题，就是 暴力分块 的题， 但是 还是 可以用回滚莫队 写滴，好像大部分题解都是 暴力分块。
#include<bits/stdc++.h> #define LL long long #define ULL unsigned long long #define rep(i,j,k) for(int i=j;i<=k;i++) #define dep(i,j,k) for(int i=k;i>=j;i--) #define INF 0x3f3f3f3f #define mem(i,j) memset(i,0,sizeof(i)) #define make(i,j) make_pair(i,j) #define pb push_back using namespace std; const int N=1e5+111; int a[N],b[N],c[N],cnt[N],pos[N],n,block; int tmp,ans[N],coun; struct noq { int l,r,id; }q[N]; bool cmp(noq a,noq b) { return pos[a.l]==pos[b.l]?a.r<b.r:pos[a.l]<pos[b.l]; } int query(int l,int r) { ///暴力求答案 int t[N]; rep(i,l,r) t[b[i]]=0; int w=0,ww=0; rep(i,l,r) { ++t[b[i]]; if(t[b[i]]>=ww) { if(t[b[i]]==ww && a[i]<w) w=a[i]; else if(t[b[i]]>ww) ww=t[b[i]],w=a[i]; } } return w; } void add(int x) { ++cnt[b[x]]; if(cnt[b[x]]>=coun) { if(cnt[b[x]]==coun && a[x]<tmp) tmp=a[x]; else if(cnt[b[x]]>coun) coun=cnt[b[x]],tmp=a[x]; } } int slove(int qnum,int bnum) { ///处理 第 bnum 块, 现在 处理到 q[qnum] 这个查询 int i=qnum; int L=min(bnum*block,n); int l=L+1,r=L; tmp=0; coun=0; ///L 即为块尾 rep(j,1,n) cnt[j]=0; ///初始化，每处理一个块 都要 搞一次的啦 for(;pos[q[i].l]==bnum;i++) { if(pos[q[i].l]==pos[q[i].r]) {/// l,r 在同一块，暴力处理 ans[q[i].id]=query(q[i].l,q[i].r); continue; } while(r<q[i].r) add(++r); ///先移动 r 指针 int w=tmp,ww=coun; ///记录 l 指针 移动前的 tmp 和 coun 值 while(l>q[i].l) add(--l); ans[q[i].id]=tmp; ///记录答案 tmp=w; coun=ww; ///还原 tmp 和 coun while(l<L+1) --cnt[b[l++]]; /// l 滚回块尾+1 } return i; ///处理完这一块后，处理到第i个查询 } int main() { scanf("%d",&n); block=sqrt(n); rep(i,1,n) { scanf("%d",&a[i]); c[i]=a[i]; pos[i]=(i-1)/block+1;///一定要加1喔，因为slove的时候l,r初始化需要 } int up=pos[n]; ///块数 sort(c+1,c+1+n); int newn=unique(c+1,c+1+n)-(c+1); rep(i,1,n) { b[i]=lower_bound(c+1,c+1+newn,a[i])-c;///数据太大，离散化a[i] } rep(i,1,n) { scanf("%d %d",&q[i].l,&q[i].r); q[i].id=i; } sort(q+1,q+1+n,cmp); int pp=1; ///处理到的 q[i]，pp即为i； rep(i,1,up) { pp=slove(pp,i); } rep(i,1,n) printf("%d\n",ans[i]); return 0; }
