前缀和 + 扫描会给人惊喜

看上去更麻烦的做法却通向了正解

懵逼的 题目

神题Orz

扯淡的 题解

省(旅)队(游)集(C)训(S)回来之后感觉做题状态肥肠不得劲, 加之又发现班没了…掏出之前的坑打算填一下…结果…

这题好神啊Orzzz

抄题解.jpg

(以下编号均从$1$开始)

我们考虑一组询问的时候, 查询$\sum _{i\in[le, ri]} deep(LCA(z, i))$, 我们发现这个$LCA$很碍事, 于是可以把所有的$i\in [le, ri]$到根的路径都加一, 然后查询$z$到根的区间和, 就是答案了

看上去多此一举, 但是我们发现, 这个玩意是满足前缀和的性质的, 也就是说
$$
\sum _{i\in [le, ri]} deep(LCA(z, i)) = \sum_{i\in [0, ri]}{deep{LCA(z, i)}} - \sum_{i \in [0, le - 1]} {deep(LCA(z, i))}
$$
这样我们考虑多组询问的时候, 可以离线所有的$z$, 然后从$1$到$n$扫描, 计算出每一个询问的两个端点上, $z$到根的区间和, 然后作差就是这个询问的答案了

是不是很妙?

沙茶的 代码

注意在进行有取膜的前缀和或差分运算的时候判断负数的情况(我会告诉你我因为这个调了一天?)

/**************************************************************
    Problem: 3626
    User: Cansult
    Language: C++
    Result: Accepted
    Time:1592 ms
    Memory:10192 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define MAXN (50000 + 5)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define Gary (201314)
using namespace std;
const int root = 1;
struct node
{
    int zh, le, ri, lazy;
}b[MAXN << 2];
struct tnode
{
    int fa, deep, begin, end, size, hs, top;
}ta[MAXN];
struct tedg
{
    int from, to, next;
}tb[MAXN << 1];
int tg[MAXN], cntb, cnta, ans[MAXN];
void adn(int from, int to)
{
    tb[++cntb].next = tg[from];
    tb[cntb].from = from, tb[cntb].to = to;
    tg[from] = cntb;
}
void init(int dq)
{
    ta[dq].size = 1;
    for (int i = tg[dq]; i; i = tb[i].next)
        if (tb[i].to != ta[dq].fa)
        {
            ta[tb[i].to].fa = dq;
            ta[tb[i].to].deep = ta[dq].deep + 1;
            init(tb[i].to);
            ta[dq].size += ta[tb[i].to].size;
            if (ta[tb[i].to].size > ta[ta[dq].hs].size)
                ta[dq].hs = tb[i].to;
        }
}
void dfs(int dq)
{
    ta[dq].begin = ++cnta;
    if (ta[dq].hs)
        ta[ta[dq].hs].top = ta[dq].top, dfs(ta[dq].hs);
    for (int i = tg[dq]; i; i = tb[i].next)
        if (tb[i].to != ta[dq].fa && tb[i].to != ta[dq].hs)
            ta[tb[i].to].top = tb[i].to, dfs(tb[i].to);
    ta[dq].end = cnta;
}
void js(int dq, int le, int ri)
{
    b[dq].le = le, b[dq].ri = ri;
    b[dq].lazy = 0;
    if (le == ri)
        return ;
    int mi = (le + ri) >> 1;
    js(LS(dq), le, mi);
    js(RS(dq), mi + 1, ri);
}
void xg(int dq, int le, int ri, int zh)
{
    b[dq].zh = (b[dq].zh + (ri - le + 1) * zh) % Gary; 
    if (b[dq].le == le && b[dq].ri == ri)
    {
        b[dq].lazy += zh;
        return ;
    }
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (le > mi)
        xg(RS(dq), le, ri, zh);
    else if (ri <= mi)
        xg(LS(dq), le, ri, zh);
    else
        xg(LS(dq), le, mi, zh), xg(RS(dq), mi + 1, ri, zh);
}
int cx(int dq, int le, int ri)
{
    if (b[dq].le == le && b[dq].ri == ri)
        return b[dq].zh;
    int mi = (b[dq].le + b[dq].ri) >> 1, re = b[dq].lazy * (ri - le + 1) % Gary;
    if (le > mi)
        re = (re + cx(RS(dq), le, ri)) % Gary;
    else if (ri <= mi)
        re = (re + cx(LS(dq), le, ri)) % Gary;
    else
        re = (re + cx(LS(dq), le, mi) + cx(RS(dq), mi + 1, ri)) % Gary;
    return re;
}
void txg(int x)
{
    while (ta[x].top != root)
    {
        xg(root, ta[ta[x].top].begin, ta[x].begin, 1);
        x = ta[ta[x].top].fa;
    }
    xg(root, ta[root].begin, ta[x].begin, 1);
}
int tcx(int x)
{
    int re = 0;
    while (ta[x].top != root)
    {
        re = (re + cx(root, ta[ta[x].top].begin, ta[x].begin)) % Gary;
        x = ta[ta[x].top].fa;
    }
    re = (re + cx(root, ta[root].begin, ta[x].begin)) % Gary;
    return re;
}
int main()
{
    int n, q;
    vector<int> nwz[MAXN], bh[MAXN];
    scanf("%d%d", &n, &q);
    for (int i = 2, srx; i <= n; i++)
    {
        scanf("%d", &srx);
        ++srx;
        adn(srx, i), adn(i, srx);
    }
    ta[root].fa = root, ta[root].deep = 1, ta[root].top = root;
    init(root), dfs(root);
    js(root, 1, n);
    for (int i = 1, srx, sry, srz; i <= q; i++)
        scanf("%d%d%d", &srx, &sry, &srz), nwz[srx].push_back(-srz - 1), nwz[sry + 1].push_back(srz + 1), bh[srx].push_back(i), bh[sry + 1].push_back(i);
    for (int i = 1; i <= n; i++)
    {
        txg(i);
        for (int j = 0; j < nwz[i].size(); j++)
            if (nwz[i][j] > 0)
                ans[bh[i][j]] += tcx(nwz[i][j]);
            else
                ans[bh[i][j]] = -tcx(-nwz[i][j]);
    }
    for (int i = 1; i <= q; i++) // 注意负数
        while (ans[i] < 0)
            ans[i] = (ans[i] + Gary) % Gary;
    for (int i = 1; i <= q; i++)
        printf("%d\n", ans[i] % Gary);
    return 0;

}

By 沙茶 Cansult