简介
对于一些区间查询问题, 当询问与数组大小同阶时, 把询问按块排序, 可以得到均摊根号复杂度的算法.
普通莫队
不含修改, 单点加入/删除均较快 ( (O(1)) 或 (O(log n)) 等).
流程
- 区间大小 (S = sqrt n)
- 排序:
- 按 ((lceil frac lS ceil , r)) 二元组排序
- 移动左右指针转移
复杂度 (O(nsqrt n)).
带修改莫队
可以单点较快修改.
流程
- 区间大小 (S = n^{frac 23})
- 排序:
- 将询问按 ((leftlceilfrac l S ight ceil, leftlceilfrac r S ight ceil, t)) 三元组排序
- 修改不需排序
- 维护 (l,r,t) 三个指针转移
复杂度 (O(n^{frac 53})).
代码
struct tq{int l,r,t,id;}q[qsz];
struct tc{int p,v;}c[qsz];
bool cmp(tq l,tq r){return inb[l.l]!=inb[r.l]?inb[l.l]<inb[r.l]:inb[l.r]!=inb[r.r]?inb[l.r]<inb[r.r]:l.t<r.t;}
void solp(int p){
//do sth
}
void solc(int p,int c){
//do sth
}
void mo(){
sort(q+1,q+pq+1,cmp);
int t=0,l=1,r=0;
rep(i,1,pq){
while(t<q[i].t)++t,solc(c[t].p,c[t].t);
while(t>q[i].t)solc(c[t].p,c[t].v),--t;
while(l<q[i].l)solp(seq[l++]);
while(l>q[i].l)solp(seq[--l]);
while(r<q[i].r)solp(seq[++r]);
while(r>q[i].r)solp(seq[r--]);
ans[q[i].id]=ans0;//update ans
}
}
树上莫队
序列变成树, 询问子树/链信息.
子树
转化成dfs序, 然后就变成区间信息了.
链
记录欧拉序, 即每个点入和出各记录一次,记为in(a), out(a).
考虑树上的一个链 ([a,b]), 不妨设in(a)<=in(b).
当a, b都不在另一个的子树中时, 它等价于dfs序中的 ([out(a), in(b)] + lca(a,b)) ,其中出现过两次的点不统计;
当b在a的子树中时, 它等价于dfs序中的 ([in(a), in(b)]) ,其中出现过两次的点不统计.
这样就也转化为了区间信息, 细节可能有所不同.
或者王室联邦分块... 不会
代码/题目
单调莫队(回滚莫队)
有时增加的复杂度较小, 但删除复杂度较大. 考虑只用增加实现.
流程
- 分块 && 排序, 同普通莫队.
- 若询问在一个块内, 直接暴力;
- 对于其他询问: 枚举块 ([L_s,R_s]), 处理左端点在该块内的询问:
- 起始左指针为 (R_s + 1), 右指针为 (R_s) ;
- 对于右指针, 根据排序, 同块内询问的右端点递增, 右移指针, 维护加入点即可;
- 对于左指针, 对于每个询问
- 保存当前的状态
- 维护左指针向左移动, 加入点
- 询问完成后恢复左指针到 (R_s + 1), 并恢复原来的状态.
容易发现时间复杂度仍为 (O(nsqrt n)).
同样, 当增加的复杂度较大, 但删除复杂度较小时, 也可以只利用删除实现莫队.
即先生成 ([L_s, n]) 的答案, 然后单点删除. 这时不需要特殊处理在同一块内的询问, 直接移动指针即可.
复杂度也为 (O(nsqrt n)).
代码
//单减莫队
for(int i=1,r=1;i<=m;i=r+1,r=i){
int lbl=inbl[qu[i].l],lp=(lbl-1)*blsz+1;
while(r<n&&inbl[qu[r+1].l]==lbl)++r;
//generate ans of [lp, n]
gene(lp,n);
int p1=lp,p2=n;
rep(j,i,r){
while(p2>qu[j].r)del(p2),--p2;
while(p1<qu[j].l)del(p1),++p1;
ans[qu[j].id]=ans0;
while(p1>lp)undel(p1-1),--p1;
}
}