jzyzoj的p2016
先码着,强制在线的树分块或者树套树?关键是我树分块还在入门阶段树套树完全不会啊摔
http://blog.csdn.net/jiangyuze831/article/details/41445003
果然我除了抄代码什么也不会......树分块之类的东西完全不会计算复杂度.....
似乎upper_bound非常浪费时间..所以更改的时候直接循环查找不然会超时......
static这种东西不要胡乱用......如果在后面直接赋值会赋值不上........
看代码就能想起来具体内容所以不需要那么详细解释了......
树分块↓
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdlib>
using namespace std;
const int maxn=;
int n,m;
int lastans=;
int f[*maxn]={};
int ad=;
struct nod{
int y;
int next;
}e[maxn*];
struct node{
int num;
int a[];
inline int ask(int k){
int fff=upper_bound(a+,a+num+,k)-a-;
return num-fff;
}
}blo[];
struct no{
int next[maxn];
int ai[maxn];
int head[maxn];
int shu;
inline void add(int x,int y){
next[++shu]=head[x];
ai[shu]=y;
head[x]=shu;
}
}gre;
int bel[maxn]={};
int tail=;
int sz;
int a[maxn]={},head[maxn]={};
int tot=;
inline void init(int x,int y){
e[++tail].next=head[x];
e[tail].y=y;
head[x]=tail;
}
void dfs(int x,int fa){
int now=bel[x];
blo[now].a[++blo[now].num]=a[x];
f[x]=fa;
for(int i=head[x];i;i=e[i].next){
if(e[i].y==fa){
continue;
}
if(blo[now].num<sz){
bel[e[i].y]=now;
}
else{
bel[e[i].y]=++tot;
}
if(bel[e[i].y]!=now){
gre.add(now,bel[e[i].y]);
}
dfs(e[i].y,x);
}
}
int coun(int x,int k){
int ans=blo[x].ask(k);
for(int i=gre.head[x];i;i=gre.next[i]){
ans+=coun(gre.ai[i],k);
}
return ans;
}
int cnt(int x,int fa,int k){
int ans=a[x]>k;
for(int i=head[x];i;i=e[i].next){
if(e[i].y==fa) continue;
if(bel[e[i].y]==bel[x]){
ans+=cnt(e[i].y,x,k);
}
else{
ans+=coun(bel[e[i].y],k);
}
}
return ans;
}
int main(){
//freopen("wtf.in","r",stdin);
//freopen("wtf.out","w",stdout);
memset(e,,sizeof(e));
memset(blo,,sizeof(blo));
scanf("%d",&n);
ad=n;
int u,v;
sz=(int)sqrt((double)n);
for(int i=;i<n;i++){
scanf("%d%d",&u,&v);
init(u,v);
init(v,u);
}
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
scanf("%d",&m);
bel[]=++tot;
dfs(,);
for(int i=;i<=tot;++i){
sort(blo[i].a+,blo[i].a+blo[i].num+);
}
for(int op,u,x,i=;i<=m;++i){ scanf("%d%d%d",&op,&u,&x);
u^=lastans,x^=lastans;
if(op==){
printf("%d\n",lastans=cnt(u,f[u],x));
}
else if(op==){
int fr=bel[u];
for(int i=;i<=blo[fr].num;i++){
if(blo[fr].a[i]==a[u]){
blo[fr].a[i]=a[u]=x;
}
}
sort(blo[fr].a+,blo[fr].a++blo[fr].num);
}
else{
int fr=bel[u];
a[++ad]=x;
init(u,ad);
f[ad]=u;
if(blo[fr].num<sz){
bel[ad]=fr;
blo[fr].a[++blo[fr].num]=x;
sort(blo[fr].a+,blo[fr].a++blo[fr].num);
}
else{
bel[ad]=++tot;
blo[bel[ad]].a[++blo[bel[ad]].num]=x;
gre.add(fr,bel[ad]);
}
}
}
return ;
}