社区讨论

不用dfs序神秘思路RE+MLE0分求条

wwoshilaoliu7
P3384【模板】重链剖分 / 树链剖分参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mlvl52qn
此快照首次捕获于
2026/02/21 08:33
3 周前
此快照最后确认于
2026/02/23 19:20
2 周前
查看原帖
样例对的但是70MB
MLE+RE
主要思路是一个点的子树里面链编号连续
开线段树记每个链被总体加的值
对每个链建的线段树
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define i128 __int128_t
struct zuoti{
	int l;
	int r;
	int ls,rs;
	i128 len;
	i128 sum;
	i128 tag;
	zuoti(){
		l=0;r=0;sum=0;tag=0;
		ls=0;rs=0;len=0;
	}
}xds1[400005],xds2[400005];
int n,q,rt,M;
int fa[100005];
int a[100005];
bool vis[100005];
int dep[100005],MXdep[100005],MXL[100005];
int idx=1;
vector<int>tmp[100005],e[100005];
vector<int>L[100005];
int inL[100005],xb[100005];
bool cmp(int aa,int bb){
	return MXdep[aa]>MXdep[bb];
}
void dfs(int x){
//	cout << "HYW";
	vis[x]=1;
	for(int i=0;i<tmp[x].size();i++){
		if(vis[tmp[x][i]]==0)e[x].push_back(tmp[x][i]);
	}
	if(e[x].size()==0){
		MXdep[x]=dep[x];
		return;
	}
	for(int i=0;i<e[x].size();i++){
		fa[e[x][i]]=x;
		dep[e[x][i]]=dep[x]+1;
		dfs(e[x][i]);
		MXdep[x]=max(MXdep[x],MXdep[e[x][i]]);
	}
	sort(e[x].begin(),e[x].end(),cmp);
}
void dfs1(int x){
//	cout << "DEB";
	L[idx].push_back(x);
	inL[x]=idx;xb[x]=L[idx].size()-1;
	if(e[x].size()==0){
		MXL[x]=idx;
		return;
	}
	for(int i=0;i<e[x].size();i++){
		dfs1(e[x][i]);
		MXL[x]=max(MXL[x],MXL[e[x][i]]);
		idx++;
	}
}
vector<zuoti>xds[100005];
// 1 -> idx-1 lian 0 ZD 1e5+1 TAG
void pushup(int id,int x){
	xds[id][x].sum=xds[id][xds[id][x].ls].sum+xds[id][xds[id][x].rs].sum;
}
void mktree(int id,int x,int l,int r){
//	cout << "HYW" << id << " " << x << " " << l << " " << r << "\n";
	zuoti tmpp;
	tmpp.len=0;tmpp.ls=0;tmpp.rs=0;tmpp.l=l;tmpp.r=r;tmpp.sum=0;tmpp.tag=0;
	xds[id].push_back(tmpp);//x==xb
	if(l==r){
		xds[id][x].sum=a[L[id][l]];
		return;
	}
	int mid=l+r>>1;
	xds[id][x].ls=xds[id].size();
	mktree(id,xds[id].size(),l,mid);
	xds[id][x].rs=xds[id].size();
	mktree(id,xds[id].size(),mid+1,r);
	pushup(id,x);
}
void mktree1(int x,int l,int r){
	xds1[x].l=l;
	xds1[x].r=r;
	if(l==r){
		xds1[x].sum=xds[l][1].sum;
		xds1[x].len=L[l].size()-1;
		return;
	}
	int mid=l+r>>1;
	mktree1(x<<1,l,mid);
	mktree1(x<<1|1,mid+1,r);
	xds1[x].sum=xds1[x<<1].sum+xds1[x<<1|1].sum;
	xds1[x].len=xds1[x<<1].len+xds1[x<<1|1].len;
}
void mktree2(int x,int l,int r){
	xds2[x].l=l;
	xds2[x].r=r;
	if(l==r){
		xds2[x].len=L[l].size()-1;
		return;
	}
	int mid=l+r>>1;
	mktree2(x<<1,l,mid);
	mktree2(x<<1|1,mid+1,r);
	xds2[x].len=xds2[x<<1].len+xds2[x<<1|1].len;
}


















