bzoj4012 [HNOI2015]开店

Description

风见幽香有一个好朋友叫八云紫，她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动，打算在幻想乡开一家小店来做生意赚点钱。这样的想法当然非常好啦，但是她们也发现她们面临着一个问题，那就是店开在哪里，面向什么样的人群。很神奇的是，幻想乡的地图是一个树形结构，幻想乡一共有 n个地方，编号为 1 到 n，被 n-1 条带权的边连接起来。每个地方都住着一个妖怪，其中第 i 个地方的妖怪年龄是 x_i。妖怪都是些比较喜欢安静的家伙，所以它们并不希望和很多妖怪相邻。所以这个树所有顶点的度数都小于或等于 3。妖怪和人一样，兴趣点随着年龄的变化自然就会变化，比如我们的 18 岁少女幽香和八云紫就比较喜欢可爱的东西。幽香通过研究发现，基本上妖怪的兴趣只跟年龄有关，所以幽香打算选择一个地方 u（u为编号），然后在 u开一家面向年龄在 L到R 之间（即年龄大于等于 L、小于等于 R）的妖怪的店。也有可能 u这个地方离这些妖怪比较远，于是幽香就想要知道所有年龄在 L 到 R 之间的妖怪，到点 u 的距离的和是多少（妖怪到 u 的距离是该妖怪所在地方到 u 的路径上的边的权之和），幽香把这个称为这个开店方案的方便值。幽香她们还没有决定要把店开在哪里，八云紫倒是准备了很多方案，于是幽香想要知道，对于每个方案，方便值是多少呢。

Input

第一行三个用空格分开的数 n、Q和A，表示树的大小、开店的方案个数和妖怪的年龄上限。

第二行n个用空格分开的数 x_1、x_2、…、x_n，x_i 表示第i 个地点妖怪的年龄，满足0<=x_i<A。(年龄是可以为 0的，例如刚出生的妖怪的年龄为 0。)

接下来 n-1 行，每行三个用空格分开的数 a、b、c，表示树上的顶点 a 和 b 之间有一条权为c(1 <= c <= 1000)的边，a和b 是顶点编号。

接下来Q行，每行三个用空格分开的数 u、 a、 b。对于这 Q行的每一行，用 a、b、A计算出 L和R，表示询问“在地方 u开店，面向妖怪的年龄区间为[L,R]的方案的方便值是多少”。对于其中第 1 行，L 和 R 的计算方法为：L=min(a%A,b%A), R=max(a%A,b%A)。对于第 2到第 Q行，假设前一行得到的方便值为 ans，那么当前行的 L 和 R 计算方法为： L=min((a+ans)%A,(b+ans)%A), R=max((a+ans)%A,(b+ans)%A)。

Output

对于每个方案，输出一行表示方便值。

Sample Input

10 10 10
0 0 7 2 1 4 7 7 7 9
1 2 270
2 3 217
1 4 326
2 5 361
4 6 116
3 7 38
1 8 800
6 9 210
7 10 278
8 9 8
2 8 0
9 3 1
8 0 8
4 2 7
9 7 3
4 7 0
2 2 7
3 2 1
2 3 4

Sample Output

1603
957
7161
9466
3232
5223
1879
1669
1282
0

HINT

满足 n<=150000,Q<=200000。对于所有数据，满足 A<=10^9。

正解：树链剖分+主席树。

这题有两种做法，第一种是网上流传的动态点分治，然后我不会。。所以我写的naive的树链剖分+主席树。不过似乎快些？

这题是要求∑dis(u,v) year[v]∈[l,r]，也就是∑dis[u]+dis[v]-2*dis[lca(u,v)] year[v]∈[l,r]，dis[u]为u到根的距离。

那么我们可以先考虑没有l和r限制的情况，首先公式的前两项我们都可以用前缀和维护，O(1)的查询，关键就是后面那个操作。我们可以用树链剖分+线段树，对于一个点到根结点的路径，每条边维护的值加上这条边的距离，然后查询的时候，只要查询u结点到根的路径和，那么就能保证查询到两点lca到根的距离，且不会重复查询。

