傳送門

題意： 一棵樹，詢問子樹中權(quán)值大于$k$的節(jié)點(diǎn)個數(shù)，修改點(diǎn)權(quán)值，插入新點(diǎn)；強(qiáng)制在線

---

?

一開始以為詢問多少種不同的權(quán)值，那道CF的強(qiáng)制在線帶修改版，直接嚇哭

然后發(fā)現(xiàn)看錯了這不一道樹上分塊水題...

用王室聯(lián)邦分塊的話需要維護(hù)每一個塊$dfs$序最小值和最大值，并且插入操作會破壞原來的性質(zhì)

不如直接按$size$分塊，根節(jié)點(diǎn)$size<block$就加入根，否則新建塊

$size$分塊不能保證塊的數(shù)量，可以被菊花圖卡掉，然而本題沒有所以就可以安心的寫了

每個塊維護(hù)排序后的值

查詢操作，不完整的塊(因?yàn)槭?size$分塊所以只有子樹根所在塊不完整)暴力，直接把塊建一個圖，每個整塊二分

修改維護(hù)有序，插入也維護(hù)有序；當(dāng)然修改和插入后重新排序也可以

?

復(fù)雜度 修改插入$O(S)$ 查詢$O(S+\frac{N}{S}logS)$

?

?

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; typedef long long ll; const int N=6e4+5, M=1e4+5, S=700; inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; }int n,Q,a[N],op,u,x; struct edge{int v,ne;} e[N<<1]; int cnt,h[N]; inline void ins(int u,int v) {e[++cnt]=(edge){v,h[u]}; h[u]=cnt;e[++cnt]=(edge){u,h[v]}; h[v]=cnt; }struct meow{int a[S], size;inline void set() {sort(a+1, a+1+size);}inline int count(int v) {return size - (upper_bound(a+1, a+1+size, v) - a) + 1;}inline void push(int v) {a[++size]=v;}inline void replace(int x,int v) { if(x==v) return;for(int i=1;i<=size;i++) if(a[i]==x) {if(v>x) while(i<size && v>a[i+1]) a[i]=a[i+1], i++;else while(i>1 && v<a[i-1]) a[i]=a[i-1], i--;a[i]=v; break;}}inline void insert(int v){int i; for(i=1; i<=size && a[i]<v; i++) ;for(int j=size; j>=i; j--) a[j+1]=a[j];a[i]=v; size++;} }b[M]; int m, pos[N], block;struct Graph4Block{struct edge{int v,ne;} e[M];int cnt,h[M];inline void ins(int u,int v) {e[++cnt]=(edge){v,h[u]}; h[u]=cnt;}int dfs(int u,int k) {int ans= b[u].count(k);for(int i=h[u];i;i=e[i].ne) ans+=dfs(e[i].v, k);return ans;} }G;int fa[N]; void dfs(int u) {int p=pos[u]; b[p].push(a[u]);for(int i=h[u];i;i=e[i].ne) if(e[i].v!=fa[u]) {fa[e[i].v]=u;if(b[p].size < block) pos[e[i].v]=p;else pos[e[i].v]=++m, G.ins(p, m);dfs(e[i].v);} }struct Block{int dfs(int u,int k) {int ans= a[u]>k;for(int i=h[u];i;i=e[i].ne) if(e[i].v!=fa[u]) {if(pos[e[i].v] == pos[u]) ans+= dfs(e[i].v, k);else ans+= G.dfs(pos[e[i].v], k);}return ans;}int Que(int u, int k) {return dfs(u, k);}void Cha(int u, int d) {b[pos[u]].replace(a[u], d); a[u]=d;}void Ins(int u, int d){a[++n]=d; ins(u, n); fa[n]=u; int p=pos[u];if(b[p].size < block) pos[n]=p, b[p].insert(a[n]);else pos[n]=++m, b[m].push(a[n]), G.ins(p, m);} }B; int main() {freopen("in", "r", stdin);n=read();for(int i=1;i<n;i++) ins(read(), read() );for(int i=1;i<=n;i++) a[i]=read();block=pow(n, 0.6);pos[1]=++m; dfs(1); for(int i=1;i<=m;i++) b[i].set();Q=read(); int lastans=0;for(int i=1;i<=Q;i++) {op=read(); u=read()^lastans; x=read()^lastans; if(op==0) lastans=B.Que(u, x), printf("%d\n",lastans);else if(op==1) B.Cha(u, x);else B.Ins(u, x);} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/candy99/p/6576084.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 3720: Gty的妹子树 [树上size分块]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。