T1004 a*b problem(HDU 7448)
不会。
T1005 小塔的养成游戏之梦(HDU 7449)
不会。
T1009 强攻计策(HDU 7453)
容易发现初始速度是多少对答案没有影响，所以我们默认初始速度为 \(0\)。题意相当于在平面直角坐标系上（横轴为时间，纵轴为速度），有一个目标高度，维护一条尽量接近目标的直线，但斜率只能是 \(-1/0/1\)，要支持一段区间目标 \(+1\)，求直线下方面积。
将一次区间 \(+1\) 拆成一段后缀 \(+1\) 和一段后缀 \(-1\)。注意到一次后缀 \(+1/-1\) 时至多只有一个位置发生向上/向下翻折，在这个位置前与目标的相对高度 \(-1/+1\)，之后相对高度不变，那么此时面积的变化量容易用这个位置表示，我们现在的任务就是快速找到这个位置。
具体而言，设 \(h_i\) 表示直线在 \(x = i\) 处的相对高度，手玩容易发现当区间 \(+1\) 时，我们要找第一个 \(0/-1\)，区间 \(-1\) 时，我们要找第一个 \(0/1\)。
现在我们要维护一个数据结构，支持区间 \(+1/-1\)，区间找第一个 \(-1/0/1\)，考虑分块，块内维护排序数组，修改时整块打标记，散块归并重构，询问时散块暴力，整块二分即可，平衡块长，时间复杂度 \(O(n \sqrt {n \log n})\)，常数较小。
Code
#include <iostream>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <vector>
using namespace std;
using LL = long long;
const int N = 1e5 + 5;
const int Mod = 1e9 + 7, Inv = (Mod + 1) / 2;
int n, m;
LL ans;
namespace Block {
int len, cnt;
int a[N], b[N], tag[N], bl[N], L[N], R[N];
void build () {
len = sqrt(n) * 0.4;
for (int i = 0; i <= n; ++i) {
bl[i] = i / len + 1;
}
cnt = bl[n];
R[0] = -1;
for (int i = 1; i <= cnt; ++i) {
L[i] = R[i - 1] + 1;
R[i] = min(n, L[i] + len - 1);
}
fill(a, a + n + 1, 0);
iota(b, b + n + 1, 0);
fill(tag, tag + cnt + 1, 0);
}
int first_val (int x, int y) {
for (int i = x; i <= R[bl[x]]; ++i) {
if (a[i] == y - tag[bl[x]]) {
return i;
}
}
for (int i = bl[x] + 1; i <= cnt; ++i) {
if (a[b[R[i]]] < y - tag[i] || a[b[L[i]]] > y - tag[i]) continue;
auto cmp = [&](int i, int j) -> bool {
return a[i] < j;
};
auto it = lower_bound(b + L[i], b + R[i] + 1, y - tag[i], cmp);
if (it != b + R[i] + 1 && a[*it] == y - tag[i]) return *it;
}
return n + 1;
}
int tmpa[N][2];
int al[2];
void add (int l, int r, int x) {
r = min(r, n);
auto rebuild = [&](int l, int r, int gl, int gr) -> void {
al[0] = 0, al[1] = 0;
for (int i = l; i <= r; ++i) {
int o = b[i] >= gl && b[i] <= gr;
tmpa[++al[o]][o] = b[i];
}
int p = l;
auto cmp = [&](int i, int j) -> bool {
return a[i] < a[j] || a[i] == a[j] && i < j;
};
for (int cur[2] = {1, 1}; cur[0] != al[0] + 1 || cur[1] != al[1] + 1; ) {
if (cur[0] != al[0] + 1 && (cur[1] == al[1] + 1 || cmp(tmpa[cur[0]][0], tmpa[cur[1]][1]))) {
b[p++] = tmpa[cur[0]][0], ++cur[0];
}
else {
b[p++] = tmpa[cur[1]][1], ++cur[1];
}
}
};
if (bl[l] == bl[r]) {
for (int i = l; i <= r; ++i) {
a[i] += x;
}
rebuild(L[bl[l]], R[bl[l]], l, r);
}
else {
for (int i = l; i <= R[bl[l]]; ++i) {
a[i] += x;
}
for (int i = L[bl[r]]; i <= r; ++i) {
a[i] += x;
}
rebuild(L[bl[l]], R[bl[l]], l, R[bl[l]]);
rebuild(L[bl[r]], R[bl[r]], L[bl[r]], r);
for (int i = bl[l] + 1; i <= bl[r] - 1; ++i) {
tag[i] += x;
}
}
}
}
void suf_add (int x) {
int pos = min(Block::first_val(x, 0), Block::first_val(x, 1));
ans += max(0, (n - pos) * 2 - 1);
Block::add(x, pos, -1);
}
void suf_minus (int x) {
int pos = min(Block::first_val(x, 0), Block::first_val(x, -1));
ans -= max(0, (n - pos) * 2 - 1);
Block::add(x, pos, 1);
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T;
cin >> T;
while (T--) {
cin >> n >> m;
Block::build(), ans = 0;
for (int i = 1, l, r; i <= m; ++i) {
cin >> l >> r;
suf_add(l), suf_minus(r);
cout << ans % Mod * Inv % Mod << '\n';
}
}
return 0;
}
T1012 图计算(HDU 7456)
考虑对于每一张图分别维护并查集，我们使用启发式合并，这样可以保证每个结点的 \(fa\) 就是它的最高级祖先，对于每一个结点，为它在所有图中的 \(fa\) 序列哈希即可。
Code
#include <iostream>
#include <vector>
#include <tuple>
#include <unordered_map>
using namespace std;
using LL = long long;
using Tp = tuple<int, int, int>;
const int N = 5e4 + 5, M = 105;
int n, m, d, q;
struct Hash_Arr {
int len;
struct Hash {
int mod, base, len;
int pw[M], now;
void init (int mod_, int base_, int len_) {
mod = mod_, base = base_, now = 0, len = len_;
pw[0] = 1;
for (int i = 1; i <= len; ++i) {
pw[i] = 1ll * pw[i - 1] * base % mod;
}
}
void add (int x, int y) { now = (now + 1ll * (mod + y) * pw[x]) % mod; }
} ha[3];
void init (int len_) {
len = len_;
ha[0].init(1000000007, 1000000009, len);
ha[1].init(1000000021, 1000000033, len);
ha[2].init(1000000087, 1000000093, len);
}
void add (int x, int y) {
ha[0].add(x, y);
ha[1].add(x, y);
ha[2].add(x, y);
}
Tp get_val () { return make_tuple(ha[0].now, ha[1].now, ha[2].now); }
} h[N];
struct tHash {
const int tB = 998244353, tP = tB * tB;
int operator() (Tp x) const {
return get<0>(x) + get<1>(x) * tB * get<2>(x) * tP;
}
};
unordered_map<Tp, int, tHash> p;
LL ans;
void add (Tp x) {
int v = p[x]++;
ans += v;
}
void remove (Tp x) {
int v = --p[x];
ans -= v;
}
struct U {
int fa[N], id;
vector<int> vec[N];
void init (int id_) {
id = id_;
fill(vec + 1, vec + n + 1, vector<int>());
for (int i = 1; i <= n; ++i) {
vec[i].push_back(i);
fa[i] = i;
h[i].add(id, i);
}
}
void unite (int x, int y) {
x = fa[x], y = fa[y];
if (x == y) return;
if (vec[x].size() < vec[y].size()) swap(x, y);
for (auto v : vec[y]) {
vec[x].push_back(v);
remove(h[v].get_val());
h[v].add(id, x - fa[v]);
add(h[v].get_val());
fa[v] = x;
}
vec[y].clear();
}
} uf[M];
int main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T;
cin >> T;
while (T--) {
cin >> n >> m >> d >> q;
for (int i = 1; i <= n; ++i) {
h[i].init(d + 1);
}
for (int i = 1; i <= d + 1; ++i) {
uf[i].init(i);
}
p.clear(), ans = 0;
for (int i = 1; i <= n; ++i) {
add(h[i].get_val());
}
for (int i = 1, u, v; i <= m; ++i) {
cin >> u >> v;
for (int j = 1; j <= d + 1; ++j) {
uf[j].unite(u, v);
}
}
for (int i = 1, u, v, w; i <= q; ++i) {
cin >> u >> v >> w;
uf[w].unite(u, v);
cout << ans << '\n';
}
}
return 0;
}