void pushdown(int id,int x){
	if(xds[id][x].tag==0)return;
	int tg=xds[id][x].tag;
	int ls=xds[id][x].ls,rs=xds[id][x].rs;
	
	xds[id][ls].tag+=tg;
	xds[id][ls].sum+=tg*(xds[id][ls].r-xds[id][ls].l+1);
	
	xds[id][rs].tag+=tg;
	xds[id][rs].sum+=tg*(xds[id][rs].r-xds[id][rs].l+1);
	xds[id][x].tag=0;
}




void modify(int id,int x,int askl,int askr,int k){
	int l=xds[id][x].l,r=xds[id][x].r;
	if(askl<=l&&r<=askr){
		xds[id][x].tag+=k;
		xds[id][x].sum+=k*(r-l+1);
		return;
	}
	pushdown(id,x);
	int mid=l+r>>1;
	if(mid>=askl)modify(id,xds[id][x].ls,askl,askr,k);
	if(mid<askr)modify(id,xds[id][x].rs,askl,askr,k);
	pushup(id,x);
}
int query(int id,int x,int askl,int askr){
	int l=xds[id][x].l,r=xds[id][x].r;
	if(askl<=l&&r<=askr){
		return xds[id][x].sum;
	}
	pushdown(id,x);
	int sum=0;
	int mid=l+r>>1;
	if(mid>=askl)sum+=query(id,xds[id][x].ls,askl,askr);
	if(mid<askr)sum+=query(id,xds[id][x].rs,askl,askr);
	return sum%M;
}
//void pushdown1(int x){
//	if(xds1[x].tag==0)return;
//	int tg=xds1[x].tag;
//	xds1[x<<1].tag+=tg;xds1[x<<1|1].tag+=tg;
//	xds1[x<<1].sum+=tg*xds1[x<<1].len;
//	xds1[x<<1|1].sum+=tg*xds1[x<<1|1].len;
//	xds1[x].tag=0;
//}
void modify1(int x,int askl,int askr,int k){
	int l=xds1[x].l,r=xds1[x].r;
	if(askl<=l&&r<=askr){
		xds1[x].sum+=k;
		return;
	}
//	pushdown1(x);
	int mid=l+r>>1;
	if(mid>=askl)modify1(x<<1,askl,askr,k);
	if(mid<askr)modify1(x<<1|1,askl,askr,k);
	xds1[x].sum=xds1[x<<1].sum+xds1[x<<1|1].sum;
}


void pushdown2(int x){
	if(xds2[x].tag==0)return;
	int tg=xds2[x].tag;
	xds2[x<<1].tag+=tg;xds2[x<<1|1].tag+=tg;
	xds2[x<<1].sum+=tg*xds2[x<<1].len;
	xds2[x<<1|1].sum+=tg*xds2[x<<1|1].len;
	xds2[x].tag=0;
}


i128 query2(int x,int askl,int askr){
//	cout << x << " " << askl << " " << askr << endl;
	i128 sum=0;
	if(askl>askr)return sum;
	int l=xds2[x].l,r=xds2[x].r;
	if(askl<=l&&r<=askr){
//		cout << "666";
		if(askl==askr)return xds2[x].sum/xds2[x].len;
		else return xds2[x].sum;
	}
	pushdown2(x);
	int mid=l+r>>1;
	if(mid>=askl)sum+=query2(x<<1,askl,askr);
	if(mid<askr)sum+=query2(x<<1|1,askl,askr);
	return sum%M; 
}








void modify2(int x,int askl,int askr,int k){
	if(askl>askr)return ;
	int l=xds2[x].l,r=xds2[x].r;
	if(askl<=l&&r<=askr){
		xds2[x].sum+=k*xds2[x].len;
		xds2[x].tag+=k;
		return ;
	}
	pushdown2(x);
	int mid=l+r>>1;
	if(mid>=askl)modify2(x<<1,askl,askr,k);
	if(mid<askr)modify2(x<<1|1,askl,askr,k);
	xds2[x].sum=xds2[x<<1].sum+xds2[x<<1|1].sum;
}









