【BZOJ4012】【HNOI2015】开店

貌似做法比较多？

写的动态树分治

还有一些树剖主席树的高端做法？

// <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;
}

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.

// 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;

}