题目：给你一个长度为n的序列，m次询问，询问 区间 [ L , R ] 中的众数出现的次数，输出 - ans;
思路： 回滚莫队 裸题
#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=2e5+111; int a[N],b[N],c[N],cnt[N],pos[N],n,block,m; int tmp,ans[N]; 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; rep(i,l,r) { ++t[b[i]]; w=max(w,t[b[i]]); } return w; } void add(int x) { ++cnt[b[x]]; tmp=max(tmp,cnt[b[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; ///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; ///记录 l 指针 移动前的 tmp 值 while(l>q[i].l) add(--l); ans[q[i].id]=tmp; ///记录答案 tmp=w; ///还原 tmp while(l<L+1) --cnt[b[l++]]; /// l 滚回块尾+1 } return i; ///处理完这一块后，处理到第i个查询 } int main() { scanf("%d %d",&n,&m); 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,m) { scanf("%d %d",&q[i].l,&q[i].r); q[i].id=i; } sort(q+1,q+1+m,cmp); int pp=1; ///处理到的 q[i]，pp即为i； rep(i,1,up) { pp=slove(pp,i); } rep(i,1,m) printf("%d ",-ans[i]); return 0; }
但是 我看了 别人的代码， 人家 好像 也不用 回滚莫队啊， 可以用普通莫队的，就是对删除操作维护好就行，多开个 数组 sum[ i ] 存的是 出现次数 为 i 的数有多少个， 然后删除操作的时候 如果 出现 mode次数的数只有一个 即 sum [ mode ] = 1； 这时，你的 mode-- 就行了，不然的话咧， mode 不变；
#include <bits/stdc++.h> using namespace std; const int N = 1e7 + 10; int n, m, mode; int a[N], b[N], cnt[N], sum[N], ans[N]; class node { public : int l, r, id, bl; bool operator < (const node &oth) const { return this->bl == oth.bl ? this->r < oth.r : this->l < oth.l; } } e[N]; template<class T>inline void read(T &x) { x = 0; int f = 0; char ch = getchar(); while (!isdigit(ch)) f |= (ch == '-'), ch = getchar(); while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); x = f ? -x : x; return; } inline void add(int x) { sum[cnt[a[x]]]--, sum[++cnt[a[x]]]++, mode = max(mode, cnt[a[x]]); //前两句是维护sum这个数出现的次数。 } inline void del(int x) { if (cnt[a[x]] == mode && sum[cnt[a[x]]] == 1) mode--; sum[cnt[a[x]]]--; sum[--cnt[a[x]]]++; } int main() { read(n), read(m); int k = sqrt(n); for (int i = 1; i <= n; ++i) read(a[i]), b[i] = a[i]; sort(b + 1, b + 1 + n); int len = unique(b + 1, b + 1 + n) - b - 1; for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + 1 + len, a[i]) - b; for (int i = 1, x, y; i <= m; ++i) { read(x), read(y); e[i] = (node) {x, y, i, x / k + 1}; } sort(e + 1, e + 1 + m); int l = 1, r = 0; for (int i = 1; i <= m; ++i) { int ll = e[i].l, rr = e[i].r; while (l < ll) del(l++); while (l > ll) add(--l); while (r < rr) add(++r); while (r > rr) del(r--); ans[e[i].id] = mode; } for (int i = 1; i <= m; ++i) printf("%d ", -ans[i]); return 0; }