luogu P3241 [HNOI2015]开店

本文主要是介绍luogu P3241 [HNOI2015]开店，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题面传送门
看到这种东西想到差分，即差分成\([1,r]\)减去\([1,l]\)的答案。
距离的式子其实是\(dist_u+dist_v-2*dist_{lca(u,v)}\)前面两项平凡所以要求\(dist_{lca(u,v)}\)
然后这个有经典套路就是每个点往根加和查就是这个式子，直接树剖就好了。
因为强制在线所以可持久化。时空复杂度\(O(nlog^2n)\)
code:

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define ll long long
#define db double
#define N 150000
#define mod 998244353
#define eps (1e-5)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
using namespace std;
int n,m,k,z,L,R,d[N+5],top[N+5],id[N+5],idea,fa[N+5],siz[N+5],son[N+5],A[N+5],W[N+5],Ws[N+5],l,r,mid,tots[N+5],root[N+5],now,Ans1[N+5];ll Ans2[N+5],dist[N+5],LA,x,y;vector<int> Id[N+5];
struct yyy{int to,w,z;};
struct ljb{int head,h[N+5];yyy f[N+5<<1];I void add(int x,int y,int z){f[++head]=(yyy){y,z,h[x]};h[x]=head;}}s;
struct Tree{
	int L[N*200],R[N*200],F[N*200],cnt;ll G[N+5<<2],Sum[N*200];
	I void build(int x,int y,int l=1,int r=n,int now=1){G[now]+=y;if(l==r)return;int m=l+r>>1;x<=m?build(x,y,l,m,now<<1):build(x,y,m+1,r,now<<1|1);}
	I void memcpy(int x,int y){L[y]=L[x];R[y]=R[x];F[y]=F[x];Sum[y]=Sum[x];}I void Up(int x){Sum[x]=Sum[L[x]]+Sum[R[x]];}
	I void pushF(int &x,int y,int now){memcpy(x,++cnt);x=cnt;F[x]+=y;Sum[x]+=y*G[now];}I void push(int x,int now){F[x]&&(pushF(L[x],F[x],now<<1),pushF(R[x],F[x],now<<1|1),F[x]=0);}
	I void insert(int x,int y,int &now,int l=1,int r=n,int Gnow=1){
		memcpy(now,++cnt);now=cnt;if(x<=l&&r<=y){F[now]++;Sum[now]+=G[Gnow];return;}push(now,Gnow);int m=l+r>>1;x<=m&&(insert(x,y,L[now],l,m,Gnow<<1),0);y>m&&(insert(x,y,R[now],m+1,r,Gnow<<1|1),0);Up(now);
	}
	I ll find(int x,int y,int now,int l=1,int r=n,int Gnow=1){
		if(x<=l&&r<=y) return Sum[now]; int m=l+r>>1;ll Ans=0;push(now,Gnow);x<=m&&(Ans+=find(x,y,L[now],l,m,Gnow<<1));y>m&&(Ans+=find(x,y,R[now],m+1,r,Gnow<<1|1));return Ans;
	}
}T;
I void dfs1(int x,int last){
	yyy tmp;fa[x]=last;siz[x]=1;d[x]=d[last]+1;for(int i=s.h[x];i;i=tmp.z) tmp=s.f[i],tmp.to^last&&(A[tmp.to]=tmp.w,dfs1(tmp.to,x),siz[x]+=siz[tmp.to],siz[son[x]]<siz[tmp.to]&&(son[x]=tmp.to));
}
I void dfs2(int x,int last){
	yyy tmp;top[x]=last;id[x]=++idea;dist[x]=dist[fa[x]]+A[x];T.build(id[x],A[x]);if(!son[x]) return;dfs2(son[x],last);for(int i=s.h[x];i;i=tmp.z) tmp=s.f[i],tmp.to^fa[x]&&tmp.to^son[x]&&(dfs2(tmp.to,tmp.to),0);
}
I ll find(int x,int now){ll Ans=0;while(x)Ans+=T.find(id[top[x]],id[x],now),x=fa[top[x]];return Ans;}
int main(){
	freopen("1.in","r",stdin);
	re int i,j;scanf("%d%d%d",&n,&m,&k);for(i=1;i<=n;i++) scanf("%d",&W[i]),Ws[i]=W[i];sort(Ws+1,Ws+n+1);for(tots[1]=1,i=2;i<=n;i++) tots[i]=tots[i-1]+(Ws[i]!=Ws[i-1]);
	for(i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),s.add(x,y,z),s.add(y,x,z);dfs1(1,0);dfs2(1,1);for(i=1;i<=n;i++){l=0;r=n+1;while(l+1<r) mid=l+r>>1,(Ws[mid]<W[i]?l:r)=mid;W[i]=tots[r];Id[W[i]].push_back(i);}
	for(i=1;i<=n;i++)for(root[i]=root[i-1],Ans1[i]=Ans1[i-1],Ans2[i]=Ans2[i-1],j=0;j<Id[i].size();j++) {x=Id[i][j];Ans1[i]++,Ans2[i]+=dist[x];while(x) T.insert(id[top[x]],id[x],root[i]),x=fa[top[x]];}
	while(m--){scanf("%d%lld%lld",&z,&x,&y);L=min((x+LA)%k,(y+LA)%k);R=max((x+LA)%k,(y+LA)%k);l=0;r=n+1;while(l+1<r) mid=l+r>>1,(Ws[mid]>=L?r:l)=mid;L=tots[r];l=0;r=n+1;while(l+1<r) mid=l+r>>1,(Ws[mid]<=R?l:r)=mid;R=tots[l];LA=dist[z]*(Ans1[R]-Ans1[L-1])+(Ans2[R]-Ans2[L-1])-(find(z,root[R])-find(z,root[L-1]))*2;printf("%lld\n",LA);}
}

这篇关于luogu P3241 [HNOI2015]开店的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！