Cansult's blog

即使愿望永远无法实现
我也不愿就这样放手

0%

翻车笔记 [LNOI2014]LCA [树链剖分, 清奇脑回路, 翻车, 前缀和]

Posted on Edited on In

前缀和 + 扫描会给人惊喜

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

懵逼的 题目

神题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\)到根的区间和, 然后作差就是这个询问的答案了

是不是很妙?

沙茶的 代码

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
/**************************************************************
    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