貌似做法比较多？
写的动态树分治
还有一些树剖主席树的高端做法？
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
// <4012.cpp> - Mon Feb 20 16:45:12 2017 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; typedef vector<pair<int,lol> > vct; #define next nxt template<typename T> inline void gg(T &res){ res=0;T fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); res*=fh; } inline int gi(){int x;gg(x);return x;} inline lol gl(){lol x;gg(x);return x;} const int MAXN=150010; const int MAXM=300010; const lol INF=1e18; int bt,b[MAXN],next[MAXM],to[MAXM],val[MAXM]; inline void add(int x,int y,int z){ next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=z; next[++bt]=b[y];b[y]=bt;to[bt]=x;val[bt]=z; } int size[MAXN],k[MAXN]; bool kill[MAXN]; int gr(int x,int f,int S){ int r=0;size[x]=1;k[x]=0; for(int i=b[x];i;i=next[i]){ if(to[i]==f||kill[to[i]])continue; int p=gr(to[i],x,S); if(k[p]<k[r])r=p; size[x]+=size[to[i]]; k[x]=max(k[x],size[to[i]]); } k[x]=max(k[x],S-size[x]); return k[x]<k[r]?x:r; } int u[MAXN],a[MAXN],f[MAXN]; lol dis[MAXN],tf[MAXN]; vct sm1[MAXN],sm2[MAXN]; void dfs(int x,int f,vct &v1,vct &v2){ v1.push_back(make_pair(x,dis[x])); v2.push_back(make_pair(a[x],dis[x])); for(int i=b[x];i;i=next[i]){ if(to[i]==f||kill[to[i]])continue; dis[to[i]]=dis[x]+val[i]; dfs(to[i],x,v1,v2); } } void work(int &x,int S){ kill[x=gr(x,0,S)]=1; tf[x]=dis[x]; for(int i=b[x];i;i=next[i]){ if(kill[to[i]]){to[i]=0;continue;} vct tmp;tmp.push_back(make_pair(-1,0)); dis[to[i]]=val[i]; dfs(to[i],0,sm1[x],tmp); sort(tmp.begin(),tmp.end()); for(int j=1;j<tmp.size();j++)tmp[j].second+=tmp[j-1].second; work(to[i],size[to[i]]); f[to[i]]=x;sm2[to[i]]=tmp; } sm1[x].push_back(make_pair(x,0)); sort(sm1[x].begin(),sm1[x].end()); } lol query(int x,int R){ lol ans=0; pair<int,lol>pr1=make_pair(x,0),pr2=make_pair(R,INF); for(int last=0;x;last=x,x=f[x]){ int p=lower_bound(sm1[x].begin(),sm1[x].end(),pr1)-sm1[x].begin(); for(int i=b[x];i;i=next[i]){ if(!to[i]||to[i]==last)continue; int l=upper_bound(sm2[to[i]].begin(),sm2[to[i]].end(),pr2)-sm2[to[i]].begin()-1; ans+=sm1[x][p].second*l+sm2[to[i]][l].second; } if(a[x]<=R)ans+=sm1[x][p].second; } return ans; } int main(){ int n=gi(),q=gi(),A=gi(); for(int i=1;i<=n;i++)u[i]=a[i]=gi(); sort(u+1,u+n+1); int t=unique(u+1,u+n+1)-u-1; for(int i=1;i<=n;i++)a[i]=lower_bound(u+1,u+t+1,a[i])-u; for(int i=1;i<n;i++){ int x=gi(),y=gi(),z=gi(); add(x,y,z); } k[0]=n;work(n,n); lol ans=0; while(q--){ int x=gi(); lol a=(gl()+ans)%A,b=(gl()+ans)%A; int L=lower_bound(u+1,u+t+1,min(a,b))-u,R=upper_bound(u+1,u+t+1,max(a,b))-u-1; printf("%lld\n",ans=query(x,R)-query(x,L-1)); } return 0; } |
说点什么