LibreOJ 2865 「IOI2018」狼人

发表于 | 分类于 | 10

为什么用了交互但是不强制在线啊？？？
在线算法玩家表示不爽。

这题算是个变种的 Kruskal 重构树。
主要改变在于并没有给出边权，而是通过点的编号来重构。

此题即在经过点的编号在某个限制下，求两个点各自的连通块的交集是否为空。
所以前半部分很容易想到 Kruskal 重构树。

上面已经说了是要按照点的编号来重构树，具体过程为：

  1. 把边按照编号较大的点排序。
  2. 做 Kruskal 过程，同时重构一棵树。
  3. 重构出来的树满足每一个非根结点的编号小于父节点的编号。

然后重构出另一棵与之对应的树。

于是询问就是分别在两棵重构出来的树上找到点的编号 ∈[0,R] 和 [L,N) 的两棵子树。
因为众所周知 Kruskal 重构树具有单调性，所以树上倍增。

然后众所周知 Kruskal 重构树的一棵子树对应一个连通块，所以相当于求两棵子树的交集。
子树？DFS 序！于是 DFS 序后主席树维护即可。
具体地说，设 id1,i,id2,i 分别表示点 i 在两棵树上的 DFS 序，
那么对于每个 i，就是一个矩阵上坐标为 (id1,i,id2,i) 的点。
问题就变成了一个子矩阵里的点数。
灰常经典，而且是静态的。

代码： 

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
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include "werewolf.h"
#define ls(p) seg[p].lson
#define rs(p) seg[p].rson
using namespace std;
const int N = 2e5;
const int M = 4e5;
const int LG = 20;
int n,m,q;
int fa[N + 5];
inline int get(int x)
{
    return fa[x] == x ? x : fa[x] = get(fa[x]);
}
struct kruskal
{
    int to[N + 5],pre[N + 5],first[N + 5];
    int edge_tot;
    inline void add(int u,int v)
    {
        int &tot = edge_tot;
        to[++tot] = v;
        pre[tot] = first[u];
        first[u] = tot;
    }
    int id[N + 5],rk[N + 5],sz[N + 5],f[N + 5][LG + 5];
    int dfn_tot;
    void dfs(int p)
    {
        rk[id[p] = ++dfn_tot] = p;
        sz[p] = 1;
        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;
                dfs(to[i]);
                sz[p] += sz[to[i]];
            }
    }
} LSS,GTR;
struct edge
{
    int u,v;
    inline bool operator<(const edge &o) const
    {
        return u < o.u;
    }
    inline bool operator>(const edge &o) const
    {
        return u > o.u;
    }
} e[M + 5];
struct segnode
{
    int sum,lson,rson;
} seg[(N << 7) + 10];
void insert(int x,int k,int &p,int tl,int tr)
{
    static int tot = 0;
    seg[++tot] = seg[p],p = tot;
    seg[p].sum += k;
    if(tl == tr)
        return ;
    int mid = tl + tr >> 1;
    if(x <= mid)
        insert(x,k,ls(p),tl,mid);
    else
        insert(x,k,rs(p),mid + 1,tr);
}
int query(int l,int r,int p,int tl,int tr)
{
    if(!p || (l <= tl && tr <= r))
        return seg[p].sum;
    int mid = tl + tr >> 1;
    int ret = 0;
    if(l <= mid)
        ret += query(l,r,ls(p),tl,mid);
    if(r > mid)
        ret += query(l,r,rs(p),mid + 1,tr);
    return ret;
}
int rt[N + 5];
vector<int> check_validity(int n,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R)
{
    m = X.size();
    q = S.size();
    for(register int i = 1;i <= m;++i)
    {
        e[i].u = ++X[i - 1],e[i].v = ++Y[i - 1];
        if(e[i].u > e[i].v)
            swap(e[i].u,e[i].v);
    }
    for(register int i = 1;i <= n;++i)
        fa[i] = i;
    sort(e + 1,e + m + 1,greater<edge>());
    for(register int i = 1;i <= m;++i)
    {
        int fu = get(e[i].u),fv = get(e[i].v);
        if(fu ^ fv)
        {
            LSS.add(fu,fv);
            fa[fv] = fu;
        }
    }
    for(register int i = 1;i <= n;++i)
        if(fa[i] == i)
            LSS.dfs(i);
    for(register int i = 1;i <= m;++i)
        swap(e[i].u,e[i].v);
    for(register int i = 1;i <= n;++i)
        fa[i] = i;
    sort(e + 1,e + m + 1);
    for(register int i = 1;i <= m;++i)
    {
        int fu = get(e[i].u),fv = get(e[i].v);
        if(fu ^ fv)
        {
            GTR.add(fu,fv);
            fa[fv] = fu;
        }
    }
    for(register int i = 1;i <= n;++i)
        if(fa[i] == i)
            GTR.dfs(i);
    for(register int i = 1;i <= n;++i)
        insert(GTR.id[LSS.rk[i]],1,rt[i] = rt[i - 1],1,n);
    int s,t,x,y;
    vector<int> ret;
    for(register int i = 0;i < q;++i)
    {
        s = ++S[i],t = ++E[i],x = ++L[i],y = ++R[i];
        for(register int i = LG;~i;--i)
            if(LSS.f[s][i] && LSS.f[s][i] >= x)
                s = LSS.f[s][i];
        for(register int i = LG;~i;--i)
            if(GTR.f[t][i] && GTR.f[t][i] <= y)
                t = GTR.f[t][i];
        ret.push_back((bool)(query(GTR.id[t],GTR.id[t] + GTR.sz[t] - 1,rt[LSS.id[s] + LSS.sz[s] - 1],1,n) - query(GTR.id[t],GTR.id[t] + GTR.sz[t] - 1,rt[LSS.id[s] - 1],1,n)));
    }
    return ret;
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment