LibreOJ 2116 「HNOI2015」开店

据说还可以动态点分治？
壮哉我大优美树剖！

跟「『2017 山东一轮集训 Day5』距离」一样的 trick。
目的是求路径的交，类似地到根加一然后计算贡献。

此题是对点权在 [L,R] 内的点与某钦定点的距离求和，容易想到转化为前缀和相减的形式，然后对线段树持久化。
并且需要离散化。
（不过直接用 map 好像也是可以的，每次查询的时候 lower/upper_bound 最近的那棵树）

这么神的题居然一遍过了，恨没生在 HNOI2015……

代码：

#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
    for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
    w ? x = -x : x;
}

const int N = 15e4;
int n,q,lim;
int a[N + 5],ind[N + 5],len;
int to[(N << 1) + 5],val[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
pair<int,int> t[N + 5];
long long lastans;
inline void add(int u,int v,int w)
{
    static int tot = 0;
    to[++tot] = v,val[tot] = w,pre[tot] = first[u],first[u] = tot;
}
int fa[N + 5],dep[N + 5],sz[N + 5],son[N + 5],top[N + 5],id[N + 5],rk[N + 5],w[N + 5];
int cnt[N + 5];
long long dis[N + 5],sum[N + 5];
void dfs1(int p)
{
    sz[p] = 1;
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ fa[p])
        {
            dep[to[i]] = dep[p] + 1,dis[to[i]] = dis[p] + val[i],fa[to[i]] = p,w[to[i]] = val[i],dfs1(to[i]),sz[p] += sz[to[i]];
            if(!son[p] || sz[to[i]] > sz[son[p]])
                son[p] = to[i];
        }
}
void dfs2(int p)
{
    static int tot = 0;
    rk[id[p] = ++tot] = p;
    if(son[p])
        top[son[p]] = top[p],dfs2(son[p]);
    for(register int i = first[p];i;i = pre[i])
        if(!id[to[i]])
            top[to[i]] = to[i],dfs2(to[i]);
}
struct node
{
    long long sum,val,tag;
    int ls,rs;
} seg[(N << 6) + 10];
int rt[N + 5],seg_tot;
void build(int &p,int tl,int tr)
{
    p = ++seg_tot;
    if(tl == tr)
    {
        seg[p].val = w[rk[tl]];
        return ;
    }
    int mid = tl + tr >> 1;
    build(seg[p].ls,tl,mid),build(seg[p].rs,mid + 1,tr);
    seg[p].val = seg[seg[p].ls].val + seg[seg[p].rs].val;
}
void update(int l,int r,int &p,int tl,int tr)
{
    seg[++seg_tot] = seg[p],p = seg_tot;
    if(l <= tl && tr <= r)
    {
        seg[p].sum += seg[p].val,++seg[p].tag;
        return ;
    }
    int mid = tl + tr >> 1;
    if(l <= mid)
        update(l,r,seg[p].ls,tl,mid);
    if(r > mid)
        update(l,r,seg[p].rs,mid + 1,tr);
    seg[p].sum = seg[seg[p].ls].sum + seg[seg[p].rs].sum + seg[p].tag * seg[p].val;
}
inline pair<long long,long long> operator+(const pair<long long,long long> &a,const pair<long long,long long> &b)
{
    return make_pair(a.first + b.first,a.second + b.second);
}
pair<long long,long long> query(int l,int r,int p,int tl,int tr)
{
    if(!p || (l <= tl && tr <= r))
        return make_pair(seg[p].sum,seg[p].val);
    int mid = tl + tr >> 1;
    pair<long long,long long> ret(0,0);
    if(l <= mid)
        ret = ret + query(l,r,seg[p].ls,tl,mid);
    if(r > mid)
        ret = ret + query(l,r,seg[p].rs,mid + 1,tr);
    ret.first += ret.second * seg[p].tag;
    return ret;
}
long long query(int p,int l,int r)
{
    long long ret = sum[r] - sum[l] + dis[p] * (cnt[r] - cnt[l]);
    while(p)
        ret -= (query(id[top[p]],id[p],rt[r],1,n).first - query(id[top[p]],id[p],rt[l],1,n).first) * 2,p = fa[top[p]];
    return ret;
}
int main()
{
    read(n),read(q),read(lim);
    for(register int i = 1;i <= n;++i)
        read(a[i]),ind[i] = a[i];
    sort(ind + 1,ind + n + 1),len = unique(ind + 1,ind + n + 1) - ind - 1;
    for(register int i = 1;i <= n;++i)
        a[i] = lower_bound(ind + 1,ind + len + 1,a[i]) - ind,t[i] = make_pair(a[i],i);
    int u,v,w;
    for(register int i = 1;i < n;++i)
        read(u),read(v),read(w),add(u,v,w),add(v,u,w);
    dep[1] = top[1] = 1,dfs1(1),dfs2(1),build(rt[0],1,n);
    sort(t + 1,t + n + 1);
    for(register int i = 1,j = 1;rt[i] = rt[i - 1],sum[i] = sum[i - 1],cnt[i] = cnt[i - 1],i <= len;++i)
        for(;t[j].first <= i && j <= n;++j)
        {
            int x = t[j].second;
            sum[i] += dis[x],++cnt[i];
            while(x)
                update(id[top[x]],id[x],rt[i],1,n),x = fa[top[x]];
        }
    int x,l,r;
    while(q--)
    {
        read(x),read(l),read(r),l = (l + lastans) % lim,r = (r + lastans) % lim;
        if(l > r)
            swap(l,r);
        l = lower_bound(ind + 1,ind + len + 1,l) - ind - 1,r = upper_bound(ind + 1,ind + len + 1,r) - ind - 1;
        printf("%lld\n",lastans = query(x,l,r));
    }
}