软件包管理器 T21 D71

软件包管理器 T21 D71

软件包管理器

思路

树剖+线段树

每次in操作询问此节点到根节点路径权值和，再把路径节点权值全部变为1

un操作询问当前节点子树权值和，再把子树权值变为0

#include
#define ll long long
#define pii pair
#define fi first
#define se second
#define pb push_back
#define si size()
#define ls (p<<1)
#define rs ((p<<1)|1)
#define mid (t[p].l+t[p].r)/2 
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}
const int qs=1e5+7;

const int mod=1e9;
ll n,m,q,a[qs]; 
int dep[qs],f[qs],fr[qs],sz[qs],son[qs],top[qs],cnt=0;
vector v[qs];
pii id[qs];
struct Tree{
	ll val,add;
	int l,r;
	#define l(x) t[x].l
	#define r(x) t[x].r
	#define val(x) t[x].val
	#define add(x) t[x].add
}t[qs<<2];

void pushup(int p){ val(p)=(val(ls)+val(rs))%mod;}
void down(int p){
	if(add(p)==-1) return;
	val(ls)=(add(p)*(r(ls)-l(ls)+1))%mod;
	val(rs)=(add(p)*(r(rs)-l(rs)+1))%mod;
	add(ls)=(add(p))%mod;
	add(rs)=(add(p))%mod;
	add(p)=-1;
}
void build(int p,int l,int r){
	l(p)=l,r(p)=r;add(p)=-1;
	if(l==r){
		val(p)=0;
		return;
	}
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(p);
//	cout<<"l="<=r(p)){
		val(p)=(val*(r(p)-l(p)+1))%mod;
		add(p)=(val)%mod;
		//cout<<"l="<mid) update(rs,l,r,val);
	pushup(p);
}

ll ask(int p,int l,int r){
	if(l<=l(p)&&r>=r(p)) return val(p);
	down(p);
	ll val=0;
	if(l<=mid) val=(val+ask(ls,l,r))%mod;
	if(r>mid) val=(val+ask(rs,l,r))%mod;
	return val; 
}

void dfs(int x,int fa){
	dep[x]=dep[fa]+1; f[x]=fa; sz[x]=1; son[x]=0;
	int ms=0;
	for(int i=0;ims) son[x]=p,ms=sz[p];
	}
}

void dfn(int x,int po){
	id[x].fi=++cnt;
	fr[cnt]=x;
	top[x]=po;
	if(!son[x]) {
		id[x].se=cnt;	return;
	}
	dfn(son[x],po);
	for(int i=0;idep[y]) swap(x,y);
	update(1,id[x].fi,id[y].fi,k);
}

ll qRange(int x,int y){
	ll ans=0,res;
	while(top[x]!=top[y]){
		if(dep[top[x]]dep[y]) swap(x,y);
	res=ask(1,id[x].fi,id[y].fi);
	ans=(ans+res)%mod;
	return ans;
}

int main(){
	
	scanf("%lld\n",&n);
	ll x;
	for(int i=1;i