BZOJ4012 [HNOI2015]開店

這道題因為太多人拿這個題卡$BZOJ$，于是成了權限題。。。

本蒟蒻表示沒錢氪金。。。

無奈，拿出了洛谷：P3241 [HNOI2015]開店

還有$LOJ$：#2116. 「HNOI2015」開店

這里附上洛谷的題面：

題目描述

風見幽香有一個好朋友叫八云紫，她們經常一起看星星看月亮從詩詞歌賦談到人生哲學。最近她們靈機一動，打算在幻想鄉開一家小店來做生意賺點錢。

這樣的想法當然非常好啦，但是她們也發現她們面臨著一個問題，那就是店開在哪里，面向什么樣的人群。很神奇的是，幻想鄉的地圖是一個樹形結構，幻想鄉一共有$n$個地方，編號為$1$ 到$n$被$n-1$ 條帶權的邊連接起來。每個地方都住著一個妖怪，其中第$i$個地方的妖怪年齡是 $x_i$ 。

妖怪都是些比較喜歡安靜的家伙，所以它們并不希望和很多妖怪相鄰。所以這個樹所有頂點的度數都小于或等于$3$。妖怪和人一樣，興趣點隨著年齡的變化自然就會變化，比如我們的$18$ 歲少女幽香和八云紫就比較喜歡可愛的東西。幽香通過研究發現，基本上妖怪的興趣只跟年齡有關，所以幽香打算選擇一個地方$u$ （$u$ 為編號），然后在$u$開一家面向年齡在$L$到$R$ 之間（即年齡大于等于$L$ 小于等于$R$ ）的妖怪的店。

也有可能$u$ 這個地方離這些妖怪比較遠，于是幽香就想要知道所有年齡在$L$ 到$R$ 之間的妖怪，到點$u$ 的距離的和是多少（妖怪到$u$ 的距離是該妖怪所在地方到$u$ 的路徑上的邊的權之和），幽香把這個稱為這個開店方案的方便值。

幽香她們還沒有決定要把店開在哪里，八云紫倒是準備了很多方案，于是幽香想要知道，對于每個方案，方便值是多少呢。

輸入輸出格式

輸入格式：

第一行三個用空格分開的數$n,Q$和$A$ ，表示樹的大小、開店的方案個數和妖怪的年齡上限。

第二行nn 個用空格分開的數$x_1,x_2,\ldots,x_n;x_i$表示第$i$個地點妖怪的年齡，滿足$0\le x_i\lt A$。(年齡是可以為$0$的，例如剛出生的妖怪的年齡為$0$ 。)

接下來$n-1$ 行，每行三個用空格分開的數$a$ 、$b$ 、$c$ ，表示樹上的頂點$a$ 和$b$ 之間有一條權為$c(1\le c\le1000)$的邊，$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)$ 。

輸出格式：

對于每個方案，輸出一行表示方便值。

輸入輸出樣例

輸入樣例#1：?復制

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

輸出樣例#1：?復制

說明

滿足$n\le1.5\times 10^5,Q\le2\times 10^5$ 。對于所有數據，滿足$A<=10^9$

題解Here!

感覺做完這題之后，自己的碼力和幾個月前不一樣了。。。

據說這題是動態淀粉質點分治？然而本蒟蒻并不會。。。

有時間再填坑吧感覺這輩子是不可能填坑的。。。

于是拿出了樹鏈剖分+主席樹。

每次詢問點權在$[L,R]$之間的所有點到某個點的距離之和，并且強制在線。

首先考慮一個簡化的版本：

詢問所有點到點$u$的距離和。

然后開始漫長地推式子。。。

當然，可以跳過漫長的過程直接看結論。。。

設$deep[i],size[i]$分別表示以$1$為根時第$i$個點的帶權深度和子樹大小。

在我的代碼中為了避免變量名沖突，就用$dis[i]$代替了這里的$deep[i]$，這點要注意一下。

觀察$1$為根和$u$為根會發生哪些變化。

$u$的子樹中某節點$v$的深度會從$deep[v]$變成$deep[v]-deep[u]$，相當于都減少了$deep[u]$，且有$size[u]$個點發生了此變化。

$fa[u]$的子樹，且不是$u$的子樹中的某節點$v$，深度會從$deep[v]$變成$deep[v]-deep[fa[u]]+deep[u]-deep[fa[u]]$，相當于減少了$2\times deep[fa[u]]-deep[u]$，且有$size[fa[u]]-size[u]$個點發生了此變化。

之后以此類推。

更具體的描述，定義$a_i$為$1$至$u$的鏈上的第$i$個點，$1$至$u$的鏈上共有$k$個點，那么所有點到$u$的距離之和可以用如下式子表示：

$$\sum_{i=1}^ndeep[i]-\sum_{i=1}^{k-1}(size[a_i]-size[a_i+1])\times (2\times deep[a_i]-deep[u])-size[u]\times deep[u]$$

