【数据结构】莫队
NanoApe
posted @ 2016年4月14日 20:20
in 蒟蒻不撕烤智熵何来
, 931 阅读
树上莫队
块状树的我不会写,这里是括号序列法
类似dfs序,这玩意就是给每个点做个进入和退出的时间戳
dfs序是进入的时间戳,离开并不会使得时间戳增加,但是我们这里给它也记录下时间戳并使其增加,那么我们可以得到长度为 $2n$ 的序列
把树转成一维的括号序列后就可以搞啦
询问点 $x$ 到点 $y$ 的路径?搞出 $[R(x),L(y)]$ 就可以辣(当x为lca时是 $[L(x),L(y)]$)(当然询问区间左右的大小关系是无所谓的)
带修改莫队
把修改的时间戳也记上,排序的时候左右端点块排序,修改时间戳从小到大,暴力还原就行辣
复杂度$O(n^{\frac 53})$
例题:糖果公园
int n, m, Q, v[maxn], w[maxn], c[maxn], last[maxn], cnt[maxn]; ll A[maxn], sum; bool vis[maxn]; int cn, L[maxn], R[maxn], h[17][maxn], dep[maxn], pos[maxc], Bk, B[maxc]; struct node{int l,r,t,id;} q[maxn]; int Q1; bool cmp(const node &a, const node &b){return B[a.l]<B[b.l] || (B[a.l]==B[b.l] && B[a.r]<B[b.r]) || (B[a.l]==B[b.l] && B[a.r]==B[b.r] && a.t<b.t);} struct node2{int x,pre,now;} p[maxn]; int Q2; void dfs(int x) { pos[L[x]=++cn]=x; rep(o, 1, 16) if (dep[x]>=(1<<o)) h[o][x]=h[o-1][h[o-1][x]]; else break; travel(x) if (p->y!=h[0][x]) h[0][p->y]=x, dep[p->y]=dep[x]+1, dfs(p->y); pos[R[x]=++cn]=x; } inline int lca(int x, int y) { if (dep[x]<dep[y]) swap(x,y); if (dep[x]!=dep[y]) { int tmp=dep[x]-dep[y]; rep(o, 0, 16) if (tmp&(1<<o)) x=h[o][x], tmp-=(1<<o); else if (!tmp) break; } dow(o, 16, 0) if (h[o][x]!=h[o][y]) x=h[o][x], y=h[o][y]; return x==y?x:h[0][x]; } inline void Vis(int x) { if (vis[x]) sum-=1LL*v[c[x]]*w[cnt[c[x]]--]; else sum+=1LL*v[c[x]]*w[++cnt[c[x]]]; vis[x]^=1; } inline void change(int x, int col) { if (vis[x]) Vis(x),c[x]=col,Vis(x); else c[x]=col; } int main() { //================================= rep(i, 1, n) c[i]=last[i]=read(); dfs(1); Bk=1750; rep(i, 1, cn) B[i]=(i-1)/Bk+1; rep(i, 1, Q) { int op=read(), x=read(), y=read(); if (op==1) { if (L[x]>L[y]) swap(x,y); int z=lca(x,y); ++Q1, q[Q1]=(node){x==z?L[x]:R[x], L[y], Q2, Q1}; } else p[++Q2]=(node2){x, last[x], y}, last[x]=y; } sort(q+1, q+1+Q1, cmp); int l=1, r=0, now=0; rep(i, 1, Q1) { while (now<q[i].t) now++, change(p[now].x, p[now].now); while (q[i].t<now) change(p[now].x, p[now].pre), now--; while (l<q[i].l) Vis(pos[l++]); while (q[i].r<r) Vis(pos[r--]); while (q[i].l<l) Vis(pos[--l]); while (r<q[i].r) Vis(pos[++r]); int x=pos[l], y=pos[r], z=lca(x,y); if (x!=z && x!=y) Vis(z); A[q[i].id]=sum; if (x!=z && x!=y) Vis(z); } //================================= return 0; }