「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}^3nt3最优
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 ~