首页 > 代码库 > BZOJ 3731 3731: Gty的超级妹子树 [树上size分块 ！]
BZOJ 3731 3731: Gty的超级妹子树 [树上size分块 ！]
传送门
题意：一棵树，询问子树中权值大于k的节点个数，修改点权值，插入新点，断开边；强制在线
该死该死该死！！！！！！
MD我想早睡觉你知不知道
该死该死沙比提
断开边只会影响一个块，重构这个块就行了
如果断开的点$u$是这个块$p$的根，只修改原图和块图就好了
否则，把$u$子树在块中的部分从$p$里删除，放到一个新块里。并且，这些点连到的其他块的点，也要在块图上与$p$断开与新块相连
所以我们维护一个删除边的$mark$标记
WA：一开始原图加的是双向边，通过判断$fa$防止出错..后来$fa$会变化，然后判断$fa$就失灵了应该会一直$dfs$停不下来
所以一开始$dfs$就给双向边不用的那一条打上$mark$标记就好了
ps：读入挂我直接复制了PoPoQQQ大爷的因为我有一次以为是读入导致WA
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#include <vector>using namespace std;typedef long long ll;const int N=2e5+5;inline int read1(){ 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;}namespace IOStream{ const int L=1<<15; char buffer[L]; char *S,*T; char Get_Char() { if(S==T) { T=(S=buffer)+fread(buffer,1,L,stdin); if(S==T) return EOF; } return *S++; } int Get_Int() { int re=0; char c; do c=Get_Char(); while(c<‘0‘||c>‘9‘); while(c>=‘0‘&&c<=‘9‘) re=(re<<1)+(re<<3)+(c-‘0‘),c=Get_Char(); return re; } }#define read IOStream::Get_Intint n,Q,a[N],op,u,x;struct meow{ vector<int> a; inline void set() {sort(a.begin(), a.end());} inline int count(int v) {return a.size() - (upper_bound(a.begin(), a.end(), v) - a.begin());} inline void push(int v) {a.push_back(v);} inline void insert(int v) {a.insert(lower_bound(a.begin(), a.end(), v), v);} inline void erase(int v) {a.erase(lower_bound(a.begin(), a.end(), v));} inline void replace(int x,int v) {if(x==v) return; erase(x); insert(v);} inline int size() {return a.size();}}b[N];int m, pos[N], block;struct Graph4Block{ struct edge{int v,ne;} e[N<<1]; int cnt, h[N], ine[N], mark[N<<1]; inline void ins(int u,int v) { e[++cnt]=(edge){v,h[u]}; h[u]=cnt; ine[v]=cnt; } inline void dele(int u) {mark[ine[u]]=1;} int dfs(int u,int k) { int ans= b[u].count(k); for(int i=h[u];i;i=e[i].ne) if(!mark[i]) ans+=dfs(e[i].v, k); return ans; }}G;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;}int fa[N], mark[N<<1], ine[N];inline void ins1(int u,int v) { e[++cnt]=(edge){v,h[u]}; h[u]=cnt; ine[v]=cnt; fa[v]=u;}inline void dele(int u) {fa[u]=0; mark[ine[u]]=1;}void dfs(int u) { int p=pos[u]; b[p].push(a[u]); for(int i=h[u];i;i=e[i].ne) if(!mark[i]) { if(e[i].v!=fa[u]) { fa[e[i].v]=u; ine[e[i].v]=i; if(b[p].size() < block) pos[e[i].v]=p; else pos[e[i].v]=++m, G.ins(p, m); dfs(e[i].v); } else mark[i]=1; }}struct Block{ int dfs(int u,int k) { int ans= a[u]>k; for(int i=h[u];i;i=e[i].ne) if(!mark[i]) 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; ins1(u, n); 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); } void dfsSpl(int u,int p) { b[p].erase(a[u]); pos[u]=m; b[m].push(a[u]); for(int i=h[u];i;i=e[i].ne) if(!mark[i]) if(e[i].v!=fa[u]) { if(pos[e[i].v] == p) dfsSpl(e[i].v, p); else G.dele(pos[e[i].v]), G.ins(m, pos[e[i].v]); } } void Split(int u){ int p=pos[u]; if(pos[fa[u]] != p) G.dele(p); else m++, dfsSpl(u, p), b[m].set(); dele(u); }}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; if(op==3) B.Split(u); else{ 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); } }}
BZOJ 3731 3731: Gty的超级妹子树 [树上size分块 ！]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。