BZOJ4012: [HNOI2015]开店
树链剖分 可持久化线段树    2016-12-30 21:22:53    390    0    0

4012: [HNOI2015]开店

Time Limit: 70 Sec  Memory Limit: 512 MB
Submit: 1101  Solved: 493
[Submit][Status][Discuss]

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

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

 

HINT

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

 

Solution

如果没有年龄限制,问题就是求树上所有点到u的距离和

每个点到u的距离为dis(1,v) + dis(1,u) - 2 * dis(1, lca(u,v)),我们只要求出lca到根的距离,就容易得到答案

求lca的距离和是个经典问题,把v到根的路径上都加上边权,答案就是求u到根的路径上的权值和

这个可以用树链剖分之类的维护

 

加上年龄的限制,可以把树链剖分可持久化一下

按照年龄排序,依次把贡献加入,询问[L,R]变成 [1,R] - [1,L-1]

 

需要注意的是可持久化线段树不太好区间修改,可以把标记永久化一下

 

Source code

/*{{{*/
#include <bits/stdc++.h>

#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

typedef long long ll;
typedef std::pair<int, int> pii;

std::string Name = __FILE__;
std::string iput = Name.substr(0, Name.length() - 4) + ".in";
std::string oput = Name.substr(0, Name.length() - 4) + ".out";

template <class T> inline bool chkmin(T &x, T y) { return x > y ? x = y, true : false; }
template <class T> inline bool chkmax(T &x, T y) { return x < y ? x = y, true : false; }

template <class T> inline T &read(T &x)
{
    static int f;
    static char c; 
    for (f = 1; !isdigit(c = getchar()); ) {
        if (c == '-')
            f = -1;
    }
    for (x = 0; isdigit(c); c = getchar()) {
        x = x * 10 + c - 48;
    }
    return x *= f;
}
 
template <class T> inline void write(T x, const char p = '\n')
{
    static int top;
    static int s[30];
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    do s[++ top] = x % 10 + 48;
    while (x /= 10);
    while (top)
        putchar(s[top --]);
    putchar(p);
}
/*}}}*/
 
const int maxn = 1.5e5 + 5;
 
int n;
int dep[maxn];

int st[maxn], cnte; 

struct edge { int to, next, w; } e[maxn * 2];

inline void addedge(int u, int v, int w)
{
    e[++ cnte] = (edge) {v, st[u], w}; st[u] = cnte;
}

namespace Heavy_light_decompsition
{
    int root;
    int val[maxn];

    namespace Segment
    {
        int tot;

        struct node 
        { 
            int val, l, r, lazy; 
            long long sum;
        } s[maxn * 45];

#define LS s[x].l
#define RS s[x].r

        inline void pushup(int x)
        {
            s[x].sum = s[LS].sum + s[RS].sum + (long long)s[x].lazy * s[x].val;
        }

        void build(int &x, int l, int r)
        {
            x = ++ tot;
            if (l == r) {
                s[x].val = val[l];
                return;
            }
            int mid = (l + r) >> 1;
            build(LS, l, mid);
            build(RS, mid + 1, r);
            s[x].val = s[LS].val + s[RS].val;
            pushup(x);
        }

        void update(int &x, int l, int r, int p, int q)
        {
            s[++ tot] = s[x];
            x = tot;
            if (p <= l && r <= q) {
                s[x].sum += s[x].val;
                ++ s[x].lazy;
                return;
            }
            int mid = (l + r) >> 1;
            if (p <= mid) update(LS, l, mid, p, q);
            if (q > mid) update(RS, mid + 1, r, p, q);
            pushup(x);
        }

        long long query(int x, int l, int r, int p, int q, int delta = 0)
        {
            if (p <= l && r <= q)
                return s[x].sum + (long long)delta * s[x].val;
            long long ret = 0;
            int mid = (l + r) >> 1;
            if (p <= mid) ret += query(LS, l, mid, p, q, delta + s[x].lazy);
            if (q > mid) ret += query(RS, mid + 1, r, p, q, delta + s[x].lazy);
            return ret;
        }

#undef LS
#undef RS
    }

