洛谷 5314 「Ynoi 2011」ODT

发表于 | 分类于 |

以前没卡过去，今天突发奇想重新交了一下就过了（
\(O(n \log^2 n)\) 过百万实锤（

不难想到链分治，对每个点开一棵平衡树维护轻儿子，不难发现轻儿子的个数和应当是 \(O(n \log n)\) 级别的。
修改可以直接暴力树剖 \(O(\log^2 n)\) 草，查询是大常数 \(O(\log n)\)。

建议用 Treap。

代码： 

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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
#include <vector>
#include <cstdio>
#include <cstdlib>
#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);
}

const int N = 1e6;
int n,m,a[N + 5];
vector<int> e[N + 5];
namespace BIT
{
    int c[N + 5];
    #define lowbit(x) ((x) & -(x))
    inline void update(int x,int k)
    {
        for(;x <= n;x += lowbit(x))
            c[x] += k;
    }
    inline int query(int x)
    {
        int ret = 0;
        for(;x;x -= lowbit(x))
            ret += c[x];
        return ret;
    }
};
namespace Treap
{
    int val[N + 5],cnt[N + 5],rnd[N + 5],sz[N + 5],ch[N + 5][2];
    int rt[N + 5],st[N + 5],top;
    inline void push(int p)
    {
        sz[p] = sz[ch[p][0]] + cnt[p] + sz[ch[p][1]];
    }
    inline void rotate(int &p,int d)
    {
        int q = ch[p][d ^ 1];
        ch[p][d ^ 1] = ch[q][d],ch[q][d] = p;
        push(p),push(p = q);
    }
    inline int new_node(int v)
    {
        static int tot = 0;
        int p = top ? st[top--] : ++tot;
        val[p] = v,cnt[p] = sz[p] = 1,rnd[p] = rand(),ch[p][0] = ch[p][1] = 0;
        return p;
    }
    void insert(int &p,int v)
    {
        if(!p)
        {
            p = new_node(v);
            return ;
        }
        ++sz[p];
        if(val[p] == v)
        {
            ++cnt[p];
            return ;
        }
        int d = v > val[p];
        insert(ch[p][d],v),rnd[p] < rnd[ch[p][d]] && (rotate(p,d ^ 1),1),push(p);
    }
    void remove(int &p,int v)
    {
        if(!p)
            return ;
        if(v < val[p])
            remove(ch[p][0],v);
        else if(v > val[p])
            remove(ch[p][1],v);
        else if(!ch[p][0] && !ch[p][1])
            !(--cnt[p],--sz[p]) && (st[++top] = p,p = 0);
        else if(ch[p][0] && !ch[p][1])
            rotate(p,1),remove(ch[p][1],v);
        else if(!ch[p][0] && ch[p][1])
            rotate(p,0),remove(ch[p][0],v);
        else
        {
            int d = rnd[ch[p][0]] > rnd[ch[p][1]];
            rotate(p,d),remove(ch[p][d],v);
        }
        push(p);
    }
    int kth(int p,int k)
    {
        if(!p)
            return 0;
        if(k <= sz[ch[p][0]])
            return kth(ch[p][0],k);
        else if(k > cnt[p] + sz[ch[p][0]])
            return kth(ch[p][1],k - cnt[p] - sz[ch[p][0]]);
        return val[p];
    }
};
namespace HLD
{
    int fa[N + 5],dep[N + 5],sz[N + 5],son[N + 5],top[N + 5],id[N + 5];
    void dfs1(int p)
    {
        sz[p] = 1;
        for(register vector<int>::iterator v = e[p].begin();v != e[p].end();++v)
            if(*v ^ fa[p])
            {
                fa[*v] = p,dep[*v] = dep[p] + 1,dfs1(*v),sz[p] += sz[*v];
                if(!son[p] || sz[son[p]] < sz[*v])
                    son[p] = *v;
            }
    }
    void dfs2(int p)
    {
        static int tot = 0;
        id[p] = ++tot;
        if(son[p])
            top[son[p]] = top[p],dfs2(son[p]);
        for(register vector<int>::iterator v = e[p].begin();v != e[p].end();++v)
            if(!id[*v])
                Treap::insert(Treap::rt[p],a[*v]),top[*v] = *v,dfs2(*v);
    }
    void update(int x,int y,int k)
    {
        while(top[x] ^ top[y])
            if(dep[top[x]] > dep[top[y]])
            {
                Treap::remove(Treap::rt[fa[top[x]]],a[top[x]]);
                BIT::update(id[top[x]],k),BIT::update(id[x] + 1,-k),a[top[x]] += k;
                Treap::insert(Treap::rt[fa[top[x]]],a[top[x]]);
                x = fa[top[x]];
            }
            else
            {
                Treap::remove(Treap::rt[fa[top[y]]],a[top[y]]);
                BIT::update(id[top[y]],k),BIT::update(id[y] + 1,-k),a[top[y]] += k;
                Treap::insert(Treap::rt[fa[top[y]]],a[top[y]]);
                y = fa[top[y]];
            }
        if(dep[x] > dep[y])
            swap(x,y);
        if(top[x] == x && (x ^ 1))
            Treap::remove(Treap::rt[fa[x]],a[x]),a[x] += k,Treap::insert(Treap::rt[fa[x]],a[x]);
        BIT::update(id[x],k),BIT::update(id[y] + 1,-k);
    }
    int query(int x,int k)
    {
        static int buf[10];
        int tot = 0;
        k <= Treap::sz[Treap::rt[x]] && (buf[++tot] = Treap::kth(Treap::rt[x],k));
        k > 1 && k - 1 <= Treap::sz[Treap::rt[x]] && (buf[++tot] = Treap::kth(Treap::rt[x],k - 1));
        k > 2 && k - 2 <= Treap::sz[Treap::rt[x]] && (buf[++tot] = Treap::kth(Treap::rt[x],k - 2));
        k > 3 && k - 3 <= Treap::sz[Treap::rt[x]] && (buf[++tot] = Treap::kth(Treap::rt[x],k - 3));
        buf[++tot] = BIT::query(id[x]);
        fa[x] && (buf[++tot] = BIT::query(id[fa[x]]));
        son[x] && (buf[++tot] = BIT::query(id[son[x]]));
        sort(buf + 1,buf + tot + 1);
        return buf[min(k,4)];
    }
};
int main()
{
    srand(20070921),read(n),read(m);
    for(register int i = 1;i <= n;++i)
        read(a[i]);
    int u,v;
    for(register int i = 1;i < n;++i)
        read(u),read(v),e[u].push_back(v),e[v].push_back(u);
    HLD::dep[1] = HLD::top[1] = 1,HLD::dfs1(1),HLD::dfs2(1);
    for(register int i = 1;i <= n;++i)
        BIT::update(HLD::id[i],a[i]),BIT::update(HLD::id[i] + 1,-a[i]);
    for(int op,x,y,z;m;--m)
    {
        read(op),read(x),read(y);
        if(op == 1)
            read(z),HLD::update(x,y,z);
        else
            printf("%d\n",HLD::query(x,y));
    }
}

Gitalking ...