那么，既然有了l和r的限制，线段树肯定不行了。那么我们就建立一棵以年龄为前缀的主席树，每次查询就是[l,r]的区间中查询点到根节点的路径和。插入路径时每次就从历史版本中用树剖寻找log个区间，然后修改就好。然而很不好写。。这题细节很多，例如离散化的边界等，还有主席树每次都必须要从上一个版本转移，不然会跪烂。。我就是因为这个调了很久。。

  1 //It is made by wfj_2048~
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <cstring>
  5 #include <cstdlib>
  6 #include <cstdio>
  7 #include <vector>
  8 #include <cmath>
  9 #include <queue>
 10 #include <stack>
 11 #include <map>
 12 #include <set>
 13 #define N (150010)
 14 #define il inline
 15 #define RG register
 16 #define ll long long
 17 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
 18 
 19 using namespace std;
 20 
 21 struct edge{ int nt,to,dis; }g[2*N];
 22 struct node{ int id,age; }s[N];
 23 
 24 int head[N],top[N],fa[N],son[N],tid[N],size[N],hsh[N],a[N];
 25 int lazy[150*N],ls[150*N],rs[150*N],rt[N],n,q,A,sz,tot,cnt,num;
 26 ll sum[150*N],res1[N],res2[N],w[N],d[N],dis[N],ans;
 27 
 28 il int gi(){
 29     RG int x=0,q=1; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
 30     if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x;
 31 }
 32 
 33 il void insert(RG int from,RG int to,RG int dis){ g[++num]=(edge){head[from],to,dis},head[from]=num; return; }
 34 
 35 il int cmp(const node &a,const node &b){ return a.age<b.age; }
 36 
 37 il void dfs1(RG int x,RG int p){
 38     fa[x]=p,size[x]=1; RG int v;
 39     for (RG int i=head[x];i;i=g[i].nt){
 40     v=g[i].to; if (v==p) continue;
 41     d[v]=g[i].dis,dis[v]=dis[x]+g[i].dis;
 42     dfs1(v,x); size[x]+=size[v];
 43     if (size[son[x]]<=size[v]) son[x]=v;
 44     }
 45     return;
 46 }
 47 
 48 il void dfs2(RG int x,RG int p,RG int anc){
 49     top[x]=anc,tid[x]=++cnt,w[cnt]=w[cnt-1]+d[x];
 50     res1[a[x]]+=(ll)dis[x],res2[a[x]]++;
 51     if (son[x]) dfs2(son[x],x,anc); RG int v;
 52     for (RG int i=head[x];i;i=g[i].nt){
 53     v=g[i].to; if (v==p || v==son[x]) continue;
 54     dfs2(v,x,v);
 55     }
 56     return;
 57 }
 58 
 59 il void update(RG int x,RG int &y,RG int l,RG int r,RG int xl,RG int xr){
 60     sum[y=++sz]=sum[x],lazy[y]=lazy[x],ls[y]=ls[x],rs[y]=rs[x];
 61     if (xl<=l && r<=xr){ sum[y]+=(ll)(w[r]-w[l-1]),lazy[y]++; return; }
 62     RG int mid=(l+r)>>1;
 63     if (xr<=mid) update(ls[x],ls[y],l,mid,xl,xr);
 64     else if (xl>mid) update(rs[x],rs[y],mid+1,r,xl,xr);
 65     else update(ls[x],ls[y],l,mid,xl,mid),update(rs[x],rs[y],mid+1,r,mid+1,xr);
 66     sum[y]=sum[ls[y]]+sum[rs[y]]+(ll)lazy[y]*(ll)(w[r]-w[l-1]); return;
 67 }
 68 
 69 il ll query(RG int x,RG int y,RG int l,RG int r,RG int xl,RG int xr,RG int la){
 70     if (xl<=l && r<=xr) return sum[y]-sum[x]+(ll)la*(ll)(w[r]-w[l-1]);
 71     RG int mid=(l+r)>>1; la+=lazy[y]-lazy[x];
 72     if (xr<=mid) return query(ls[x],ls[y],l,mid,xl,xr,la);
 73     else if (xl>mid) return query(rs[x],rs[y],mid+1,r,xl,xr,la);
 74     else return query(ls[x],ls[y],l,mid,xl,mid,la)+query(rs[x],rs[y],mid+1,r,mid+1,xr,la);
 75 }
 76 
 77 il void change(RG int id,RG int x){
 78     RG int last=rt[s[id-1].age]; //不计last会跪烂！！！
 79     while (x) update(last,rt[s[id].age],1,n,tid[top[x]],tid[x]),last=rt[s[id].age],x=fa[top[x]];
 80     return;
 81 }
 82 
 83 il ll Query(RG int x,RG int l,RG int r){
 84     RG ll res=0; while (x) res+=query(rt[l-1],rt[r],1,n,tid[top[x]],tid[x],0),x=fa[top[x]];
 85     return res;
 86 }
 87 
 88 il void work(){
 89     n=gi(),q=gi(),A=gi(); hsh[++tot]=0,hsh[++tot]=A+1;
 90     for (RG int i=1;i<=n;++i) hsh[++tot]=a[i]=gi();
 91     sort(hsh+1,hsh+tot+1); tot=unique(hsh+1,hsh+tot+1)-hsh-1;
 92     for (RG int i=1;i<=n;++i) a[i]=lower_bound(hsh+1,hsh+tot+1,a[i])-hsh;
 93     for (RG int i=1;i<n;++i){ RG int u=gi(),v=gi(),w=gi(); insert(u,v,w),insert(v,u,w); }
 94     dfs1(1,0),dfs2(1,0,1); for (RG int i=1;i<=n;++i) s[i]=(node){i,a[i]}; sort(s+1,s+n+1,cmp);
 95     for (RG int i=1;i<=n;++i) change(i,s[i].id);
 96     for (RG int i=1;i<=tot;++i) res1[i]+=res1[i-1],res2[i]+=res2[i-1];
 97     while (q--){
 98     RG int x=gi(),l=gi(),r=gi();
 99     l=(l+(int)(ans%A))%A,r=(r+(int)(ans%A))%A; if (l>r) swap(l,r);
100     l=lower_bound(hsh+1,hsh+tot+1,l)-hsh,r=upper_bound(hsh+1,hsh+tot+1,r)-hsh-1;
101     ans=res1[r]-res1[l-1]+(res2[r]-res2[l-1])*(ll)dis[x]-(Query(x,l,r)<<1);
102     printf("%lld
",ans);
103     }
104     return;
105 }
106 
107 int main(){
108     File("shop");
109     work();
110     return 0;
111 }