    int TIME;
    int fa[maxn], faw[maxn], dfn[maxn], size[maxn], son[maxn], top[maxn];

    void dfs1(int x, int Fa)
    {
        fa[x] = Fa;
        dep[x] = dep[Fa] + faw[x];
        size[x] = 1;
        for (int i = st[x]; i; i = e[i].next) {
            int v = e[i].to;
            if (v != Fa) {
                faw[v] = e[i].w;
                dfs1(v, x);
                size[x] += size[v];
                if (size[son[x]] < size[v])
                    son[x] = v;
            }
        }
    }

    void dfs2(int x, int Top)
    {
        top[x] = Top;
        dfn[x] = ++ TIME;
        if (son[x])
            dfs2(son[x], Top);
        for (int i = st[x]; i; i = e[i].next) {
            int v = e[i].to;
            if (v != fa[x] && v != son[x])
                dfs2(v, v);
        }
    }

    void build()
    {
        dfs1(1, 0);
        dfs2(1, 1);
        faw[1] = 0;
        for (int i = 1; i <= n; ++ i)
            val[dfn[i]] = faw[i];
        Segment::build(root, 1, n);
    }

    void insert(int x)
    {
        while (x) {
            Segment::update(root, 1, n, dfn[top[x]], dfn[x]);
            x = fa[top[x]];
        }
    }

    long long query(int Root, int x)
    {
        if (!Root) return 0;
        long long ret = 0;
        while (x) {
            ret += Segment::query(Root, 1, n, dfn[top[x]], dfn[x]);
            x = fa[top[x]];
        }
        return ret;
    }
}


pii a[maxn];
int b[maxn];

int root[maxn];
long long sumv[maxn];
int count[maxn];

void exec()
{
    int A, Q;

    read(n);
    read(Q);
    read(A);
    for (int i = 1; i <= n; ++ i) {
        b[i] = read(a[i].first);
        a[i].second = i;
    }

    std::sort(a + 1, a + n + 1);
    std::sort(b + 1, b + n + 1);
    int size = std::unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; ++ i) {
        a[i].first = std::lower_bound(b + 1, b + size + 1, a[i].first) - b;
    }

    for (int i = 1; i < n; ++ i) {
        int u, v, w;
        read(u), read(v), read(w);
        addedge(u, v, w);
        addedge(v, u, w);
    }

    Heavy_light_decompsition::build();

    for (int i = 1; i <= n; ++ i) {
        count[a[i].first] = i;
        sumv[a[i].first] += dep[a[i].second];
        Heavy_light_decompsition::insert(a[i].second);
        root[a[i].first] = Heavy_light_decompsition::root;
    }

    for (int i = 1; i <= size; ++ i)
        sumv[i] += sumv[i - 1];

    long long ans = 0;

    while (Q --) {
        int u, L, R;
        read(u), read(L), read(R);
        (L += ans) %= A;
        (R += ans) %= A;
        if (L > R) 
            std::swap(L, R);
        L = std::lower_bound(b + 1, b + size + 1, L) - b;
        R = std::upper_bound(b + 1, b + size + 1, R) - b - 1;

        ans = sumv[R] - sumv[L - 1] + (long long)(count[R] - count[L - 1]) * dep[u] - 2 * (Heavy_light_decompsition::query(root[R], u) - Heavy_light_decompsition::query(root[L - 1], u));

        write(ans);

        ans %= A;
    }
}

/*{{{*/
int main() 
{
    if (fopen(iput.c_str(), "r") != NULL) {
        freopen(iput.c_str(), "r", stdin);
        freopen(oput.c_str(), "w", stdout);
    }

    exec();

    fclose(stdin);
    fclose(stdout);

    return 0;
}
/*}}}*/

 

Codeforce 286E
390 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航