玄学线段树思路求助

我觉得这道题树剖之后可以用一种玄学的方式维护
我的思路是:树剖后，在线段树上维护区间和，对一段区间进行修改时，
如果是 $install$ ，就把节点的值改成

(r-l+1)

，因为这个区间全部要安装；
如果是 $uninstall$ ，就把节点的值改为

0

，因为这个区间全都被卸载了
通过

push\_up

操作维护

tree[1]

的值为区间总和（即现在已经安装的软件包的数量）
每次用

lastans

记录上次操作时的软件包总和减去这次的总和得到答案

然而样例都过不去（可能是我调错了？）
求

dalao

看看我思路的可行性

以下是我的爆零代码

qwq

CPP

#include<bits/stdc++.h>
using namespace std;

int n,m,cnt,lastans;
char s[11];
int head[100003];
int tot[100003],son[100003],top[100003],fa[100003],idx[100003],dep[100003];
struct node
{
	int next,v;
}e[100003];

void add(int u,int v)
{
	e[++cnt].v=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}

struct Segment_tree
{
	int tree[500003];
	void modify(int nl,int nr,int l,int r,int p,int k)
	{
		if(nl<=l&&r<=nr)
		{
			tree[p]=(r-l+1)*k;
			return;
		}
		int mid=(l+r)>>1;
		if(nl<=mid) modify(nl,nr,l,mid,p<<1,k);
		if(nr>mid) modify(nl,nr,mid+1,r,p<<1|1,k);
		tree[p]=tree[p<<1]+tree[p<<1|1];
	}
}t;
//只有一个修改操作。。因为不需要建树
void dfs1(int u)
{
	tot[u]=1;
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(v==fa[u]) continue;
		fa[v]=u;
		dep[v]=dep[u]+1;
		dfs1(v);
		tot[u]+=tot[v];
		if(tot[v]>tot[son[u]]) son[u]=v;
	}
}

void dfs2(int u,int topf)
{
	idx[u]=++cnt;
	top[u]=topf;
	if(!son[u]) return;
	dfs2(son[u],topf);
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(!idx[v]) dfs2(v,v);
	}
}

void modify_install(int x)
{
	while(top[x]!=1)
	{
		t.modify(idx[top[x]],idx[x],1,n,1,1);
		x=fa[top[x]];
	}
	t.modify(1,idx[x],1,n,1,1);
}

void modify_uninstall(int x)
{
	t.modify(idx[x],idx[x]+tot[x]-1,1,n,1,0);
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin>>n;
	for(int i=2,x;i<=n;++i)
	{
		cin>>x;++x;
		add(i,x);add(x,i);
	}
	cnt=0;dfs1(1);dfs2(1,1);
	cin>>m;
	for(int i=1,x;i<=m;++i)
	{
		cin>>s>>x;++x;
		if(s[0]=='i') modify_install(x);
		else modify_uninstall(x);
		cout<<abs(lastans-t.tree[1])<<endl;
		lastans=t.tree[1];
	}
	return 0;
}

玄学线段树思路求助

讨论操作

回复

相关推荐

玄学线段树思路求助