标签:# 莫队算法

「专题训练」 莫队算法

「BZOJ 2038」小Z的袜子 莫队模版题 处理出询问区间中每种颜色的数量,计算出抽中相同颜色袜子的数量即可 「NBUT 1457」Sona 莫队维护区间立方和,直接减去原来的立方和,更改后加上现在的立方和,不需要计算公式 「CF 940F」 Machine Learning 带修莫队+暴力统计 因为要塞入1,2,3,....k1,2,3,....k1,2,3,....k时,需要k∗(k+1)2\frac{k*(k+1)}{2}2k∗(k+1)​个元素,因此nnn个元素最多填充n\sqrt{n}n​个区间,因此答案的区间不会超过n\sqrt{n}n​ 「CF 617F」XOR and Favorite Number 莫队算法 异或部分可以用前缀和解决,设pre[i] = a[1] ^ \cdots ^ a[o] 在莫队的过程中,假设当前区间为[l,r−1][l,r-1][l,r−1],更新至[l,r][l,r][l,r]时,新增了一个 pre[r]pre[r]pre[r],那么对于答案的新增的贡献是在区间[l,r−1][l,r-1][l,r−1]中,有多少个pre[r]kpre[r] ^ kpre[r]k 「洛谷 P3604」美好的每一天 状态压缩 + 莫队算法 将 26 个字母的出现的奇偶性压缩成一个数字,然后对于是否为回文串,只需要确认某个区间只有的数字为0或为2的整次幂 前缀和一下就跟上题差不多了 「AT1219」 歴史の研究 回滚莫队 对于某些不好做减处理的莫队问题,对于左端点同一个块中问题,我们可以进行反复回滚操作,使得不存在减问题 const ll mod = 1e9+7; const int N = 2e5+10; int block; struct node { int id,l,r; }q[N]; int cntl[N],cntr[N],b[N],d[N],e[N]; bool cmp(node x,node y) { if(b[x.l] == b[y.l]) return x.r < y.r; return x.l < y.l; } int a[N],vl,vr; int n,m; ll res[N]; ll clca(int l,int r) { int last[N]; ll res = 0ll; for(int i=l;i<=r;i++) last[a[i]]=0; for(int i=l;i<=r;i++) { last[a[i]]++; res = max(1ll * last[a[i]] * e[i],res); } return res; } void solve() { ll rans = 0; for(int i=1,l=1,r=0;i<=m;i++) { if(b[q[i-1].l] != b[q[i].l] || i == 0) { FOR(j,vl,vr) cntr[a[j]] = 0; rans = 0; l = min(n,block*b[q[i].l]); r = l -1; vl = r; } if(b[q[i].l]== b[q[i].r]) res[q[i].id] = clca(q[i].l,q[i].r); else { // putchar('-'); // PLN2(q[i].l,q[i].r); ll ans = 0; while(l > q[i].l) { --l;int x = a[l]; cntl[x]++; ans = max(1ll * (cntl[x] + cntr[x]) * e[l],ans); } while (r < q[i].r) { ++r;int x= a[r]; cntr[x]++; ans = max(1ll * (cntl[x] + cntr[x]) * e[r],ans); rans = max(1ll*cntr[x] * e[r],rans); } vr = max(r,vr); while(l < min(n,block*b[q[i].l])) cntl[a[l]] = 0,++l; res[q[i].id] = max(ans,rans); } } } map<int,int> mp; int main() { // __IN;__OUT; RLL2(n,m); FOR(i,1,n) RLL(e[i]); FOR(i,1,n) d[i] = e[i]; sort(d+1,d+1+n); int tot = 0; FOR(i,1,n)if(!mp[d[i]]) mp[d[i]] = ++tot; FOR(i,1,n) a[i] = mp[e[i]]; // FOR(i,1,n) PLP(c[i]);PN(); block = sqrt(n); FOR(i,1,n) b[i] = (i-1)/block+1; FOR(i,1,m) RLL2(q[i].l,q[i].r); FOR(i,1,m) q[i].id = i; sort(q+1,q+1+m,cmp); // FOR(i,1,m)PLN2(q[i].l,q[i].r); solve(); FOR(i,1,m) PLN(res[i]); return 0; } 「洛谷 P1903」[国家集训队]数颜色 / 维护队列 带修莫队 在原有基础上加上一维时间,处理出每个询问出现那那个时间段,在莫队移动的时候多移动时间即可 区间大小为nnn ,修改次数为ttt时,块的大小为 nt3\sqrt{nt}^3nt​3最优 int block = ceil(exp((log(n)+log(t))/3)) 「WC2013」糖果公园 树上带修莫队 可以将树的欧拉序求出来,存每个点在欧拉序中出现的第一次位置和最后一次位置 对于区间内出现两次的值,不予以统计 如果两点不在树的同一子树内,则需要格外统计lcalcalca 然后将树上询问变成区间询问,然后跟上题一样
Read More ~

「Template」莫队算法

能用int 尽量用int,不然很容易超时 const int N = 2e6; int c[N],blo[N],d[N]; map<int,int> mp; ll ans,cnt[N]; struct node{int l,r,id;ll pp;}a[N]; bool cmp1(const node a,const node b) {if(blo[a.l]==blo[b.l])return a.r<b.r;return a.l<b.l;} bool cmp(const node a,const node b) {return a.id < b.id;} void add(int x) { ans -= (cnt[x] > 0); cnt[x]++; ans += (cnt[x] > 0); } void del(int x) { ans -= (cnt[x] > 0); cnt[x]--; ans += (cnt[x] > 0); } void solve(int num) { for(int i=1,l=1,r=0;i<=num;i++) { for(;r<a[i].r;r++)add(c[r+1]); for(;r>a[i].r;r--)del(c[r]); for(;l<a[i].l;l++)del(c[l]); for(;l>a[i].l;l--)add(c[l-1]); a[i].pp = ans; } } int main() { // __IN;__OUT; int n,m;RLL(n); FOR(i,1,n) RLL(c[i]); //如果需要离散化 // FOR(i,1,n) d[i] = c[i]; // sort(d+1,d+1+n); // int tot = 0; // FOR(i,1,n)if(!mp[d[i]]) mp[d[i]] = ++tot; // FOR(i,1,n) c[i] = mp[c[i]]; // FOR(i,1,n) PLP(c[i]);PN(); RLL(m); int block = n/sqrt((m>>1)/3); FOR(i,1,n) blo[i] = (i-1)/block+1; FOR(i,1,m) RLL2(a[i].l,a[i].r); FOR(i,1,m) a[i].id = i; sort(a+1,a+1+m,cmp1); solve(m); sort(a+1,a+1+m,cmp); FOR(i,1,m) PLN(a[i].pp); return 0; }
Read More ~