Description

?風(fēng)見幽香有一個(gè)好朋友叫八云紫，她們經(jīng)常一起看星星看月亮從詩詞歌賦談到

人生哲學(xué)。最近她們靈機(jī)一動(dòng)，打算在幻想鄉(xiāng)開一家小店來做生意賺點(diǎn)錢。這樣的 想法當(dāng)然非常好啦，但是她們也發(fā)現(xiàn)她們面臨著一個(gè)問題，那就是店開在哪里，面 向什么樣的人群。很神奇的是，幻想鄉(xiāng)的地圖是一個(gè)樹形結(jié)構(gòu)，幻想鄉(xiāng)一共有 n 個(gè)地方，編號為 1 到 n，被 n-1 條帶權(quán)的邊連接起來。每個(gè)地方都住著一個(gè)妖怪， 其中第 i 個(gè)地方的妖怪年齡是 x_i。妖怪都是些比較喜歡安靜的家伙，所以它們并 不希望和很多妖怪相鄰。所以這個(gè)樹所有頂點(diǎn)的度數(shù)都小于或等于 3。妖怪和人一 樣，興趣點(diǎn)隨著年齡的變化自然就會(huì)變化，比如我們的 18 歲少女幽香和八云紫就 比較喜歡可愛的東西。幽香通過研究發(fā)現(xiàn)，基本上妖怪的興趣只跟年齡有關(guān)，所以 幽香打算選擇一個(gè)地方 u（u為編號），然后在 u開一家面向年齡在 L到R 之間（即 年齡大于等于 L、小于等于 R）的妖怪的店。也有可能 u這個(gè)地方離這些妖怪比較 遠(yuǎn)，于是幽香就想要知道所有年齡在 L 到 R 之間的妖怪，到點(diǎn) u 的距離的和是多 少（妖怪到 u 的距離是該妖怪所在地方到 u 的路徑上的邊的權(quán)之和） ，幽香把這個(gè) 稱為這個(gè)開店方案的方便值。幽香她們還沒有決定要把店開在哪里，八云紫倒是準(zhǔn) 備了很多方案，于是幽香想要知道，對于每個(gè)方案，方便值是多少呢。

Input

?第一行三個(gè)用空格分開的數(shù) n、Q和A，表示樹的大小、開店的方案個(gè)數(shù)和妖

怪的年齡上限。? 第二行n個(gè)用空格分開的數(shù) x_1、x_2、…、x_n，x_i 表示第i 個(gè)地點(diǎn)妖怪的年 齡，滿足0<=x_i<A。(年齡是可以為 0的，例如剛出生的妖怪的年齡為 0。)? 接下來 n-1 行，每行三個(gè)用空格分開的數(shù) a、b、c，表示樹上的頂點(diǎn) a 和 b 之 間有一條權(quán)為c(1 <= c <= 1000)的邊，a和b 是頂點(diǎn)編號。? 接下來Q行，每行三個(gè)用空格分開的數(shù) u、 a、 b。對于這 Q行的每一行，用 a、 b、A計(jì)算出 L和R，表示詢問“在地方 u開店，面向妖怪的年齡區(qū)間為[L,R]的方 案的方便值是多少”。對于其中第 1 行，L 和 R 的計(jì)算方法為：L=min(a%A,b%A),? R=max(a%A,b%A)。對于第 2到第 Q行，假設(shè)前一行得到的方便值為 ans，那么當(dāng) 前行的 L 和 R 計(jì)算方法為： L=min((a+ans)%A,(b+ans)%A),? R=max((a+ans)%A,(b+ans)%A)。?

Output

對于每個(gè)方案，輸出一行表示方便值。?

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。對于所有數(shù)據(jù)，滿足 A<=10^9

Source

?

哎，原來這是一道主席樹的套路題啊，然而當(dāng)年用動(dòng)態(tài)點(diǎn)分治做碼得要死。。。

對于每個(gè)u要求：

拆開一下，相當(dāng)于是求：

前兩項(xiàng)都可以通過dis數(shù)組的前綴和求解，問題的瓶頸在于后面一項(xiàng)。。。

這一項(xiàng)，1-lca的路徑其實(shí)是1-v的路徑和1-u的路徑的交。。。

首先我們不考慮年齡限制，我們只需要把1--v路徑上的點(diǎn)都打上標(biāo)記，然后只要查詢1--u路徑上的和即可。。。

(跟LNOI的LCA類似，相當(dāng)于是線段樹上區(qū)間修改和區(qū)間求和。。。)

加上年齡限制的話，我們可以把點(diǎn)按照年齡大小依次加入，

然后可持久化一下，對與每個(gè)年齡都建一棵線段樹(每個(gè)點(diǎn)都是在歷史版本上修改log個(gè)區(qū)間)

然后查詢的話直接利用前綴和的性質(zhì)相減即可，lazy實(shí)現(xiàn)標(biāo)記永久化。。。

