LibreOJ 2113 「HNOI2015」接水果

发表于 | 分类于 | 13

按照套路，可以用 DFS 序把问题转化成询问覆盖一个点的所有矩形中的第 k 小权值。
这个别人都讲烂了。

然后，就可以用数据结构维护辣！
但是为什么大家都写了整体二分……

我永远喜欢树套树！
于是我选择了用树套树维护扫描线。
但是这样子卡不过去。

我用了一些卡常的技巧： - 读入优化。 - 权值离散化，单次操作从 O(lognlogc) 降到了 O(lognlogp)。 - 发现我们不用每个矩形都存两个（旋转 90∘），而是保证所有坐标点 (x,y) 都满足 x≤y，这样就只用存一个矩形。

于是这样子就能通过了。

代码： 

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
#include <cstdio>
#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;
    while(ch < '0' || ch > '9')
        w |= ch == '-',ch = gc();
    while(ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc();
    w ? x = -x : x;
}

const int N = 4e4;
const int LG = 16;
const int C = 1e9;
int n,p,q;
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 id[N + 5],sz[N + 5],dep[N + 5],f[N + 5][LG + 5];
void dfs(int p)
{
    static int tot = 0;
    sz[p] = 1,id[p] = ++tot;
    for(register int i = 1;i <= LG;++i)
        f[p][i] = f[f[p][i - 1]][i - 1];
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ f[p][0])
            f[to[i]][0] = p,dep[to[i]] = dep[p] + 1,dfs(to[i]),sz[p] += sz[to[i]];
}
struct segnode
{
    int sum,tag;
    int ls,rs;
} seg[N * 770 + 10];
struct node
{
    int rt;
    int ls,rs;
} tree[N * 40 + 10];
int rt;
void update(int l,int r,int k,int &p,int tl,int tr)
{
    static int tot = 0;
    if(!p)
        p = ++tot;
    seg[p].sum += k * (min(r,tr) - max(l,tl) + 1);
    if(l <= tl && tr <= r)
    {
        seg[p].tag += k;
        return ;
    }
    int mid = tl + tr >> 1;
    l <= mid && (update(l,r,k,seg[p].ls,tl,mid),1);
    r > mid && (update(l,r,k,seg[p].rs,mid + 1,tr),1);
}
int query(int x,int p,int tl,int tr)
{
    if(!p || tl == tr)
        return seg[p].sum;
    int mid = tl + tr >> 1;
    return seg[p].tag + (x <= mid ? query(x,seg[p].ls,tl,mid) : query(x,seg[p].rs,mid + 1,tr));
}
void insert(int l,int r,int x,int k,int &p,int tl,int tr)
{
    static int tot = 0;
    if(!p)
        p = ++tot;
    update(l,r,k,tree[p].rt,1,n);
    if(tl == tr)
        return ;
    int mid = tl + tr >> 1;
    x <= mid ? insert(l,r,x,k,tree[p].ls,tl,mid) : insert(l,r,x,k,tree[p].rs,mid + 1,tr);
}
int query(int x,int k,int p,int tl,int tr)
{
    if(!p || tl == tr)
        return tl;
    int mid = tl + tr >> 1;
    int cnt = query(x,tree[tree[p].ls].rt,1,n);
    return k <= cnt ? query(x,k,tree[p].ls,tl,mid) : query(x,k - cnt,tree[p].rs,mid + 1,tr);
}
struct edge
{
    int x,y1,y2,w,k,id;
    inline bool operator<(const edge &o) const
    {
        return x < o.x || (x == o.x && k > o.k);
    }
} e[N * 9 + 10];
int tot;
int ans[N + 5];
int ind[N + 5],len;
int main()
{
    read(n),read(p),read(q);
    int u,v;
    for(register int i = 1;i < n;++i)
        read(u),read(v),add(u,v),add(v,u);
    dep[1] = 1,dfs(1);
    int a,b,c;
    for(register int i = 1;i <= p;++i)
    {
        read(a),read(b),read(c),ind[i] = c;
        if((id[a] <= id[b] && id[b] < id[a] + sz[a]) || (id[b] <= id[a] && id[a] < id[b] + sz[b]))
        {
            if(dep[a] > dep[b])
                swap(a,b);
            int t = b;
            for(register int j = LG;~j && dep[t] - dep[a] > 1;--j)
                if(f[t][j] && dep[f[t][j]] > dep[a])
                    t = f[t][j];
            if(id[t] > 1)
            {
                e[++tot] = (edge){1,id[b],id[b] + sz[b] - 1,c,1,0};
                e[++tot] = (edge){id[t] - 1,id[b],id[b] + sz[b] - 1,c,-1,0};
            }
            if(id[t] + sz[t] <= n)
            {
                e[++tot] = (edge){id[b],id[t] + sz[t],n,c,1,0};
                e[++tot] = (edge){id[b] + sz[b] - 1,id[t] + sz[t],n,c,-1,0};
            }
        }
        else
        {
            if(id[a] > id[b])
                swap(a,b);
            e[++tot] = (edge){id[a],id[b],id[b] + sz[b] - 1,c,1,0};
            e[++tot] = (edge){id[a] + sz[a] - 1,id[b],id[b] + sz[b] - 1,c,-1,0};
        }
    }
    sort(ind + 1,ind + p + 1),len = unique(ind + 1,ind + p + 1) - ind - 1;
    for(register int i = 1;i <= q;++i)
    {
        read(a),read(b),read(c);
        if(id[a] > id[b])
            swap(a,b);
        e[++tot] = (edge){id[a],id[b],0,c,0,i};
    }
    sort(e + 1,e + tot + 1);
    for(register int i = 1;i <= tot;++i)
    {
        if(!e[i].k)
            ans[e[i].id] = ind[query(e[i].y1,e[i].w,rt,1,len)];
        else
            insert(e[i].y1,e[i].y2,lower_bound(ind + 1,ind + len + 1,e[i].w) - ind,e[i].k,rt,1,len);
    }
    for(register int i = 1;i <= q;++i)
        printf("%d\n",ans[i]);
}

0 comments
Anonymous
Markdown is supported

Be the first person to leave a comment!