2024.7.8

2024.7.8 【追逐影子的人，自己就是影子 —— 荷马】

Monday 六月初三

---

讲的根本听不懂好吧！

目前只写了三道题（但是黑色

确实是没见过这么抽象的数据结构

Gregor and the Two Painters
Number of Components
Equal LCM Subsets

这个lcm确实让我印象深刻，

第一次把一个数学+数据结构写成这样

//2024.7.8
//by wite_ice
//Equal LCM Subsets
#include <bits/stdc++.h>
using namespace std;
const int N = 1001;
typedef pair<int, int> p;
typedef __int128 ll;int T, n, m;
int c[2], sz[2];
ll a[2][N], d[2][N];inline ll read(){ll ans = 0;char ch = getchar();while (ch < '0' || ch > '9')ch = getchar();while (ch >= '0' && ch <= '9'){ans = ans * 10 + (ch ^ 48);ch = getchar();}return ans;
}void write(ll n){if (n >= 10) write(n / 10);putchar(n % 10 + '0');}struct tree{ll s[N * 4], sum;void build(int x, int l, int r, ll a[]) {if(l == r) {s[x] = sum / __gcd(sum, a[l]);return ;}int mid = (l + r) >> 1;build(x << 1, l, mid, a);build(x << 1 | 1, mid + 1, r, a);s[x] = __gcd(s[x << 1], s[x << 1 | 1]);}void change(int x, int l, int r, int p) {if(l == r) {s[x] = 0;return ;}int mid = (l + r) >> 1;if(p <= mid) change(x << 1, l, mid, p);else change(x << 1 | 1, mid + 1, r, p);s[x] = __gcd(s[x << 1], s[x << 1 | 1]);}ll work() {return s[1];}
}t[2][N];int main() {cin >> T;while(T--) {cin >> n >> m;for(int i = 1; i <= n; ++i)a[0][i] = read(), d[0][i] = 0;for(int i = 1; i <= m; ++i)a[1][i] = read(), d[1][i] = 0;c[0] = c[1] = 0, sz[0] = n, sz[1] = m;queue <p> q;for(int k = 0; k <= 1; ++k) for(int i = 1; i <= sz[k]; ++i) {t[k][i].sum = a[k][i], t[k][i].build(1, 1, sz[k ^ 1], a[k ^ 1]);if(t[k][i].work() > 1) q.push({k, i}), d[k][i] = 1, ++c[k];}while(q.size()) {p x = q.front(); q.pop();int f = (x.first) ^ 1;for(int i = 1; i <= sz[f]; ++i) {if(!d[f][i]) {t[f][i].change(1, 1, sz[f ^ 1], x.second);if(t[f][i].work() > 1) q.push({f, i}), d[f][i] = 1, ++c[f];}}}if(c[0] == sz[0] || c[1] == sz[1]) cout << "NO" << endl;else {cout << "YES" << endl << sz[0] - c[0] << ' ' << sz[1] - c[1] << endl;for(int i = 1; i <= n; ++i) if(!d[0][i]) write(a[0][i]), putchar(' ');cout << endl;for(int i = 1; i <= m; ++i)if(!d[1][i]) write(a[1][i]), putchar(' ');cout << endl;}}
}

不过对线段树的理解加深了不少，理解了很多之前未曾设想的用法

理解了一些方法，比如钦定某个点为代表元，之后向四周遍历

或者使用类似染色的思想，简化问题