常用算法学习笔记
Post time: 2021-05-18 16:48:40
整体二分
模板题：\(q\) 次查询区间第 \(k\) 小，带单点修改。\(n,q\leq 10^5\)。
考虑如果只有一次询问，有一个做法是考虑在值域 \([L,R]\) 上二分答案 \(mid\)，把所有 \(\leq mid\) 的数设为 \(1\)，否则设为 \(0\)，如果查询区间 \([l,r]\) 内的和 \(\geq k\)，说明答案在 \([L,mid]\) 里，否则在 \([mid+1,R]\) 里。这样做的复杂度是 \(O(n\log v)\)。
如果有 \(q\) 组询问，暴力做法就是对于每个询问都做一遍这个做法。但是这样显然复杂度爆炸，考虑合并这些询问。因为每一次求解都是在同一个值域上二分，不妨把所有询问一起二分答案 \(mid\)。把所有答案在 \([L,mid]\) 的询问放到左边递归，答案在 \([mid+1,R]\) 的询问放在右边递归，当 \(L=R\) 或者区间内没有询问时终止。这样，只需要快速统计区间内的和了。这显然可以用树状数组实现，所以总的复杂度是 \(O(n\log n\log v)\)。
有修改操作怎么办？考虑把修改操作拆成删除和插入，和询问一起按照时间顺序做上边的操作，如果这个操作是加入或删除，则在树状数组里 \(+1\) 或者 \(-1\)。这样就可以直接用上面那个做法做了，复杂度不变。
模板P2617
点击查看代码
#include
#include
#include
#include
using namespace std;
const int N=1e5+13;
struct Node{int op,x,y,z;}q[N<<2],lq[N<<2],rq[N<<2];
int n,m,ans[N],a[N];
struct BIT{
int t[N];
inline int lowbit(int x){return x&-x;}
inline void add(int x,int k){for(;x<=n;x+=lowbit(x))t[x]+=k;}
inline int sum(int x){int res=0;for(;x;x-=lowbit(x))res+=t[x];return res;}
}T;
void solve(int L,int R,int l,int r){
if(l>r) return;
if(L==R){
for(int i=l;i<=r;++i)
if(q[i].op>0) ans[q[i].op]=L;
return;
}
int mid=(L+R)>>1;
int lt=0,rt=0;
for(int i=l;i<=r;++i){
if(q[i].op<=0){
if(q[i].y<=mid) T.add(q[i].x,q[i].op?-1:1),lq[++lt]=q[i];
else rq[++rt]=q[i];
}
else{
int cnt=T.sum(q[i].y)-T.sum(q[i].x-1);
if(cnt>=q[i].z) lq[++lt]=q[i];
else rq[++rt]=q[i],rq[rt].z-=cnt;
}
}
for(int i=l;i<=r;++i)
if(q[i].op<=0&&q[i].y<=mid) T.add(q[i].x,q[i].op?1:-1);
for(int i=1;i<=lt;++i) q[l+i-1]=lq[i];
for(int i=1;i<=rt;++i) q[l+lt+i-1]=rq[i];
solve(L,mid,l,l+lt-1);
solve(mid+1,R,l+lt,r);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&a[i]),q[i].x=i,q[i].y=a[i];
int cnt=n;
for(int i=1;i<=m;++i){
char in;cin>>in;
if(in=='Q') ++cnt,q[cnt].op=i,scanf("%d%d%d",&q[cnt].x,&q[cnt].y,&q[cnt].z);
else{
int xx,yy;scanf("%d%d",&xx,&yy);
q[++cnt].x=xx,q[cnt].y=yy;
q[++cnt].x=xx,q[cnt].y=a[xx];
a[xx]=yy,q[cnt].op=-1;
}
}
memset(ans,-1,sizeof ans);
solve(0,1e9,1,cnt);
for(int i=1;i<=m;++i)
if(ans[i]!=-1) printf("%d\n",ans[i]);
return 0;
}
动态dp（动态树分治）
一般是对于一些比较简单的树形dp问题，加上了单点修改的操作。模板：树上最大权独立集，单点修改，\(n,q\leq 10^5\)。
首先考虑没有修改的情况，设 \(f_{i,0}\) 表示不选 \(i\) 号点子树内的最大答案，\(f_{i,1}\) 表示选 \(i\) 号点（儿子都不选）的最大答案，写出dp式子
\[\begin{aligned} f_{u,0}&=\sum_{v\in son(u)}\max(f_{v,0},f_{v,1})\\ f_{u,1}&=\sum_{v\in son(u)} f_{v,0} \end{aligned} \]当进行一次单点修改的时候，事实上只可能会修改从修改点到根的路径上的点的dp值。若想动态维护，那么可以很自然的想到进行重链剖分，这样每个点到根的路径上最多只会有 \(O(\log n)\) 条重链。
如何在每条重链上动态维护 dp 值呢？首先引入一个广义矩阵乘法 \(A* B=C\)，其中
\[C_{i,j}=\max_k(A_{i,k}+B_{k,j}) \]也就是将原来矩阵乘法的乘变加、加变 \(\max\)，可以证明这样的矩阵乘法也满足结合律。
构造一个答案矩阵 \(\begin{bmatrix}f_{i,0}\\f_{i,1}\end{bmatrix}\)，考虑转移：由于这里出现了轻重链以及轻重儿子的区分，所以需要重新设计dp状态： \(g_{i,0}\) 表示不选 \(i\)，只考虑轻儿子时的答案；\(g_{i,1}\) 表示选 \(i\)，只考虑轻儿子时的答案。设 \(u\) 的重儿子为 \(s[u]\)，则
\[\begin{aligned} f_{u,0}&=g_{u,0}+\max(f_{s[u],0},f_{s[u],1})\\ f_{u,1}&=g_{u,1}+f_{s[u],0} \end{aligned} \]把它化成广义矩阵乘法的形式，即
\[\begin{aligned} f_{u,0}&=\max(g_{u,0}+f_{s[u],0},g_{u,0}+f_{s[u],1})\\ f_{u,1}&=\max(g_{u,1}+f_{s[u],0},-\infty) \end{aligned} \]化为矩阵形式，即
\[\begin{bmatrix} g_{u,0} & g_{u,0}\\ g_{u,1} & -\infty \end{bmatrix} * \begin{bmatrix}f_{s[u],0}\\f_{s[u],1}\end{bmatrix} = \begin{bmatrix}f_{u,0}\\f_{u,1}\end{bmatrix} \]每一段重链的结尾都一定是叶子结点，在这个结点存下 \(f\) 答案数组，然后就可以一步一步向上更新，利用线段树维护即可。单点修改的时候只需要修改每条重链的链尾，通过链头的 \(g\) 值去更新上一个链链尾的 \(f\) 值即可。最后的查询直接查整条 \(1\) 的重链即可。
模板P4719
点击查看代码
#include
#include
#include
using namespace std;
inline int max(const int &a,const int &b){return a>b?a:b;}
const int N=1e5+13,INF=0x3f3f3f3f;
struct Matrix{
int d[3][3];
Matrix(){memset(d,0,sizeof d);}
Matrix operator *(const Matrix &A)const{
Matrix Ans;
for(int i=1;i<=2;++i)
for(int j=1;j<=2;++j)
for(int k=1;k<=2;++k)
Ans.d[i][j]=max(Ans.d[i][j],d[i][k]+A.d[k][j]);
return Ans;
}
}g[N];
struct Edge{int v,nxt;}e[N<<1];
int n,m,a[N],h[N],tot;
int fa[N],siz[N],dep[N],f[N][2],son[N],top[N],id[N],b[N],dfs_clock,ed[N];
inline void add_edge(int u,int v){e[++tot]=(Edge){v,h[u]};h[u]=tot;}
void dfs1(int u,int father,int deep){
fa[u]=father,siz[u]=1,dep[u]=deep;
f[u][0]=0,f[u][1]=a[u];
int maxson=0;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(v==father) continue;
dfs1(v,u,deep+1);siz[u]+=siz[v];
if(siz[v]>maxson) maxson=siz[v],son[u]=v;
f[u][0]+=max(f[v][0],f[v][1]),f[u][1]+=f[v][0];
}
}
void dfs2(int u,int topf){
top[u]=topf,id[u]=++dfs_clock,b[dfs_clock]=u;
g[u].d[2][1]=a[u],g[u].d[2][2]=-INF;
ed[topf]=dfs_clock;
if(!son[u]) return;
dfs2(son[u],topf);
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
g[u].d[1][1]+=max(f[v][0],f[v][1]);
g[u].d[2][1]+=f[v][0];
}
g[u].d[1][2]=g[u].d[1][1];
}
struct SegTree{int l,r;Matrix x;}t[N<<2];
#define ls p<<1
#define rs p<<1|1
#define mid ((t[p].l+t[p].r)>>1)
inline void refresh(int p){t[p].x=t[ls].x*t[rs].x;}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r) return void(t[p].x=g[b[l]]);
build(ls,l,mid),build(rs,mid+1,r);
refresh(p);
}
void update(int p,int x){
if(t[p].l==t[p].r) return void(t[p].x=g[b[x]]);
update(x<=mid?ls:rs,x);
refresh(p);
}
Matrix query(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r) return t[p].x;
if(r<=mid) return query(ls,l,r);
if(l>mid) return query(rs,l,r);
return query(ls,l,r)*query(rs,l,r);
}
inline void t_update(int u,int w){
g[u].d[2][1]+=w-a[u];a[u]=w;
while(u){
Matrix las=query(1,id[top[u]],ed[top[u]]);
update(1,id[u]);
Matrix now=query(1,id[top[u]],ed[top[u]]);
u=fa[top[u]];
g[u].d[1][1]+=max(now.d[1][1],now.d[2][1])-max(las.d[1][1],las.d[2][1]);
g[u].d[1][2]=g[u].d[1][1];
g[u].d[2][1]+=now.d[1][1]-las.d[1][1];
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1,u,v;i 动态点分治（点分树）
考虑把点分治的过程建成树，这棵树的性质有：每一层的点所属连通块大小和为 \(O(n)\)，共有最多 \(O(\log n)\) 层。所以有些动态问题的操作可以直接在点分树上暴力跳祖先修改。
例题 [ZJOI2007]捉迷藏
考虑在点分树上维护两个堆：\(d_u\) 维护 \(u\) 为根的连通块上的所有黑点到 \(fa_u\) （点分树上父亲）的距离，\(ch_u\) 维护 \(u\) 每个子树中到 \(u\) 最远的点，那么答案就是所有 \(ch_u\) 的最大值和次大值和的最大值，每个点的答案也一起放到答案堆中。
每次修改的时候，在点分树上暴力跳，更新 \(d\) 和 \(ch\) 堆，再重新把答案加到答案堆里边去。查询直接输出。
点击查看代码
const int N=1e5+13;
struct Edge{int v,nxt;}e[N<<1];
struct Heap{
std::priority_queue p,q;
inline void insert(int x){p.push(x);}
inline void erase(int x){q.push(x);}
inline int top(){
while(!q.empty()&&p.top()==q.top()) p.pop(),q.pop();
return p.top();
}
inline void pop(){
while(!q.empty()&&p.top()==q.top()) p.pop(),q.pop();
p.pop();
}
inline int setop(){
int tmp=top(),res;pop();
res=top();insert(tmp);
return res;
}
inline int size(){return p.size()-q.size();}
}d[N],ch[N],ans;
int n,h[N],etot;
int siz[N],maxx[N],rt,psum,fa[N],dep[N],dis[N][21];
bool vis[N],col[N];
inline void add_edge(int u,int v){e[++etot]=(Edge){v,h[u]};h[u]=etot;}
namespace Tree{
int fa[N],dep[N],siz[N],son[N],top[N];
void dfs1(int u,int f,int deep){
dep[u]=deep,siz[u]=1,fa[u]=f;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(v==f) continue;
dfs1(v,u,deep+1);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int topf){
top[u]=topf;
if(!son[u]) return;
dfs2(son[u],topf);
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
}
}
inline void init(){dfs1(1,0,0);dfs2(1,1);}
inline int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]=2) ans.insert(ch[u].top()+ch[u].setop());
else if(ch[u].size()) ans.insert(ch[u].top());
}
int main(){
// freopen("9.in","r",stdin);
// freopen("P2056.out","w",stdout);
read(n);
for(int i=1;i=2) ans.erase(ch[u].top()+ch[u].setop());
ch[u].erase(0);
if(ch[u].size()>=2) ans.insert(ch[u].top()+ch[u].setop());
for(int p=u;fa[p];p=fa[p]){
if(ch[fa[p]].size()>=2) ans.erase(ch[fa[p]].top()+ch[fa[p]].setop());
ch[fa[p]].erase(d[p].top());
d[p].erase(dis[u][dep[u]-dep[fa[p]]]);
if(d[p].size()) ch[fa[p]].insert(d[p].top());
if(ch[fa[p]].size()>=2) ans.insert(ch[fa[p]].top()+ch[fa[p]].setop());
}
}
else{
if(ch[u].size()>=2) ans.erase(ch[u].top()+ch[u].setop());
ch[u].insert(0);
if(ch[u].size()>=2) ans.insert(ch[u].top()+ch[u].setop());
for(int p=u;fa[p];p=fa[p]){
if(ch[fa[p]].size()>=2) ans.erase(ch[fa[p]].top()+ch[fa[p]].setop());
if(d[p].size()) ch[fa[p]].erase(d[p].top());
d[p].insert(dis[u][dep[u]-dep[fa[p]]]);
ch[fa[p]].insert(d[p].top());
if(ch[fa[p]].size()>=2) ans.insert(ch[fa[p]].top()+ch[fa[p]].setop());
}
}
col[u]^=1;
}
else{
if(ans.size()) println(ans.top());
else println(-1);
}
// print('\n');print("debug: "),print(++cnt),print(':'),print('\n');
/*std::queue q;while(!q.empty()) q.pop();
while(ans.size()) q.push(ans.top()),ans.pop();
while(!q.empty()) print(q.front()),print(' '),ans.insert(q.front()),q.pop();*/
// for(int i=1;i<=n;++i) print(i),print(':'),println(ch[i].size());
// print('\n');
}
return 0;
}
回滚莫队
如果莫队只能支持加入/删除其中的一种，那么可以使用回滚莫队。
以只能加入为例，我们把序列每 \(B\) 个分成一块，然后把询问按照左端点所在块升序为第一关键字、右端点升序为第二关键字排序。
依次考虑每个区间，如果当前区间左端点和上一个左端点不在同一个块了，就把此时的 \(l\) 放到当前块右端点 \(+1\)，\(r\) 放到当前块右端点并清空答案。这个操作会进行 \(O(\frac{n}{B})\) 次。
如果这个区间的右端点和左端点在同一个块内我们可以直接 \(O(B)\) 暴力计算答案；否则，因为左端点在同一个块的时候右端点是递增的，所以这部分不需要删除并且 \(r\) 总共会移动 \(O(n)\) 次。对于 \(l\) 来说，我们每次都从这个块右端点开始向左扫到区间左端点，这个也不需要删除并且每个询问左端点最多只需要移动 \(O(B)\) 次。
所以总复杂度为 \(O(mB+\frac{n^2}{B})\)，取 \(B=\frac{n}{\sqrt m}\) 可得最优复杂度 \(O(n\sqrt m)\)。
例题 [JOISC2014] 历史研究
模板 回滚莫队