noip 模拟 34 Equation

T2 稀有算法 : 树剖
虽说过不了,但能打出来就好
考场时就86,到现在还是86,实在卡不动了...
代码能力++
noip 模拟 34 Equation
这里不做树剖讲解,仅作留念。(下文讲正解)
有兴趣的 \(oler\) 可以自行尝试

#include <bits/stdc++.h>
#define re register
#define ll long long
using namespace std; 
const int maxn=1000010;
char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline int read() {
    int s=0,w=1; char ch=getchar();
    while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) w=-1;ch=getchar(); }
    while(ch>=‘0‘&&ch<=‘9‘) { s=s*10+ch-‘0‘; ch=getchar(); }
    return s*w;
}

int n,q,w[maxn],fa[maxn];
struct EDGE { int var,nxt; } edge[maxn];
int head[maxn],cnt;
inline void add(int a,int b) { edge[++cnt]=(EDGE){ b,head[a] }; head[a]=cnt; }
int dep[maxn],size[maxn],son[maxn];
inline void dfs1(int now) {
	dep[now]=dep[fa[now]]+1;
	size[now]=1;
	for(re int i=head[now],to;~i;i=edge[i].nxt) {
		to=edge[i].var;
		dfs1(to);
		size[now]+=size[to];
		if(size[son[now]]<size[to]) son[now]=to;
	}
}
int tot,top[maxn],id[maxn],eid[maxn];
inline void dfs2(int now,int pre) {
	top[now]=pre; id[now]=++tot; eid[tot]=now;
	if(!son[now]) return;
	dfs2(son[now],pre);
	for(re int i=head[now],to;~i;i=edge[i].nxt) {
		if((to=edge[i].var)==son[now]) continue;
		dfs2(to,to);
	}
}
struct WORK {
	ll tre[maxn];
	#define lewbit(x) (-x&x)
	inline void insert(int pos,int val) {
		while(pos<=n) { tre[pos]+=val; pos+=lewbit(pos); }
	}
	inline ll que(int pos) {
		ll ans=0;
		while(pos) { ans+=tre[pos]; pos-=lewbit(pos); }
		return ans;
	}
	inline ll query(int l,int r) { return que(r)-que(l-1); }
} tre[2];
ll as1,as2;int s;
inline int get_ans(int a,int b) {
	int sl1,sl2,date=1; as1=0,as2=0;
	sl1=(dep[a]&1)?1:0; sl2=(dep[b]&1)?1:0;
	while(top[a]!=top[b]) {
		if(dep[top[a]]<dep[top[b]]) { s=a;a=b;b=s; date^=1; }
		if(date) as1+=tre[sl1].query(id[top[a]],id[a]); else as2+=tre[sl2].query(id[top[a]],id[a]);
		a=fa[top[a]];
	}  
	if(a==b) return a;
	if(id[a]<id[b]) { date^=1; } else { s=a;a=b;b=s; }
	if(date) as1+=tre[sl1].query(id[a]+1,id[b]); else as2+=tre[sl2].query(id[a]+1,id[b]);
	return a;
}
inline void pushup(int a) {
	int sl1; as1=0;
	sl1=(dep[a]&1)?1:0;
	while(top[a]!=1) {
		as1+=tre[sl1].query(id[top[a]],id[a]);
		a=fa[top[a]];
	}  
	if(a==1) return;
	as1+=tre[sl1].query(2,id[a]);
}
signed main(void) {
	//freopen("5_1.in","r",stdin);
	//freopen("ww.out","w",stdout);
	memset(head,-1,sizeof(head));
	n=read(),q=read();
	for(re int i=2;i<=n;++i) {
		fa[i]=read(),w[i]=read();
		add(fa[i],i);
	}
	dfs1(1),dfs2(1,1);
	for(re int i=1;i<=tot;++i) 
		if(dep[eid[i]]&1)
		tre[1].insert(i,w[eid[i]]),tre[0].insert(i,-w[eid[i]]);
		else tre[1].insert(i,-w[eid[i]]),tre[0].insert(i,w[eid[i]]);
	ll as;
	for(re int i=1,c,x,y,z,lca,sl1,sl2;i<=q;++i) {
		c=read();
		if(c&1) {
			x=read(),y=read(),z=read();
			if(x==y) {
				if(z&1) { puts("none"); continue; }
				z>>=1; 
				pushup(x);
				if((dep[x]-dep[1])&1) sl1=1; else sl1=2;
				if(sl1&1) printf("%lld\n",as1-z); 
				else printf("%lld\n",-(as1-z)); 
				continue;
			}
			lca=get_ans(x,y);
			if((dep[x]-dep[lca])&1) sl1=1; else sl1=2;
			if((dep[y]-dep[lca])&1) sl2=1; else sl2=2; 
			if(sl1!=sl2) {
				as=as1+as2;
				if(as==z) puts("inf"); else puts("none");
			}
			else {
				as=(as1-as2+z); 
				if(as&1) { puts("none"); continue; }
				as>>=1; 
				if(sl1&1) as=as1-as; else as=-(as1-as);
				pushup(lca);
				if((dep[lca]-dep[1])&1) sl1=1; else sl1=2;
				if(sl1&1) printf("%lld\n",as1-as); 
				else printf("%lld\n",-(as1-as)); 
			} 
		}
		else {
			x=read(),y=read(); z=y;
			y-=w[x];
			if(dep[x]&1)
			tre[1].insert(id[x],y),tre[0].insert(id[x],-y);
			else tre[1].insert(id[x],-y),tre[0].insert(id[x],y);
			w[x]=z;
		}
	}
}