(史上最強(qiáng)樣例，沒有之一。。。)

// MADE BY QT666 #include<cstdio> #include<algorithm> #include<cmath> #include<iostream> #include<cstring> #include<vector> #define int long long using namespace std; typedef long long ll; const int N=300050; int head[N],to[N],nxt[N],v[N],cnt; int size[N],top[N],son[N],deep[N],fa[N],dfn[N],tt,dis[N],d[N]; int sz,rt[N],ls[N*20],rs[N*20],sum[N*20],lazy[N*20],res[N],res2[N],num[N]; int hsh[N],a[N],tot,n,Q,A; void dfs1(int x,int f){size[x]=1;deep[x]=deep[f]+1;for(int i=head[x];i;i=nxt[i]){int y=to[i];if(y!=f){d[y]=v[i];dis[y]=dis[x]+v[i];dfs1(y,x);fa[y]=x;size[x]+=size[y];if(size[y]>size[son[x]]) son[x]=y;}} } void dfs2(int x,int ff){top[x]=ff;dfn[x]=++tt;res[tt]=res[tt-1]+d[x];if(son[x]) dfs2(son[x],ff);for(int i=head[x];i;i=nxt[i]){int y=to[i];if(y!=fa[x]&&y!=son[x]) dfs2(y,y);} } void update(int x,int &y,int l,int r,int xl,int xr){y=++sz;ls[y]=ls[x],rs[y]=rs[x];lazy[y]=lazy[x];sum[y]=sum[x];if(xl<=l&&r<=xr){sum[y]+=(res[r]-res[l-1]);lazy[y]++;return;}int mid=(l+r)>>1;if(xr<=mid) update(ls[x],ls[y],l,mid,xl,xr);else if(xl>mid) update(rs[x],rs[y],mid+1,r,xl,xr);else update(ls[x],ls[y],l,mid,xl,mid),update(rs[x],rs[y],mid+1,r,mid+1,xr);sum[y]=sum[ls[y]]+sum[rs[y]]+lazy[y]*(res[r]-res[l-1]); } int query(int x,int y,int l,int r,int xl,int xr,int la){if(xl<=l&&r<=xr){return sum[y]-sum[x]+la*(res[r]-res[l-1]);}int mid=(l+r)>>1;la+=lazy[y]-lazy[x];if(xr<=mid) return query(ls[x],ls[y],l,mid,xl,xr,la);else if(xl>mid) return query(rs[x],rs[y],mid+1,r,xl,xr,la);else return query(ls[x],ls[y],l,mid,xl,mid,la)+query(rs[x],rs[y],mid+1,r,mid+1,xr,la); } vector<int> p[N]; void insert(int x,int age){while(x){update(rt[age],rt[age],1,n,dfn[top[x]],dfn[x]);x=fa[top[x]];} } int ask(int x,int l,int r){int ret=0;while(x){ret+=query(rt[l-1],rt[r],1,n,dfn[top[x]],dfn[x],0);x=fa[top[x]];}return ret; } void lnk(int x,int y,int z){to[++cnt]=y,nxt[cnt]=head[x],v[cnt]=z,head[x]=cnt;to[++cnt]=x,nxt[cnt]=head[y],v[cnt]=z,head[y]=cnt; } main(){scanf("%lld%lld%lld",&n,&Q,&A);for(int i=1;i<=n;i++) scanf("%lld",&a[i]),hsh[++tot]=a[i];sort(hsh+1,hsh+1+tot);tot=unique(hsh+1,hsh+1+tot)-hsh-1;for(int i=1;i<=n;i++) a[i]=lower_bound(hsh+1,hsh+1+tot,a[i])-hsh,p[a[i]].push_back(i);for(int i=1;i<n;i++){int x,y,z;scanf("%lld%lld%lld",&x,&y,&z);lnk(x,y,z);}dfs1(1,0);dfs2(1,1);for(int i=1;i<=tot;i++){rt[i]=rt[i-1];res2[i]=res2[i-1];num[i]=num[i-1];for(int j=0;j<p[i].size();j++) insert(p[i][j],i),res2[i]+=dis[p[i][j]],num[i]++;}int ans=0;while(Q--){int u,a,b;scanf("%lld%lld%lld",&u,&a,&b);int l=min((a+ans)%A,(b+ans)%A),r=max((a+ans)%A,(b+ans)%A);l=lower_bound(hsh+1,hsh+1+tot,l)-hsh,r=upper_bound(hsh+1,hsh+1+tot,r)-hsh-1;ans=res2[r]-res2[l-1]+(num[r]-num[l-1])*dis[u]-2*ask(u,l,r);printf("%lld\n",ans);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/qt666/p/7265067.html

總結(jié)

以上是生活随笔為你收集整理的bzoj 4012: [HNOI2015]开店 主席树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。