展開：

$$\sum_{i=1}^ndeep[i]-size[u]\times deep[u]-(2\times \sum_{i=1}^{k-1}size[a_i]\times deep[a_i]-2\times\sum_{i=1}^{k-1}size[a_{i+1}]\times deep[a_i]-\sum_{i=1}^{k-1}size[a_i]\times deep[u]+\sum_{i=1}^{k-1}size[a_{i+1}]\times deep[u])$$

$$=\sum_{i=1}^ndeep[i]-size[u]\times deep[u]-2\times\sum_{i=1}^{k-1}size[a_i]\times deep[a_i]+2\sum_{i=1}^{k-1}size[a_{i+1}]\times deep[a_i]+\sum_{i=1}^{k-1}size[a_i]\times deep[u]-\sum_{i=1}^{k-1}size[a_{i+1}]\times deep[u]$$

把其中的某個式子提出來，化簡：

$$\sum_{i=1}^{k-1}size[a_i]\times deep[u]-\sum_{i=1}^{k-1}size[a_{i+1}]\times deep[u]$$

$$=\sum_{i=1}^{k-1}size[a_i]\times deep[u]-\sum_{i=2}^ksize[a_i]\times deep[u]$$

$$=size[a_1]\times deep[u]-size[a_k]\times deep[u]$$

$$=n\times deep[u]-size[u]\times deep[u]$$

于是原式變為：

$$\sum_{i=1}^ndeep[i]+n\times deep[u]-2\times size[u]\times deep[u]-2\times \sum_{i=1}^{k-1}size[a_i]\times deep[a_i]+2\times \sum_{i=1}^{k-1}size[a_{i+1}]\times deep[a_i]$$

現在觀察：

$$-2\sum_{i=1}^{k-1}size[a_i]\times deep[a_i]+2\sum_{i=1}^{k-1}size[a_{i+1}]\times deep[a_i]$$

即：

$$2\sum_{i=1}^{k-1}size[a_{i+1}]\times deep[a_i]-2\sum_{i=1}^{k-1}size[a_i]\times deep[a_i]$$

這里直接相減出現的$size[a_i]-size[a_{i+1}]$難以處理，我們考慮進行錯位相減。

$$\text{原式}=2\sum_{i=2}^ksize[a_i]\times deep[a_{i-1}]-2\sum_{i=1}^{k-1}size[a_i]\times deep[a_i]$$

$$=2\sum_{i=2}^ksize[a_i]\times deep[a_{i-1}]-2\sum_{i=2}^{k-1}size[a_i]\times deep[a_i](deep[a_1]=deep[1]=0)$$

$$=2\times size[a_k]\times deep[a_{k-1}]+2\sum_{i=2}^{k-1}size[a_i]\times (deep[a_{i-1}]-deep[a_i])$$

將原式中的$-2\times size[u]\times deep[u]$并入上式中，得到：

$$2\times size[a_k]\times deep[a_{k-1}]-2\times size[a_k]\times deep[a_k]+2\sum_{i=2}^{k-1}size[a_i]\times (deep[a_{i-1}]-deep[a_i])$$

$$=2\sum_{i=2}^ksize[a_i](deep[a_{i-1}]-deep[a_i])$$

注意到$deep[a_i]-deep[a_{i-1}]$是點$i$到其父節點的邊權，設為$fv[i]$。

故原式等于：

$$\sum_{i=1}^ndeep[i]+n\times deep[u]-2\sum_{i=2}^ksize[a_i]\times fv[a_i]$$

到此，我們的推式子結束了。

并且這玩意可以進行維護了。

現在考慮如何加入$[L,R]$的限制。

直接通過子樹查詢的方式進行，單次復雜度與樹高約為線性關系，顯然是鐵定$TLE$的。

怎么辦？

這時便要體會主席樹的版本作用。

將點按照點權排序，一個一個加入，最終答案便是$R$對應版本的主席樹的答案減去$L-1$對應版本的主席樹的答案。

也就是做一個差分：$Ans(L,R)=Ans(1,R)-Ans(1,L-1)$

而且，每次加入一個點的時候，樹的形態不發生變化，$fv[i]$不發生變化，只有$size[i]$發生變化。

所以只需把加入的這個點到根的路徑上的所有點的$size$進行$+1$即可。

查詢時從當前指定的點出發，向上統計$\sum size[i]\times fv[i]$。

這是可以通過樹鏈剖分維護的。

由于空間限制，需要使用標記永久化。

這題目就做完了。

好長。。。

