题意: n个点m条边的无向图, 边上带两种权a, b, q个询问, 某两点之间是否存在一条简单或非简单路径, 使路径上a的最大值为max_a, b的最大值为max_b. (1 ≤ n, q ≤ 5*10^4, 1 ≤ m ≤ 10^5, 0 ≤ a, b ≤ 10^9) 这道题写得我好辛苦嘤嘤嘤 QAQ
去年此题获得0分. 据说是分块 + 并查集, 最近在练分块, 就去写一写, 好大一个坑.
先讲我的做法.
暴力怎么做呢? 只加入边权不超过max_a, max_b的边, 用并查集维护连通块, 再检查等号能否取到. 由于是暴力, 检查可以一条边一条边地试, 看看u, v是否和它相连.
每次都从头加边太暴力了, 可不可以在先前的基础上加呢? 由于有两维, 直接排序是不行的 (以a为第一关键字, 则不能保证b不减). 一种思路是对一维排序 (比如a), 枚举最大值, 维护a满足限制的那些边形成的连通块. 把询问离线, 也按a排序. 需要支持查询b≤b_max的边所形成的连通块. 我们维护一个 "前缀和". 每个位置维护一个空间会爆, 更新的代价也太大. 维护得太少查询的代价太大. 是时候分块了.
将边按b排序, 分成
不好搞, 其实直接将零碎的边加入即可. 但是怎么还原呢? 我的策略是这样的: 设整块的并查集为s, 另开一个并查集t. s中的点向t中对应点连一条虚边 (概念上的, 不用真的连). 于是, 合并操作均在t中进行. 用一个数组记录t中哪些点被修改过 (用一个布尔数组判重以减小常数), 最后还原即可. s, t中分别进行路径压缩.
检查等号能否取到用带权并查集实现.
更新的话, 在至多
先WA了一次, 上网查了一下, 发现是a, b初始化的问题. 0也是有效值, 所以得用-1初始化.
然后开始TLE.
我在OJ上提交千百遍, 却卡不进那时限~
自己测了一些随机数据......见鬼, 明明跑得快于许多题解, 怎么我就T掉了? 其实按照原题, 应该是都T掉了......原题不开-O2, 每组数据4s, 除了一份代码, 其余都跑了6s+, 包括我.
并查集加上按秩合并, 调整块的大小, fread, 均无济于事.
不服气 QAQ 重写了一遍. 原来是用指针写的并查集 (因为想少传几个参数), 改成了数组+struct. 优化了一些小细节, 快了一些, 交到BZOJ上仍然超时.
想起去年在群里传了数据......测了一下, 40s绰绰有余啊, 虽然有些单个点可能超时. 据说BZOJ还开了-O2呢. 在一个群里问了一下, VW神犇一语惊醒梦中人: 你的电脑太高级了......QAQ
还没调块的大小呢. 面向数据, 改成一块
cmath里的sqrt好慢, 不如自行枚举.
事实上我的算法时间复杂度为
用Claris的代码交了一遍, 跑的比我自己的快10s+......自己的代码应该排在rank 213, 很符合我.
这个算法启发我们, 对于二维的问题, 可以枚举一个维度, 另一个维度用数据结构等维护.
上面的算法对每一块开一个并查集, 而在大数组上寻址是很慢的.
按b对边和询问分块. 但是我们不再维护 "前缀和", 而是对于块i, 将块0~i-1中的边按a排序, b_max落在块i中的询问也按a排序, 暴力加边, 对于询问中包含的落在块i中的边, 先加, 再撤销.
设块的大小为s, 则时间复杂度为
支持撤销的方法是记录每一步合并操作. 可以记录所有修改, 也可以记录哪些点被改动过以及先前的值.
是不是有点像莫队呢?
这个算法启发我们, 当满足某种关系的询问之间能转移时, 可以考虑分块, 将其组合成一个前缀 + 零碎部分. 前缀是可以公用的, 需要能在线性左右的时间内计算.
以下是我的代码, 算法一不带fread的版本.
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N = 5e4, MAX_M = 1e5, SIZE = 548, BLOCK = MAX_M/SIZE + 1;
int sz, blk, n, m, e[2][MAX_M], o[MAX_N];
struct Edge {
int u, v, a, b, k;
} E[MAX_M+1], Q[MAX_N];
typedef Edge Query;
inline bool cmp_a(int i, int j) { return E[i].a < E[j].a; }
inline bool cmp_b(int i, int j) { return E[i].b < E[j].b; }
inline bool cmp_q(int i, int j) { return Q[i].a < Q[j].a; }
struct Node {
int p, r, a, b;
Node(): p(-1), r(0), a(-1), b(-1) {}
};
struct Set {
Node x[MAX_N];
int get(int i)
{
return x[i].p == -1 ? i : x[i].p = get(x[i].p);
}
void merge(int u, int v, int a, int b, int& ru, int& rv)
{
ru = get(u);
rv = get(v);
if (x[rv].r > x[ru].r)
swap(ru, rv);
x[ru].a = max(x[ru].a, max(x[rv].a, a));
x[ru].b = max(x[ru].b, max(x[rv].b, b));
x[ru].r += ru != rv && x[ru].r == x[rv].r;
x[rv].p = ru != rv ? ru : -1;
}
void merge(int u, int v, int a, int b)
{
int ru, rv;
merge(u, v, a, b, ru, rv);
}
} S[BLOCK], t;
inline void init()
{
while (sz*sz < m*3)
++sz;
blk = (m+sz-1)/sz;
}
inline void update(const Edge& f)
{
for (int i = f.k/sz; i < blk; ++i)
S[i].merge(f.u, f.v, f.a, f.b);
}
bool query(int u, int v, int a, int b)
{
E[m].b = b;
int id = upper_bound(e[1], e[1]+m, m, cmp_b) - e[1] - 1;
if (id == -1 || E[e[1][id]].b != b)
return false;
int num = id/sz, top = 0, r1, r2;
bool ok = false;
static int used[MAX_N];
static bool mark[MAX_N];
if (num) {
Set& s = S[num-1];
for (int i = num*sz; i <= id; ++i) {
const Edge& f = E[e[1][i]];
if (f.a <= a) {
int ru = s.get(f.u), rv = s.get(f.v), ma = max(s.x[ru].a, s.x[rv].a), mb = max(s.x[ru].b, s.x[rv].b);
t.merge(ru, rv, max(f.a, ma), max(f.b, mb), ru, rv);
mark[ru] ? 0 : mark[used[top++] = ru] = true;
mark[rv] ? 0 : mark[used[top++] = rv] = true;
}
}
int ru = s.get(u), rv = s.get(v);
r1 = t.get(ru);
r2 = t.get(rv);
ok = r1 == r2 && max(t.x[r1].a, s.x[ru].a) == a && max(t.x[r1].b, s.x[ru].b) == b;
} else {
for (int i = 0; i <= id; ++i) {
const Edge& f = E[e[1][i]];
if (f.a <= a) {
int ru, rv;
t.merge(f.u, f.v, f.a, f.b, ru, rv);
mark[ru] ? 0 : mark[used[top++] = ru] = true;
mark[rv] ? 0 : mark[used[top++] = rv] = true;
}
}
r1 = t.get(u);
r2 = t.get(v);
ok = r1 == r2 && t.x[r1].a == a && t.x[r1].b == b;
}
while (top--) {
int o = used[top];
mark[o] = false;
t.x[o] = Node();
}
return ok;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i) {
scanf("%d%d%d%d", &E[i].u, &E[i].v, &E[i].a, &E[i].b);
--E[i].u;
--E[i].v;
e[0][i] = e[1][i] = i;
}
sort(e[0], e[0]+m, cmp_a);
sort(e[1], e[1]+m, cmp_b);
for (int i = 0; i < m; ++i)
E[e[1][i]].k = i;
int q;
scanf("%d", &q);
for (int i = 0; i < q; ++i) {
scanf("%d%d%d%d", &Q[i].u, &Q[i].v, &Q[i].a, &Q[i].b);
--Q[i].u;
--Q[i].v;
o[i] = i;
}
sort(o, o+q, cmp_q);
init();
for (int i = 0, j = 0; i < q; ++i) {
Query& qr = Q[o[i]];
while (j < m && E[e[0][j]].a <= qr.a)
update(E[e[0][j++]]);
qr.k = j && E[e[0][j-1]].a == qr.a && query(qr.u, qr.v, qr.a, qr.b);
}
for (int i = 0; i < q; ++i)
puts(Q[i].k ? "Yes" : "No");
return 0;
}
以下还是我的代码, 算法二. 跑得比算法一带fread快, 然而比Claris爷等人慢......你们这些自带小常数的人 QAQ
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N = 5e4, MAX_M = 1e5;
struct Edge {
int u, v, a, b, k;
} E[MAX_M], Q[MAX_N];
typedef Edge Query;
struct Node {
int p, r, a, b;
Node(): p(-1), r(0), a(-1), b(-1) {};
} x[MAX_N], t[MAX_N];
int sz = 1, blk, n, m, q, now, o[MAX_N];
int used[MAX_N], top;
bool mark[MAX_N], ans[MAX_N];
inline bool cmp_b(const Edge& i, const Edge& j) { return i.b < j.b; }
inline bool cmp_a(int i, int j) { return E[i].a < E[j].a; }
inline bool cmp_q(int i, int j) { return Q[i].k < Q[j].k || Q[i].k == Q[j].k && Q[i].a < Q[j].a; }
int get(int i)
{
return x[i].p == -1 ? i : get(x[i].p);
}
void merge(int u, int v, int a, int b, bool c=true)
{
int ru = get(u), rv = get(v);
if (c && !mark[ru]) {
mark[ru] = true;
t[ru] = x[ru];
used[top++] = ru;
}
if (c && !mark[rv]) {
mark[rv] = true;
t[rv] = x[rv];
used[top++] = rv;
}
if (x[rv].r > x[ru].r)
swap(ru, rv);
x[ru].a = max(a, max(x[ru].a, x[rv].a));
x[ru].b = max(b, max(x[ru].b, x[rv].b));
x[ru].r += ru != rv && x[ru].r == x[rv].r;
x[rv].p = ru != rv ? ru : -1;
}
inline void retrace()
{
while (top) {
int v = used[--top];
mark[v] = false;
x[v] = t[v];
}
}
inline void init()
{
int tmp = 1;
while ((1<<tmp) < m)
++tmp;
tmp *= m;
while (sz*sz < tmp)
++sz;
blk = (m+sz-1)/sz;
}
void process(int num)
{
int st = num*sz, ed = min(st + sz, m), j = 0;
static int e[MAX_M];
for (int i = 0; i < st; ++i)
e[i] = i;
sort(e, e+st, cmp_a);
while (now < q && Q[o[now]].k == num) {
const Query& qr = Q[o[now]];
while (j < st && E[e[j]].a <= qr.a) {
const Edge& f = E[e[j++]];
merge(f.u, f.v, f.a, f.b, false);
}
for (int i = st; i < ed && E[i].b <= qr.b; ++i) {
const Edge& f = E[i];
if (f.a <= qr.a)
merge(f.u, f.v, f.a, f.b);
}
int ru = get(qr.u), rv = get(qr.v);
ans[o[now]] = ru == rv && x[ru].a == qr.a && x[ru].b == qr.b;
retrace();
++now;
}
for (int i = 0; i < n; ++i)
x[i] = Node();
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i) {
scanf("%d%d%d%d", &E[i].u, &E[i].v, &E[i].a, &E[i].b);
--E[i].u;
--E[i].v;
}
sort(E, E+m, cmp_b);
init();
scanf("%d", &q);
for (int i = 0; i < q; ++i) {
scanf("%d%d%d%d", &Q[i].u, &Q[i].v, &Q[i].a, &Q[i].b);
--Q[i].u;
--Q[i].v;
o[i] = i;
Q[i].k = upper_bound(E, E+m, (Edge){0, 0, 0, Q[i].b, 0}, cmp_b) - E - 1;
if (Q[i].k == -1 || E[Q[i].k].b != Q[i].b)
Q[i].k = -1;
else
Q[i].k /= sz;
}
sort(o, o+q, cmp_q);
while (now < q && Q[o[now]].k == -1)
++now;
for (int i = 0; i < blk; ++i)
if (now < q && Q[o[now]].k == i)
process(i);
for (int i = 0; i < q; ++i)
puts(ans[i] ? "Yes" : "No");
return 0;
}