神奇的分块。
假如没有 \(2\) 操作,我们可以直接用主席树解决。
我们考虑将询问分块,每遍历完一块就将这一块内出现的所有修改更新。如果在块内,就把当前块之前的所有修改暴力算,当然只有修改的节点在询问的节点的子树内才会发生。
具体的来说,我们可以用分块维护 dfs 序,并将块内的元素排序,询问 \(O(\sqrt n)\)。
对于新加进来的点,暴力跳找到其祖先,这样就能判断包含关系了。
总复杂度 \(O(n\sqrt{n}\cdot \log\sqrt{n})\)。
code:
#include<bits/stdc++.h>
using namespace std;
const int N=6e4+5,N2=600+5;
int n,m,fa[N],tp[N],l[N],r[N],tot=0,w[N],loc[N],a[N];
vector<int>adj[N];
struct kuai{int l,r,siz,val[N2];}b[N2];
struct node{
int op,u,x,y;
node(int op=0,int u=0,int x=0,int y=0):op(op),u(u),x(x),y(y){}
};
vector<node>vec;
void dfs(int u,int lst){
l[u]=++tot;fa[u]=lst;
for(int i=0;i<adj[u].size();++i)if(adj[u][i]!=lst)dfs(adj[u][i],u);
r[u]=tot;
}
void build(){
int cnt=1,j=0,len=sqrt(n);
for(int i=1;i<=n;++i)a[l[i]]=w[i];
b[1].l=1;
for(int i=1;i<=n;++i){
++j;loc[i]=cnt;
b[cnt].r=i;
b[cnt].val[j]=a[i];
if(j==len)b[cnt].siz=b[cnt].r-b[cnt].l+1,j=0,++cnt,b[cnt].l=i+1;
}
for(int i=1;i<=cnt;++i)sort(b[i].val+1,b[i].val+b[i].siz+1);
}
int query(int L,int R,int k){
int res=0,x=loc[L],y=loc[R];
if(x==y){for(int i=L;i<=R;++i)if(a[i]>k)++res;}
else{
for(int i=L;i<=b[x].r;++i)if(a[i]>k)++res;
for(int i=b[y].l;i<=R;++i)if(a[i]>k)++res;
if(x+1<y){
for(int i=x+1;i<y;++i){
int p=upper_bound(b[i].val+1,b[i].val+b[i].siz+1,k)-b[i].val;
res+=b[i].siz-p+1;
}
}
}
return res;
}
int get(int u){
if(fa[u]<=n)return fa[u];
return tp[u]=get(fa[u]);
}
bool check(int u,int v){
if(u>n&&v<=n)return false;
if(u<=n&&v<=n)return l[u]<=l[v]&&r[u]>=l[v];
if(u<=n&&v>n){
if(!tp[v])tp[v]=get(v);
return l[u]<=l[tp[v]]&&r[u]>=l[tp[v]];
}else{
while(fa[v]>n){
if(v==u)return true;
v=fa[v];
}
return v==u;
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<n;++i){
int u,v;cin>>u>>v;
adj[u].push_back(v);adj[v].push_back(u);
}
for(int i=1;i<=n;++i)cin>>w[i];
dfs(1,0);build();
cin>>m;
int B=sqrt(m),nn=n,j=0,lst=0;
while(m--){
int op,u,x;cin>>op>>u>>x;
u^=lst;x^=lst;
if(j==B){
n=nn;memset(tp,0,sizeof(tp));
for(int i=0;i<vec.size();++i){
node t=vec[i];
if(t.op==2)adj[t.y].push_back(t.u);
}
tot=0;
dfs(1,0);build();j=0;vec.clear();
}
++j;
if(op==0){
lst=query(l[u],r[u],x);
for(int i=0;i<vec.size();++i){
node t=vec[i];
if(check(u,t.u)){
if(t.op==1){
if(t.x<=x&&t.y>x)++lst;
if(t.x>x&&t.y<=x)--lst;
}else lst+=t.x>x;
}
}
cout<<lst<<endl;
}else if(op==1){
vec.push_back(node(1,u,w[u],x));
w[u]=x;
}else{
vec.push_back(node(2,++nn,x,u));
w[nn]=x;fa[nn]=u;
}
}
return 0;
}
标签:int,题解,cin,tp,P2137,++,lst,Gty,op
From: https://www.cnblogs.com/HQJ2007/p/17561557.html