void solve(int x,int y,int k){
	while(inL[x]!=inL[y]){
		int tx=L[inL[x]][1],ty=L[inL[y]][1];
		if(dep[tx]<dep[ty]){int t=x;x=y;y=t;tx=L[inL[x]][1],ty=L[inL[y]][1];}
		modify(inL[x],1,1,xb[x],k);
		modify1(1,inL[x],inL[x],k*xb[x]);
		x=fa[tx];
	}
	if(xb[x]>xb[y]){int t=x;x=y;y=t;}
	modify(inL[x],1,xb[x],xb[y],k);
	modify1(1,inL[x],inL[x],k*(xb[y]-xb[x]+1));
}


i128 SUM(int x,int y){
	i128 sum=0;
	while(inL[x]!=inL[y]){
		int tx=L[inL[x]][1],ty=L[inL[y]][1];
		if(dep[tx]<dep[ty]){int t=x;x=y;y=t;tx=L[inL[x]][1],ty=L[inL[y]][1];}
//		modify(inL[x],1,1,xb[x],k);
//		modify1(1,inL[x],inL[x],k*xb[x]);
		sum+=query(inL[x],1,1,xb[x]);
		sum+=query2(1,inL[x],inL[x])*xb[x];
		x=fa[tx];
	}
	if(xb[x]>xb[y]){int t=x;x=y;y=t;}
	sum+=query(inL[x],1,xb[x],xb[y]);
	sum+=query2(1,inL[x],inL[x])*(xb[y]-xb[x]+1);
	return sum%M;
}




void solve2(int x,int k){
	int ln=L[inL[x]].size()-1;
	modify(inL[x],1,xb[x],ln,k);
	modify1(1,inL[x],inL[x],k*(ln-xb[x]+1));
	modify2(1,inL[x]+1,MXL[x],k);
}

i128 SUM2(int x){
//	cout << "HYW";
	int ln=L[inL[x]].size()-1;
	i128 sum=0;
	sum+=query(inL[x],1,xb[x],ln);
//	cout << "HYW";
	sum+=query2(1,inL[x],inL[x])*(ln-xb[x]+1);
//	cout << "HYW";
	sum+=query2(1,inL[x]+1,MXL[x]);
//	cout << "HYW";
//	cout << "HYW";
	return sum%M;
}

signed main(){
	cin >> n >> q >> rt >> M;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	for(int i=1;i<n;i++){
		int u,v;
		cin >> u >> v;
		tmp[u].push_back(v);
		tmp[v].push_back(u);
	}
	dfs(rt);
	for(int i=0;i<=n;i++){
		L[i].push_back(0);
		xds[i].push_back(zuoti());
	}
	dfs1(rt);
//	cout << idx << " ";
	for(int i=1;i<=idx;i++){
		if(L[i].size()==1){
			idx=i;break;
		}
	}
//	cout << idx << endl;
//	Sleep(11451);
	for(int i=1;i<idx;i++){
		mktree(i,1,1,L[i].size()-1);
	}
	mktree1(1,1,idx-1);//Lians sum 
	mktree2(1,1,idx-1);//Lians tag
	for(int i=1;i<=q;i++){
		int opt,x,y,z;
		cin >> opt;
		if(opt==1){
			cin >> x >> y >> z;
			solve(x,y,z);
		}
		else if(opt==2){
			cin >> x >> y;
			int tmpp=SUM(x,y);
			tmpp=(tmpp%M+M)%M;
			cout << tmpp << endl;
		}
		else if(opt==3){
			cin >> x >> z;
			solve2(x,z);
		}
		else {
			cin >> x;
			int tmpp=SUM2(x);
			tmpp=(tmpp%M+M)%M;
			cout << tmpp << endl;
		}
	}
	return 0;
}

回复

共 2 条回复，欢迎继续交流。

正在加载回复...