附代碼：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 200010
using namespace std;
int n,m,age,c=1,d=1;
int root[MAXN];
int head[MAXN],deep[MAXN],son[MAXN],size[MAXN],fa[MAXN],id[MAXN],pos[MAXN],top[MAXN];
long long dis[MAXN],sum[MAXN];
struct Tree{int next,to,w;
}a[MAXN<<1];
struct Point{int val,id;friend bool operator <(const Point &p,const Point &q){if(p.val==q.val)return p.id<q.id;return p.val<q.val;}
}point[MAXN];
inline int read(){int date=0,w=1;char c=0;while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}return date*w;
}
namespace CT{#define LSON(x) a[x].l#define RSON(x) a[x].r#define DATA(x) a[x].data#define SUM(x) a[x].sum#define SIGN(x) a[x].cint size=0;struct Chairman_Tree{long long data,sum;int l,r,c;}a[MAXN<<7];inline void pushup(int rt){DATA(rt)=DATA(LSON(rt))+DATA(RSON(rt));SUM(rt)=SUM(LSON(rt))+SUM(RSON(rt))+DATA(rt)*SIGN(rt);}inline void buildtree(int l,int r,int &rt){a[++size]=a[rt];rt=size;SIGN(rt)=LSON(rt)=RSON(rt)=SUM(rt)=DATA(rt)=0;if(l==r){DATA(rt)=dis[pos[l]]-dis[fa[pos[l]]];return;}int mid=l+r>>1;buildtree(l,mid,LSON(rt));buildtree(mid+1,r,RSON(rt));pushup(rt);}void update(int l,int r,int lside,int rside,int &rt){a[++size]=a[rt];rt=size;if(l<=lside&&rside<=r){SIGN(rt)++;SUM(rt)+=DATA(rt);return;}int mid=lside+rside>>1;if(l<=mid)update(l,r,lside,mid,LSON(rt));if(mid<r)update(l,r,mid+1,rside,RSON(rt));pushup(rt);}long long query(int l,int r,int c,int lside,int rside,int rt){long long ans=0;if(l<=lside&&rside<=r)return (SUM(rt)+DATA(rt)*c);c+=SIGN(rt);int mid=lside+rside>>1;if(l<=mid)ans+=query(l,r,c,lside,mid,LSON(rt));if(mid<r)ans+=query(l,r,c,mid+1,rside,RSON(rt));return ans;}
}
inline void add(int u,int v,int w){a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++;a[c].to=u;a[c].w=w;a[c].next=head[v];head[v]=c++;
}
void dfs1(int rt){son[rt]=0;size[rt]=1;for(int i=head[rt];i;i=a[i].next){int will=a[i].to;if(!deep[will]){deep[will]=deep[rt]+1;dis[will]=dis[rt]+a[i].w;fa[will]=rt;dfs1(will);size[rt]+=size[will];if(size[son[rt]]<size[will])son[rt]=will;}}
}
void dfs2(int rt,int f){id[rt]=d++;pos[id[rt]]=rt;top[rt]=f;if(son[rt])dfs2(son[rt],f);for(int i=head[rt];i;i=a[i].next){int will=a[i].to;if(will!=fa[rt]&&will!=son[rt])dfs2(will,will);}
}
void update_path(int x,int y,int u){while(top[x]!=top[y]){if(deep[top[x]]<deep[top[y]])swap(x,y);CT::update(id[top[x]],id[x],1,n,root[u]);x=fa[top[x]];}if(deep[x]>deep[y])swap(x,y);CT::update(id[x],id[y],1,n,root[u]);
}
long long query_path(int x,int y,int u){long long s=0;while(top[x]!=top[y]){if(deep[top[x]]<deep[top[y]])swap(x,y);s+=CT::query(id[top[x]],id[x],0,1,n,root[u]);x=fa[top[x]];}if(deep[x]>deep[y])swap(x,y);s+=CT::query(id[x],id[y],0,1,n,root[u]);return s;
}
long long solve(int x,int u){return (sum[u]+dis[x]*u-2LL*query_path(1,x,u));
}
void work(){int l,r,u;long long last=0;while(m--){u=read();l=read();r=read();l=(l+last)%age;r=(r+last)%age;if(l>r)swap(l,r);l=lower_bound(point+1,point+n+1,(Point){l,0})-point;r=upper_bound(point+1,point+n+1,(Point){r,MAXN})-point-1;last=solve(u,r)-solve(u,l-1);printf("%lld\n",last);}
}
void init(){int u,v,w;n=read();m=read();age=read();for(int i=1;i<=n;i++){point[i].val=read();point[i].id=i;}for(int i=1;i<n;i++){u=read();v=read();w=read();add(u,v,w);}deep[1]=1;dfs1(1);dfs2(1,1);sort(point+1,point+n+1);CT::buildtree(1,n,root[0]);for(int i=1;i<=n;i++){sum[i]=sum[i-1]+dis[point[i].id];root[i]=root[i-1];update_path(1,point[i].id,i);}
}
int main(){init();work();return 0;
}