BZOJ 3052 「WC2013」糖果公园

发表于 | 分类于 |

树上莫队真好玩（
一不小心就写了 \(144\) 行（逃

首先考虑序列上的带修莫队，只要给询问加一维时间就可以了。
那么问题来了，怎么把问题放到树上？
用树剖把询问划分成几个区间。

这样子复杂度没法接受……
考虑把 DFS 序改一下，在递归到每个点和递归完每个点的时候都记录，变成括号序列。
我们定义括号序列中一段区间只有只出现了一次的数有贡献。
样例以 \(1\) 为根，得到的括号序列即 \(\{1,3,4,4,2,2,3,1\}\)。

设 \(st_p\) 表示递归到 \(p\) 的时间戳，\(ed_p\) 表示递归完 \(p\) 的时间戳。
对于一个询问 \(x,y\;(st_x < st_y)\)，我们分两种情况讨论：

  1. \([st_y,ed_y] \subseteq [st_x,ed_x]\)：
    这种情况，我们只需要计算 \([st_x,st_y]\) 的贡献即可。
    例如样例的树中，查询 \(1,2\)，区间为 \([1,5]\)，实际有贡献的点为 \(1,3,2\)，恰好是我们想要的。

  2. \([st_x,ed_x] \bigcap [st_y,ed_y] = \emptyset\)：
    这种情况，我们需要计算的是 \([ed_x,st_y]\)。
    但是这样会少掉 \(\text{LCA}\) 的贡献，再加回来。
    例如查询 \(4,2\)，区间为 \([4,5]\)，实际有贡献的点为 \(4,2\)，加上 \(\text{LCA}\) 即 \(3\) 的贡献就好了。

计算贡献时，可以用一个数组记录有贡献的点。
然后添加 / 删除贡献时，异或处理即可。

洛谷上开了 O2 才能过（\(\color{darkblue}{\text{TLE}\ 28458\,\text{ms}} \to \color{green}{\text{AC}\ 9889\,\text{ms}}\)）。

代码： 

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
#include <cstdio>
#include <cmath>
#include <algorithm>
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 = 1e5;
const int M = 1e5;
const int Q = 1e5;
int n,m,q,block;
int v[M + 5],a[N + 5],pos[(N << 1) + 5];
int w[N + 5];
int to[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
int fa[N + 5],dep[N + 5],sz[N + 5],son[N + 5],top[N + 5],st[N + 5],ed[N + 5],dfn[(N << 1) + 5];
void dfs1(int p)
{
    static int tot = 0;
    dfn[st[p] = ++tot] = p,sz[p] = 1;
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ fa[p])
        {
            fa[to[i]] = p,dep[to[i]] = dep[p] + 1,dfs1(to[i]),sz[p] += sz[to[i]];
            if(!son[p] || sz[to[i]] > sz[son[p]])
                son[p] = to[i];
        }
    dfn[ed[p] = ++tot] = p;
}
void dfs2(int p)
{
    if(son[p])
        top[son[p]] = top[p],dfs2(son[p]);
    for(register int i = first[p];i;i = pre[i])
        if(!top[to[i]])
            top[to[i]] = to[i],dfs2(to[i]);
}
inline int getlca(int x,int y)
{
    while(top[x] ^ top[y])
        dep[top[x]] > dep[top[y]] ? x = fa[top[x]] : y = fa[top[y]];
    return dep[x] < dep[y] ? x : y;
}
int chg_tot,qry_tot;
struct s_change
{
    int x,y;
} chg[Q + 5];
struct s_query
{
    int l,r,lca,id,t;
    inline bool operator<(const s_query &o) const
    {
        return pos[l] ^ pos[o.l] ? pos[l] < pos[o.l] : (pos[l] & 1 ? r < o.r : r > o.r);
    }
} qry[Q + 5];
int cnt[M + 5],vis[N + 5];
long long cur,ans[M + 5];
inline void calc(int x)
{
    if(!x)
        return ;
    (vis[x] ^= 1) ? cur += (long long)v[a[x]] * w[++cnt[a[x]]] : cur -= (long long)v[a[x]] * w[cnt[a[x]]--];
}
int main()
{
    read(n),read(m),read(q);
    for(register int i = 1;i <= m;++i)
        read(v[i]);
    for(register int i = 1;i <= n;++i)
        read(w[i]);
    for(register int i = 1;i < n;++i)
    {
        int u,v;
        read(u),read(v),add(u,v),add(v,u);
    }
    dep[1] = 1,top[1] = 1,dfs1(1),dfs2(1);
    for(register int i = 1;i <= n;++i)
        read(a[i]);
    int op,x,y;
    while(q--)
    {
        read(op),read(x),read(y);
        if(!op)
            chg[++chg_tot] = (s_change){x,y};
        else
        {
            int lca = getlca(x,y);
            if(st[x] > st[y])
                swap(x,y);
            if(lca == x || lca == y)
                qry[++qry_tot] = (s_query){st[x],st[y],0,qry_tot,chg_tot};
            else
                qry[++qry_tot] = (s_query){ed[x],st[y],lca,qry_tot,chg_tot};
        }
    }
    chg_tot ? block = pow(n * 2,2.0 / 3) : block = n * 2 / sqrt(m * 2 / 3);
    for(register int i = 1;i <= n * 2;++i)
        pos[i] = (i - 1) / block + 1;
    sort(qry + 1,qry + qry_tot + 1);
    for(register int i = 1,l = 1,r = 0,c = 0;i <= qry_tot;++i)
    {
        while(r < qry[i].r)
            calc(dfn[++r]);
        while(r > qry[i].r)
            calc(dfn[r--]);
        while(l < qry[i].l)
            calc(dfn[l++]);
        while(l > qry[i].l)
            calc(dfn[--l]);
        while(c > qry[i].t)
        {
            if(vis[chg[c].x])
                cur += (long long)w[++cnt[chg[c].y]] * v[chg[c].y] - (long long)w[cnt[a[chg[c].x]]--] * v[a[chg[c].x]];
            swap(chg[c].y,a[chg[c].x]);
            --c;
        }
        while(c < qry[i].t)
        {
            ++c;
            if(vis[chg[c].x])
                cur += (long long)w[++cnt[chg[c].y]] * v[chg[c].y] - (long long)w[cnt[a[chg[c].x]]--] * v[a[chg[c].x]];
            swap(chg[c].y,a[chg[c].x]);
        }
        calc(qry[i].lca),ans[qry[i].id] = cur,calc(qry[i].lca);
    }
    for(register int i = 1;i <= qry_tot;++i)
        printf("%lld\n",ans[i]);
}

Gitalking ...