应该想出来的,题目让求 \(x_{1}\) ,显然我们可以把每个点的 \(w\) 值改为 \(x_{now}\)\(x_{1}\) 的关系式(\(x_{i}\pm x_{1}=w_{i}\)),注意判断加减。这样就可以很容易求出所需答案。
(以下「权值」为我们新定义的权值)
关键在于修改,我们发现,当一个点的权值改变时,其子树和该节点的奇偶性相同的节点的权值改变量和该节点相同,反之相反,自己推一下就好了。
于是,我们可以维护两个树状数组分别记录奇性和偶性的点值差分表,更改时判断一下子树根节点的奇偶性,对应更新子节点。
code

#include <bits/stdc++.h>
#define re register
#define ll long long
using namespace std; 
const int maxn=1000010;
char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline int read() {
    int s=0,w=1; char ch=getchar();
    while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) w=-1;ch=getchar(); }
    while(ch>=‘0‘&&ch<=‘9‘) { s=s*10+ch-‘0‘; ch=getchar(); }
    return s*w;
}
struct EDGE { int var,nxt; } edge[maxn];
int n,q,cnt,head[maxn];
inline void add(int a,int b) { edge[++cnt]=(EDGE){ b,head[a] }; head[a]=cnt; }
struct Tree_array {
	ll tre[maxn]; 
	inline int lewbit(int x) { return x&(-x); }
	#define lewbit(x) x&(-x)
	inline void insert(int pos,int val) { while(pos<=n) { tre[pos]+=val; pos+=lewbit(pos); } }
	inline int query(int pos) { ll ans=0; while(pos) { ans+=tre[pos]; pos-=lewbit(pos); } return ans; }
} tre[2];
int w[maxn],val[maxn],tot,dep[maxn],dfn[maxn],size[maxn],id[maxn],fa[maxn];
inline void dfs(int now) {
	w[now]-=w[fa[now]];
	dep[now]=dep[fa[now]]+1;
	id[now]=++tot;
	size[now]=1;
	if(dep[now]&1) tre[1].insert(id[now],w[now]),tre[1].insert(id[now]+1,-w[now]);
	else tre[0].insert(id[now],w[now]),tre[0].insert(id[now]+1,-w[now]);
	for(re int i=head[now],to;~i;i=edge[i].nxt) { dfs(edge[i].var); size[now]+=size[edge[i].var]; }
}
signed main(void) {
	memset(head,-1,sizeof(head));
	n=read(),q=read();
	for(re int i=2;i<=n;i++) { fa[i]=read(),val[i]=w[i]=read(); add(fa[i],i); } 
	dep[1]=id[1]=size[1]=tot=1; 
	for(re int i=head[1];~i;i=edge[i].nxt) { dfs(edge[i].var); size[1]+=size[edge[i].var]; }
	ll as,as1,as2;
	for(re int i=1,c,x,y,z,ls1,ls2;i<=q;i++) {
		c=read();
		if(c==1) {
			x=read(),y=read(),z=read();
			ls1=(dep[x]&1)? 1:0; ls2=(dep[y]&1)? 1:0;
			as1=tre[ls1].query(id[x]); as2=tre[ls2].query(id[y]);
			if(ls1!=ls2) {
				ll as=as1+as2;
				if(as!=z) { puts("none"); } else { puts("inf"); }
			}
			else {
				ll as=as1-as2+z;
				if(as&1) { puts("none"); continue; }
				as>>=1;
				as=ls1? (as-as1):(as1-as);
				printf("%lld\n",as);
			}
		}
		else {
			x=read(),y=z=read(); y-=val[x];
			ls1=(dep[x]&1)? 1:0;
			tre[ls1].insert(id[x],y),tre[ls1].insert(id[x]+size[x],-y);
			tre[ls1^1].insert(id[x],-y),tre[ls1^1].insert(id[x]+size[x],y);
			val[x]=z;
		}
	}
}

noip 模拟 34 Equation

上一篇:计算机网络part2——物理层


下一篇:swoole源码方式安装