42 条评论
-
呦呦 LV 1 @ 2024-11-12 15:19:07
我是一个小白，写了题库里的几题，我把代码放到我自己的软件中运行，答案是正确的。可是提交后往往只能得一半的分数，甚至零分，我看了些视频，好像是有点要卡，可是我找了很多资料，实在是没有没有非常详细的回答。不知道有没有人能帮我解答一下。在解题时到底怎么看答案需要的点，怎么才能得高分，应该先学些什么知识，再进行答题，还是通过答题看答案，慢慢积累
-
@ 2024-11-17 14:14:54就是得查一下，RE数据类型，数组之类的有没有问题，TLE要优化， MLE要解决空间问题，WA查方法，在自己的地方测的只是样例，自己还要多造数据测，造极端数据。我虽然是小升初，但是我就是这样过来的
-
-
@ 2022-10-7 12:18:36#041 2022.10.7
Statement
选一个陪审团，先随机挑选 个人作为陪审团的候选人，然后选 人组成陪审团。控方和辩方会给候选人打分。请做到选出的 个人满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案，那么选辩控双方总分之和最大的方案。如果方案还是不惟一，输出任意一种均可。
- 任何分值不超过 。
Tutorial
Click to see
虽然数据范围不大，以为是搜索，但其实是受了“宇宙射线”影响的超级变形背包。可能连一点背包的影子都不见了。
考虑 DP。设状态 表示前 个人中选 个人，得分差为 ，最大的得分总和。注意这里得分差不是绝对值差，为了防止下标出现负数，差需要加上 。
这道题难于找出答案的具体方案。在 DP 过程中，把所有不合法解全部标为负无穷，从 处剖开，不难发现，最终状态中找到的第一个合法状态，就是我们想要的。后面的倒退不难，注意输出格式。
为什么这样就解决问题了呢？要求差最小，把 看作 ，也就是对于 ，如果状态 合法， 的绝对值一定是最小的。至于和最大，DP 迭代过程中已经计算出来了。
// 陪审团 #include <iostream> #include <cstring> #include <vector> #include <cstdio> #include <algorithm> #define SIZE 205 #define all(x) x.begin(), x.end() #define debug(x) cout<<#x<<":"<<x<<endl; using namespace std; int n, m; int p[SIZE], d[SIZE]; int base=400; int f[SIZE][21][1000]; signed main() { int COUNT=1; while(cin>>n>>m && n+m) { for(int i=1; i<=n; i++) cin>>p[i]>>d[i]; memset(f, -0x3f, sizeof(f)); f[0][0][base]=0; for(int i=1; i<=n; i++) for(int j=0; j<=m; j++) for(int k=0; k<1000; k++) { int tmp=k-(p[i]-d[i]); if(tmp<0 || tmp>=1000) { f[i][j][k]=f[i-1][j][k]; continue; } if(!j) { f[i][j][k]=f[i-1][j][k]; continue; } f[i][j][k]=max(f[i-1][j][k], f[i-1][j-1][tmp]+p[i]+d[i]); } int v=0; while(f[n][m][base-v]<0 && f[n][m][base+v]<0) v++; if(f[n][m][base-v]>f[n][m][base+v]) v=base-v; else v=base+v; vector<int> ans; int i=n, j=m, k=v; while(j) { if(f[i][j][k]==f[i-1][j][k]) i--; else { ans.push_back(i); k-=(p[i]-d[i]); i--, j--; } } int sp=0, sd=0; for(int i=0; i<ans.size(); i++) sp+=p[ans[i]], sd+=d[ans[i]]; printf("Jury #%d\n", COUNT++); printf("Best jury has value %d for prosecution and value %d for defence:\n", sp, sd); sort(all(ans)); for(int i=0; i<ans.size(); i++) cout<<" "<<ans[i]; cout<<endl; cout<<endl; } return 0; }👀 25👍 16🌿 13😄 11❤️ 11👎 3😕 3-
@ 2022-11-7 21:46:28现在是Hydro每月一题吧
-
@ 2023-3-13 20:41:55现在，没了吗。
-
@ 2023-4-26 7:27:43
现在，没了吗。
-
@ 2023-4-28 22:35:10现在，没了吗。
-
@ 2023-7-8 21:27:14现在是Hydro每年一题吧/kel
-
@ 2023-11-4 17:50:40
应该是Hydro每世纪一题
-
@ 2024-1-29 16:14:36
这下彻底没了
-
@ 2024-3-1 20:11:31
想发，可是站长undefined不回
-
@ 2024-3-23 19:49:31今年的呢？每年一题？
-
@ 2024-6-19 21:39:48C++？
-
@ 2024-8-6 8:05:216666
-
@ 2024-8-16 10:59:53现在是彻底没题了
-
@ 2024-10-4 9:01:59Hydro每(没)
年一题 -
@ 2024-10-7 15:40:44啊！
-
@ 2024-10-23 16:01:27
新手，问一下这个是用哪种语言写的
-
@ 2022-8-19 8:02:26
#040 2022.8.19
Statement
现在有一种卡牌游戏，每张卡牌上有三个属性值：。
把卡牌分为 两类，分别有 张。
两张卡牌能够配对，当且仅当，存在至多一项属性值使得两张卡牌该项属性值互质，且两张卡牌类别不同。
比如一张 类卡牌属性值分别是 ，一张 类卡牌属性值分别为 。
那么这两张牌是可以配对的，因为只有 和 一组属性互质。
游戏的目的是最大化匹配上的卡牌组数，当然每张卡牌只能用一次。
$\textbf{Data Range:} 1 \leq n1, n2 \leq 3 \times 10^4$。
Solution
solution
这道题有一个很直接的最大流做法，但是暴力建边的复杂度和边数都是 $n_1 \times n_2$ 的，于是要考虑优化建边的数量。注意到题目要求两张卡牌存在至多一项属性值使得两张卡牌该项属性值互质。
这个要求等价于两张卡牌至少有两项属性值的 大于 ，也就是有至少一个相同的质因数。
我们先暴力枚举这两项属性值是 三种情况。
我们分别枚举 中这两个属性值的质因数，以及他们可能形成的组合，将这个质因数组合建出一个点 。
然后枚举 中这两个属性值的质因数，以及他们可能形成的组合，查看之前枚举 的时候是否有建出对应的点，如果有代表 和 这两个属性值存在相同的质因数，也就满足了上面的要求。
那么可以将这个东西进行网络流建模，我们假设左边 中第 张卡牌包含 点所代表的质因数，右边第 张卡牌也包含 点所包含的质因数。
那么我们可以 ，流量为 ，，流量为 。
如此对枚举的两项属性值是 三种情况分别做一遍，然后设置一个源点和汇点与 卡牌分别连边，流量为 ，之后跑最大流即可。
以内的质数只有 个，一个数最多 个质因子。
我们中间新建出来的点数最多为 ，中间建出来的边数最多为 。
// 德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱 // 德丽莎的可爱在于德丽莎很可爱，德丽莎为什么很可爱呢，这是因为德丽莎很可爱！ // 没有力量的理想是戏言，没有理想的力量是空虚 #include <bits/stdc++.h> #define LL long long #define int long long using namespace std; char ibuf[1 << 15], *p1, *p2; #define getchar() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 15, stdin), p1==p2) ? EOF : *p1++) inline int read() { char ch = getchar(); int x = 0, f = 1; while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); return x * f; } void print(LL x) { if (x > 9) print(x / 10); putchar(x % 10 + '0'); } template<class T> bool chkmin(T &a, T b) { return a > b ? (a = b, true) : false; } template<class T> bool chkmax(T &a, T b) { return a < b ? (a = b, true) : false; } #define rep(i, l, r) for (int i = (l); i <= (r); i++) #define repd(i, l, r) for (int i = (l); i >= (r); i--) #define REP(i, l, r) for (int i = (l); i < (r); i++) const int N = 5e6; int pr[N], cnt, vis[N]; void prime(int n) { rep (i, 2, n) { if (!vis[i]) { pr[++cnt] = i; } for (int j = i; j <= n; j += i) vis[j] = 1; } } int n1, n2; map <pair<int,int>, int> id; int tot, S, T; int num = 1, nex[N], first[N], v[N], flow[N]; vector <int> ys[205]; int dep[N], cur[N]; queue <int> q; struct node { int a, b, c; } X[N], Y[N]; bool bfs(int s,int t) { rep (i, 0, t) dep[i] = 0; q.push(s); dep[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); cur[u] = first[u]; for (int i = first[u]; i; i = nex[i]) { int to = v[i]; if (dep[to] || !flow[i]) continue; q.push(to); dep[to] = dep[u] + 1; cur[to] = first[to]; } } return dep[t] != 0; } int dfs(int x,int a) { if (x == T) return a; int ans = 0; for (int i = cur[x]; i; i = nex[i]) { int to = v[i]; cur[x] = i; if (dep[to] == dep[x] + 1 && flow[i]) { int qwq = dfs(to, min(flow[i], a)); a -= qwq; flow[i] -= qwq; flow[i ^ 1] += qwq; ans += qwq; if (!a) break; } } return ans; } int mxflow(int s,int t) { int ans = 0; while (bfs(s, t)) ans += dfs(s, 1ll << 30); return ans; } void add(int from,int to,int val) { nex[++num] = first[from]; first[from] = num; v[num] = to; flow[num] = val; } void ins(int a,int b,int c) { add(a, b, c), add(b, a, 0); } void solve() { prime(200); n1 = read(), n2 = read(); rep (i, 1, n1) { X[i].a = read(), X[i].b = read(), X[i].c = read(); } rep (i, 1, n2) { Y[i].a = read(), Y[i].b = read(), Y[i].c = read(); } tot = n1 + n2; sort(pr + 1, pr + cnt + 1); rep (x, 1, 200) { rep (j, 1, cnt) { if (x < pr[j]) continue; if (x % pr[j] == 0) ys[x].push_back(pr[j]); } } // AB id.clear(); rep (i, 1, n1) { int A = X[i].a, B = X[i].b; for (auto p : ys[A]) { for (auto q : ys[B]) { int pp = p, qq = q; if (id[{pp, qq}] == 0) { id[ {pp, qq} ] = ++tot; // cout << 1 << " " << pp << " " << qq << " get id : " << tot << "\n"; } int pt = id[ {pp, qq} ]; ins(i, pt, 1); } } } rep (i, 1, n2) { int A = Y[i].a, B = Y[i].b; for (auto p : ys[A]) { for (auto q : ys[B]) { int pp = p, qq = q; if (id[ {pp, qq} ] == 0) { id[ {pp, qq} ] = ++tot; } int pt = id[ {pp, qq} ]; ins(pt, i + n1, 1); } } } // AC id.clear(); rep (i, 1, n1) { int A = X[i].a, B = X[i].c; for (auto p : ys[A]) { for (auto q : ys[B]) { int pp = p, qq = q; if (id[{pp, qq}] == 0) { id[ {pp, qq} ] = ++tot; } int pt = id[ {pp, qq} ]; ins(i, pt, 1); } } } rep (i, 1, n2) { int A = Y[i].a, B = Y[i].c; for (auto p : ys[A]) { for (auto q : ys[B]) { int pp = p, qq = q; if (id[ {pp, qq} ] == 0) { id[ {pp, qq} ] = ++tot; } int pt = id[ {pp, qq} ]; ins(pt, i + n1, 1); } } } //BC id.clear(); rep (i, 1, n1) { int A = X[i].b, B = X[i].c; for (auto p : ys[A]) { for (auto q : ys[B]) { int pp = p, qq = q; if (id[{pp, qq}] == 0) id[ {pp, qq} ] = ++tot; int pt = id[ {pp, qq} ]; ins(i, pt, 1); } } } rep (i, 1, n2) { int A = Y[i].b, B = Y[i].c; for (auto p : ys[A]) { for (auto q : ys[B]) { int pp = p, qq = q; if (id[ {pp, qq} ] == 0) { id[ {pp, qq} ] = ++tot; } int pt = id[ {pp, qq} ]; ins(pt, i + n1, 1); } } } S = tot + 1, T = tot + 2; rep (i, 1, n1) ins(S, i, 1); rep (i, 1, n2) ins(i + n1, T, 1); int ans = mxflow(S, T); cout << ans << "\n"; } signed main () { #ifdef LOCAL_DEFINE freopen("1.in", "r", stdin); freopen("1.ans", "w", stdout); #endif int T = 1; while (T--) solve(); #ifdef LOCAL_DEFINE cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; #endif return 0; }❤️ 9👍 8👀 4-
@ 2022-8-19 11:31:30现在是Hydro每月一题吧
-
@ 2022-8-24 7:15:12emmm....
-
@ 2022-10-6 19:14:59e
-
-
@ 2022-7-22 7:31:21#039 2022.7.22
标签：倍增。
Statement
定义函数 如下：
$$f\big((l,~r)\big) = (\min_{i = l}^r a_i,~\max_{i = l}^r a_i) $$给出长度为 的值域为 序列 ， 个询问，每次询问给出 ，问 通过多少次 操作后达到 ，或判断无法达到。
Solution
Solution
考虑对于一个点 ，当其同时存在于 和 内时，由于 $\min_{i = l_1}^{r_1} a_i \le a_p \le \max_{i = l_1}^{r_1} a_i$，所以 ，同理 。也就是说，当两个区间有交时，他们各进行一次 操作后分别得到的两个新区间也同样有交。
对于 $[l_1,~r_1],~[l_2,~r_2]~(l_1 \le l_2 \le r_1 \le r_2)$，显然有 $f\big((l_1,~r_2)\big) = f\big((l_1,~r_1)\big) \bigcup f\big((l_2,~r_2)\big)$。而我们通过上面的结论可知等号右侧的两个区间有交，可以通过对左端点取较小值，右端点取较大值的方法得到他们的并。
这启发我们得到：$f\big((l,~r)\big) = \bigcup_{i = l}^{r - 1} f\big((i,~i + 1)\big)$。若预处理得到 ，则 $f\big((l,~r)\big) = (\min_{i = l}^{r - 1} x_i, \max_{i = l}^{r - 1} y_i)$，可通过两个 ST 表做到 得出答案。
考虑当我们需要进行多次 操作时需要如何计算，由于 $f^{a + b}\big((l,~r)\big) = f^a\Big(f^b\big((l,~r)\big)\Big)$，不难想到使用倍增的思想，对于每个 我们预处理 ，再使用与上面相同的 ST 表维护方法即可 算出 。
询问 最少需操作多少次时，我们只需要从大往小枚举 找到最大的 满足 ，除去无解情况后答案即为 。
总时间复杂度 。
Code
偷了个懒使用线段树实现。复杂度 ，也可通过本题。
/** * @file 1707E.cpp * @author Macesuted (i@macesuted.moe) * @date 2022-07-17 * * @copyright Copyright (c) 2022 * */ #include <bits/stdc++.h> using namespace std; #ifndef LOCAL #define endl '\n' #endif bool mem1; #define maxn 100005 #define maxlgn 18 typedef pair<int, int> pii; pii merge(const pii& a, const pii& b) { return {min(a.first, b.first), max(a.second, b.second)}; } class SegmentTree { private: pii tree[maxn << 2]; int n; void pushUp(int p) { return tree[p] = merge(tree[p << 1], tree[p << 1 | 1]), void(); } void insert(int p, int l, int r, int qp, pii v) { if (l == r) return tree[p] = v, void(); int mid = (l + r) >> 1; qp <= mid ? insert(p << 1, l, mid, qp, v) : insert(p << 1 | 1, mid + 1, r, qp, v); return pushUp(p); } pii query(int p, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return tree[p]; int mid = (l + r) >> 1; if (qr <= mid) return query(p << 1, l, mid, ql, qr); if (ql > mid) return query(p << 1 | 1, mid + 1, r, ql, qr); return merge(query(p << 1, l, mid, ql, qr), query(p << 1 | 1, mid + 1, r, ql, qr)); } public: void resize(int _n) { return n = _n, void(); } void insert(int p, pii v) { return insert(1, 1, n, p, v); } pii query(pii a) { return a.first >= a.second ? pii{INT_MAX, INT_MIN} : query(1, 1, n, a.first, a.second - 1); } }; int a[maxn]; SegmentTree ST[maxlgn]; void solve(void) { int n, q; cin >> n >> q; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 0; i < maxlgn; i++) ST[i].resize(n); for (int i = 1; i < n; i++) ST[0].insert(i, {min(a[i], a[i + 1]), max(a[i], a[i + 1])}); for (int i = 1; i < maxlgn; i++) for (int j = 1; j < n; j++) ST[i].insert(j, ST[i - 1].query(ST[i - 1].query({j, j + 1}))); while (q--) { int l, r; cin >> l >> r; if (l == 1 && r == n) cout << 0 << endl; else if (l == r) cout << -1 << endl; else { int ans = 0; for (int i = maxlgn - 1; ~i; i--) { pii ret = ST[i].query({l, r}); if (ret != pii{1, n}) ans |= 1 << i, tie(l, r) = ret; } ans++; cout << (ans == (1 << maxlgn) ? -1 : ans) << endl; } } return; } bool mem2; int main() { ios::sync_with_stdio(false), cin.tie(nullptr); #ifdef LOCAL cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl; #endif int _ = 1; while (_--) solve(); #ifdef LOCAL cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl; #endif return 0; }👍 12❤️ 5🕊️ 5🍋 4👀 4😄 3-
@ 2022-7-30 23:00:46现在是每周一题吧
-
@ 2022-8-5 21:54:27
催更，催更！
-
@ 2022-8-5 21:54:30
催更，催更！
-
@ 2022-8-12 14:09:14
为什么不同步到题解呢？
-
@ 2022-8-14 9:56:57
催更！！！
-
@ 2023-4-6 22:30:06
请问题目标签怎么打出来的？
-
@ 2024-8-18 12:54:02催！
-
-
@ 2022-7-19 7:47:15
#038.2022.7.19
标签：莫比乌斯反演，数论
Statement
给定 个数 ，求 的值。
，。
Solution
solution
肯定还是要考虑莫反，但是题目中给定了 ，这就不能常规的进行反演。
但是其实没有影响的，我们记录每个数 的出现次数 ，然后原式子等价于下面的式子：
$$\sum_{i=1}^N\sum_{j=1}^N \text{lcm}(i,j) \times c_i \times c_j $$于是可以进行反演了。
$$\sum_{i=1}^N\sum_{j=1}^N \text{lcm}(i,j) \times c_i \times c_j $$$$\sum_{i=1}^N\sum_{j=1}^N \dfrac{i \times j}{\gcd(i,j)} \times c_i \times c_j $$然后我们套路的改为枚举 。
$$\sum_{d=1}^N \sum_{i=1}^{\frac{N}{d}}\sum_{j=1}^{\frac{N}{d}} \dfrac{id \times jd}{d} \times c_{id} \times c_{jd} [(i,j)= 1] $$$$\sum_{d=1}^N \sum_{i=1}^{\frac{N}{d}}\sum_{j=1}^{\frac{N}{d}} ijd \times c_{id} \times c_{jd} [(i,j)= 1] $$$$\sum_{d=1}^N \sum_{i=1}^{\frac{N}{d}}\sum_{j=1}^{\frac{N}{d}} \sum_{x|(i,j)} \mu(x) \times ijd \times c_{id} \times c_{jd} $$$$\sum_{d=1}^N \sum_{i=1}^{\frac{N}{d}}\sum_{j=1}^{\frac{N}{d}} \sum_{x|i,x | j} \mu(x) \times ijd \times c_{id} \times c_{jd} $$之后枚举 。
$$\sum_{d=1}^N \sum_{x=1}^{\frac{N}{d}}\mu(x) \sum_{i=1}^{\frac{N}{dx}} \sum_{j=1}^{\frac{N}{dx}} ix \times jx \times d \times c_{idx} \times c_{jdx} $$$$\sum_{d=1}^N \sum_{x=1}^{\frac{N}{d}}\mu(x) x^2 \sum_{i=1}^{\frac{N}{dx}} \sum_{j=1}^{\frac{N}{dx}} ijd\times c_{idx} \times c_{jdx} $$$$\sum_{d=1}^N d\sum_{x=1}^{\frac{N}{d}}\mu(x) x^2 \sum_{i=1}^{\frac{N}{dx}} \sum_{j=1}^{\frac{N}{dx}} ij\times c_{idx} \times c_{jdx} $$令 ，代入进行化简。
$$\sum_{T=1}^N \sum_{d|T} d \times \mu(\dfrac{T}{d}) \times (\dfrac{T}{d})^2 \sum_{i=1}^{\frac{N}{T}} \sum_{j=1}^{\frac{N}{T}} ij \times c_{\frac{idT}{d}} \times c_{\frac{jdT}{d}} $$$$\sum_{T=1}^N (\sum_{d|T} d \times \mu(\dfrac{T}{d}) \times (\dfrac{T}{d})^2) \times (\sum_{i=1}^{\frac{N}{T}} \sum_{j=1}^{\frac{N}{T}} ij \times c_{\frac{idT}{d}} \times c_{\frac{jdT}{d}}) $$对于 $\sum_{d|T} d \times \mu(\dfrac{T}{d}) \times (\dfrac{T}{d})^2$ 这一部分，他等价于 $T \sum_{d|T} \times \mu(\dfrac{T}{d}) \times (\dfrac{T}{d})$，于是我们可以在进行线性筛之后暴力枚举倍数预处理就好了，复杂度是对的。
所以我们只用考虑后面一部分怎么做，也就是 $\sum_{i=1}^{\frac{N}{T}} \sum_{j=1}^{\frac{N}{T}} ij \times c_{\frac{idT}{d}} \times c_{\frac{jdT}{d}}$。
我们发现这东西其实不用写成 两层循环，完全可以写成 $(\sum_{i=1}^{\frac{N}{T}} i \times c_{\frac{idT}{d}})^2 = (\sum_{i=1}^{\frac{N}{T}} i \times c_{iT})^2$。
和上面一样的，莫反题到最后优化也就是整除分块和预处理了。
我们对每个 暴力预处理 ，根据经典结论 。
然后枚举倍数的复杂度也是这样的，所以之前的预处理复杂度也是 的。
于是总预处理复杂度为 。
最后我们直接暴力回答答案就好了，统计答案的复杂度为 。
// 德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱 // 德丽莎的可爱在于德丽莎很可爱，德丽莎为什么很可爱呢，这是因为德丽莎很可爱！ // 没有力量的理想是戏言，没有理想的力量是空虚 #include <bits/stdc++.h> #define LL long long #define int long long using namespace std; char ibuf[1 << 15], *p1, *p2; #define getchar() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 15, stdin), p1==p2) ? EOF : *p1++) inline int read() { char ch = getchar(); int x = 0, f = 1; while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); return x * f; } void print(LL x) { if (x > 9) print(x / 10); putchar(x % 10 + '0'); } template<class T> bool chkmin(T &a, T b) { return a > b ? (a = b, true) : false; } template<class T> bool chkmax(T &a, T b) { return a < b ? (a = b, true) : false; } #define rep(i, l, r) for (int i = (l); i <= (r); i++) #define repd(i, l, r) for (int i = (l); i >= (r); i--) #define REP(i, l, r) for (int i = (l); i < (r); i++) const int N = 5e4 + 6, M = 5e4 + 5; int n, vis[N], c[N], pr[N], tot, mu[N]; void prime(int n) { mu[1] = 1; rep (i, 2, n) { if (!vis[i]) { pr[++tot] = i; mu[i] = -1; } rep (j, 1, tot) { if (pr[j] * i > n) break; vis[i * pr[j]] = 1; if (i % pr[j] == 0) { mu[i * pr[j]] = 0; break; } else { mu[i * pr[j]] = -mu[i]; } } } } int f[N], g[N]; void solve() { n = read(); rep (i, 1, n) { int x = read(); c[x] ++; } prime(M); rep (i, 1, M) for (int j = i; j <= M; j += i) f[j] += mu[i] * i; rep (i, 1, M) f[i] *= i; rep (T, 1, M) for (int i = 1; i <= M / T; i++) g[T] += i * c[i * T]; int ans = 0; rep (T, 1, M) ans += f[T] * g[T] * g[T]; cout << ans; } signed main () { #ifdef LOCAL_DEFINE freopen("1.in", "r", stdin); freopen("1.ans", "w", stdout); #endif int T = 1; while (T--) solve(); #ifdef LOCAL_DEFINE cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; #endif return 0; }👍 5❤️ 5 -
@ 2022-7-14 8:02:10
#037 2022.7.13
标签：
dp,math,*3100。Statement
有一个 的网格，初始是全部联通的。
除了第一行与最后一行的网格，每天每一行的最左边和最右边的格子都有 的概率消失。
消失的网格不再联通，求 天后，网格始终保持联通的概率。
答案对 取模。
$\textbf{Data Range:} 1 \leq n,m \leq 1.5 \times 10^3, k\leq 10^5$。
Solution
Solution
不难发现最后每一行剩下的一定都会是一个连续的区间，而且每行之间相互独立。
自然设立状态 表示当前是第 行， 天后这一行剩下的区间为 ，第 行到第 行都联通的概率。
先考虑算变成区间 的概率。
设 天内，消失 个格子的概率为 。
所以剩下区间 的概率为 。
当然还需要检查这段区间长度是否合法，因为最多消失 个格子。
转移式子不难写出。
$$dp_{i,l,r} = g_{l-1} \times g_{m-r} \sum_{[l_1, r_1] \cap [l,r] \neq \varnothing} dp_{i-1,l_1,r_1} $$复杂度 ，显然不行，而且状态数都为 。
那考虑优化状态，去掉左端点的限制。
设 表示第 行的剩余区间的右端点为 ，第 行到第 行都联通的概率，转移的时候枚举 进行转移。
考虑一个和区间 有交的区间 。
它满足 ，那么容斥把这一部分算出来即可。
对于 的部分，枚举 时计算 。
对于 的部分，因为网格是对称的，所以 也可以表示左端点为 且联通的概率，因此这一部分可以计算为 。
于是转移如下。
$$dp_{i,r} = \sum_{l=1}^r g_{l-1} g_{m-r} (\sum_{j=1}^m f_{i-1, j} - \sum_{j = 1}^ {i-1} f_{i-1,j} - \sum_{j=1}^{m-r} f_{i-1,j}) $$这东西长得就很一脸前缀和的样子，那就考虑前缀和优化。
令 表示 。
$$f_{i,r} = g_{m-r} \sum_{l=1}^r g_{l-1} )(s_m - s_{l-1} - s_{m-r}) $$$$f_{i,r} = g_{m-r} \times( (s_m - s_{m-r}) \sum_{l = 1}^r g_{l-1} - \sum_{l=1}^r g_{l-1} s_{l-1}) $$在令 和 依次为 与 的前缀和，之后即可做到 转移，总时间复杂度 。
// 德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱 // 德丽莎的可爱在于德丽莎很可爱，德丽莎为什么很可爱呢，这是因为德丽莎很可爱！ #include <bits/stdc++.h> #define int long long using namespace std; inline int read() { int x = 0, f = 1; char ch = getchar(); while( !isdigit(ch) ) { if(ch == '-') f = -1; ch = getchar(); } while( isdigit(ch) ) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } return x * f; } const int N = 3e6, mod = 1e9 + 7; int n, m, a, b, pt, pt2, k, ans, fac[N], ifac[N], dp[3005][3005], g[3005]; int power(int a,int b) { int ans = 1; while (b) { if (b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1;} return ans; } int binom(int n,int m) { return fac[n] * ifac[m] % mod * ifac[n - m] % mod; } int s[N], p[N], q[N]; signed main () { n = read(), m = read(), a = read(), b = read(), k = read(); fac[0] = 1; for (int i = 1; i <= k; i++) fac[i] = fac[i - 1] * i % mod; ifac[k] = power(fac[k], mod - 2); for (int i = k - 1; ~i; i--) ifac[i] = ifac[i + 1] * (i + 1) % mod; pt = a * power(b, mod - 2) % mod; pt2 = 1 - pt; pt2 += mod; pt2 %= mod; for (int i = 0; i <= k && i <= m; i++) g[i] = binom(k, i) * power(pt, i) % mod * power(pt2, k - i) % mod; dp[0][m] = 1; p[0] = g[0]; for (int i = 1; i <= m; i++) p[i] = p[i - 1] + g[i], p[i] %= mod; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) s[j] = s[j - 1] + dp[i - 1][j], s[j] %= mod; for (int j = 1; j <= m; j++) q[j] = q[j - 1] + g[j] * s[j] % mod, q[j] %= mod; for (int r = 1; r <= m; r++) dp[i][r] = g[m - r] * ( (s[m] - s[m - r] + mod) % mod * p[r - 1] % mod - q[r - 1] + mod) % mod; } for (int i = 1; i <= m; i++) { ans += dp[n][i]; ans %= mod;} printf("%lld\n", ans); return 0; }👍 7❤️ 6😄 4 -
@ 2022-7-9 12:57:38
#036 2022.7.9 [IOI2020] mushrooms
标签：构造，交互。
(不要提交到洛谷上的这道题，那道题交不了) 研究蘑菇的专家安德鲁在研究新加坡的本地蘑菇。
作为研究的一部分，安德鲁采集了 个蘑菇，编号为 到 。每个蘑菇均为两种蘑菇种类之一，称为 或 。
安德鲁知道蘑菇 属于种类 ，但是由于这两种蘑菇看起来很相似，他不知道蘑菇 到 属于哪一种。
幸运的是,安德鲁的实验室里有一台机器可以帮助他。在使用这台机器时,需要将两个或者多个蘑菇放到机器里,并摆成一排（以任意顺序），然后打开机器。接下来，这台机器会计算所有不属于同一种类的相邻蘑菇对的个数。例如,如果你把种类为 的蘑菇（按照这个顺序）放到机器中，结果应该是 。
但是，因为机器操作非常昂贵，机器只能使用有限的次数。此外，在机器的所有使用中，放置到机器中的蘑菇总数不能超过 。请使用这台机器帮助安德鲁来数一数他采集了多少个种类为 的蘑菇。
题解
为了方便, 以下我们将不加申明的将 用作上一次 操作的返回值, 读者可以根据上下文知道这个 的值.
Method 1
我们考虑朴素暴力: 对所有 执行操作 , 这是一个时间复杂度 的算法, 可以获得 ... 10 分.
Method 2
我们发现: 如果已知有 个 0, 分别是 , 那么可以执行这样的一次操作来求出长度为 的序列 中 0 的个数: $\texttt{query}(\{g_1, f_1, g_2, f_2, \cdots g_k, f_k\})$. 容易知道 $\sum\limits_{i=1}^k g_i = \lceil\frac{ret}{2}\rceil$. 有 个 1 的情况下同理.
而如何求出 呢? 显然直接套用 Method 1 即可. 我们使用类似根号分治的思想可以做到 的复杂度(实际上后续都是常数优化, 并没有超越这个复杂度.)
Optimize 1
我们考察这种操作: $\texttt{query}(\{g_1, f_1, g_2, f_2, \cdots g_k, f_k\})$. 那么可以根据 的奇偶性判断 的值, 具体来说, 由于 左右均为相同的值, 故不管这些数如何取值, 均不会影响 的奇偶性, 所以 的奇偶性只由 决定, 也即可以得出 的具体值. 于是我们可以动态的维护当前 0/1 的个数和这些 0/1 的位置然后每次启发式的用 0/1 去询问.
Optimize 2
这同时也可以对 Method 1 的过程做出优化: 在有两个相同值的数 时, 每次可以通过 确定 , 的具体值.
Optimize 3
Method 2 的过程已经难以优化, 接下来我们来优化 Method 1 的过程.
不妨考虑我们有充分多的 0 和充分多的 1, 接下来我们考虑如何更优的询问, 具体来说, 我们将用 2 询问次得到 5 个数的具体值.
我们设 为所有 0 的位置序列, 为所有 1 的位置序列. 即 必有 .
我们先进行询问 . 根据返回值讨论: 首先可以发现根据 的奇偶性确定 , 然后我们令 , 这样就有 . 显然只需要考虑 的情况.
如果 , 我们接下来进行询问 $\texttt{query}(\{q_1, y, q_2, p_1, z, p_2, u, p_3, v\})$, 然后令 (这是因为有相邻的 ).
首先考察 的奇偶性以确定 , 然后令 , 这样就有 , 也即 , 这样又可以根据 的奇偶性来确定 , 从而确定 和 .
Optimize 4
调整你的参数.
👍 9❤️ 4-
@ 2022-7-13 9:02:03
催更
-
@ 2022-7-13 21:32:07
催催催
-
@ 2022-7-13 22:19:48
喵
-
-
@ 2022-7-8 0:06:12
#035 2022.7.8
标签：Hash。
给定一个树，定义一个节点的权值为删去这个节点后的图中最大连通块的大小。定义树的品种为所有节点权值构成的可重集，两树品种相同当且仅当可重集相同。
现在要给这个树加一个叶子，求能得到多少品种的树，以及每个品种有多少种添加方法得到。
，时限 4s。
题解
显然，对于一个不是重心的节点，删掉这个点后的连通块里面，最大的连通块就是包含重心的连通块。因此如果叶子添加在重心头上，别的点权值都要加一，重心不变。（对于两个重心的情况，在一个重心上加点时，显然另一个重心权值是要加一的。）
考虑如果不加在重心上。注意到上面提到的性质，哪些节点的权值会改变（如图 1，3 号节点是重心，把它当作根）：
假设我们向 9 号节点添加一个叶子，来分类讨论。
- 和被添加叶子的点不在同一子树（如 1,2,6,7 号点），显然权值都会加一。
- 和被添加叶子点在同一侧，不在这个点到根的路径上（如 5,10 号点），考虑到删掉后其最大连通块是根的那一侧，因此权值也会加一。
- 重心（如 3 号点），若被添加叶子点在重心的最大子树内，则重心权值加一；否则不变。
- 被添加叶子节点本身（如 9 号点），显然不变。
- 重心和被添加叶子点路径上的点（如 4 号点），因为删掉它后新叶子没有连通到根，所以不变。
总结一下，如果新叶子在重心的最大子树内，不会改变的就是重心到它的链（不包括两端）；否则，不会改变的是重心到它的链（包括重心，不包括被添加节点）。
我们要维护的是所有点贡献的集合，考虑从重心出发深搜整颗树，到达一个点时，只需要修改这一个点的贡献即可。可以用 Hash 实现。
注意到集合是无序的，如果和我考场降智 naive 地用每个点权值的 次方和（ 为常量）当 Hash 函数，注意到 在 时分布不少，很大概率被卡掉。因此考虑维护每个点权值构成的桶，对这个桶进行字符串 Hash 即可。
单 Hash 也被卡了（我运气背还是出题人毒瘤还是生日悖论再现都有可能），建议双 Hash。
剩下的都是一些细节问题，例如两个重心的情况，可以考虑断掉中间的边，拆成两棵树考虑（在一棵树上时反正另一棵树点的贡献都是要加一的），等等。
代码
#include<bits/stdc++.h> #define int long long using namespace std; bool Begin; const int max_n=2000006,mod1=1000000009,mod2=998244853; inline int read(){ int x=0;bool w=0;char c=getchar(); while(c<'0' || c>'9') w|=c=='-',c=getchar(); while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return w?-x:x; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10^48); } struct graph{ int ct,hd[max_n],to[max_n<<1],nx[max_n<<1]; graph(){ct=1;} inline void add(int u,int v){ nx[++ct]=hd[u],hd[u]=ct,to[ct]=v; } }e; inline int MOD1(int x){ return (x>=mod1?x-mod1:x); } inline int MOD2(int x){ return (x>=mod2?x-mod2:x); } struct Hashnum{ int x1,x2; Hashnum(int A=0,int B=0):x1(A),x2(B){} bool operator == (const Hashnum &b) const{ Hashnum a=*this; return (a.x1==b.x1 && a.x2==b.x2); } bool operator < (const Hashnum &b) const{ Hashnum a=*this; return (a.x1<b.x1 || (a.x1==b.x1 && a.x2<b.x2)); } Hashnum operator * (const Hashnum &b) const{ Hashnum a=*this; return Hashnum(a.x1*b.x1%mod1,a.x2*b.x2%mod2); } Hashnum operator + (const Hashnum &b) const{ Hashnum a=*this; return Hashnum(MOD1(a.x1+b.x1),MOD2(a.x2+b.x2)); } Hashnum operator - (const Hashnum &b) const{ Hashnum a=*this; return Hashnum(MOD1(a.x1-b.x1+mod1),MOD2(a.x2-b.x2+mod2)); } Hashnum operator * (const int &b) const{ Hashnum a=*this; return a*Hashnum(b,b); } Hashnum operator + (const int &b) const{ Hashnum a=*this; return a+Hashnum(b,b); } Hashnum operator - (const int &b) const{ Hashnum a=*this; return a-Hashnum(b,b); } }hs; int n,sz[max_n],mxs[max_n]; inline void dfs1(int u,int fa){ sz[u]=1; for(register int i=e.hd[u];i;i=e.nx[i]){ int v=e.to[i]; if(v==fa) continue; dfs1(v,u); sz[u]+=sz[v]; mxs[u]=max(mxs[u],sz[v]); } mxs[u]=max(mxs[u],n-sz[u]); } int zx,zx2; inline void dfs2(int u,int fa){ zx=u; for(register int i=e.hd[u];i;i=e.nx[i]){ int v=e.to[i]; if(v==fa) continue; if(sz[v]>n/2) dfs2(v,u); } } int ans[max_n],tong[max_n],pw1[max_n],pw2[max_n]; int B1=114514,B2=11037; map<Hashnum,int> mp; inline void dfs3(int u,int fa,Hashnum hs){ for(register int i=e.hd[u];i;i=e.nx[i]){ int v=e.to[i]; if(v==fa || v==zx || v==zx2) continue; Hashnum t=hs-Hashnum(pw1[mxs[v]+1],pw2[mxs[v]+1])+Hashnum(pw1[mxs[v]],pw2[mxs[v]]); ++mp[t]; dfs3(v,u,t); } } bool End; #define File "forest" signed main(){ // #ifndef ONLINE_JUDGE // freopen(File ".in","r",stdin); // freopen(File ".out","w",stdout); // #endif // cerr<<"Memory : "<<(&Begin-&End)/1024.0/1024<<"\n"; n=read(); for(register int i=1;i<n;++i){ int u=read(),v=read(); e.add(u,v),e.add(v,u); } dfs1(1,-1); dfs2(1,-1); for(register int i=1;i<=n;++i) ++tong[mxs[i]+1]; ++tong[n]; if(!(n&1)) for(register int i=1;i<=n;++i) if(i!=zx && mxs[i]==mxs[zx]){ zx2=i; break; } for(register int i=1;i<=n;++i){ hs.x1=(hs.x1*B1+tong[i]), hs.x2=(hs.x2*B2+tong[i]); } pw1[n]=pw2[n]=1; for(register int i=n-1;i;--i){ pw1[i]=pw1[i+1]*B1%mod1, pw2[i]=pw2[i+1]*B2%mod2; } ++mp[hs-Hashnum(pw1[mxs[zx]+1],pw2[mxs[zx]+1])+Hashnum(pw1[mxs[zx]],pw2[mxs[zx]])]; if(zx2) ++mp[hs-Hashnum(pw1[mxs[zx2]+1],pw2[mxs[zx2]+1])+Hashnum(pw1[mxs[zx2]],pw2[mxs[zx2]])]; dfs3(zx,-1,hs); if(zx2) dfs3(zx2,-1,hs); int cnt=0; for(auto i=mp.begin();i!=mp.end();++i) ans[++cnt]=(*i).second; sort(ans+1,ans+1+cnt); write(cnt),putchar('\n'); for(register int i=1;i<=cnt;++i) write(ans[i]),putchar('\n'); return 0; }👍 6 -
@ 2022-7-7 10:43:22
#034 2022.7.7
标签：网络流。
Statement
有 个酿酒点和 个存酒点。对于第 个酿酒点，生产 （ 为实数）升酒需要花费 ，最多能生产 升酒。对于第 个存酒点，其最多能存储 升酒。每个酿酒点生产酒后需立即运至该酿酒点可到达的存酒点，每个酿酒点可到达的存酒点已知并给出。求：1. 所有酿酒点最大一共能产生多少酒 2. 在酿酒量达到最大值时花费的最小值为多少，以分数形式给出。
Solution
Solution
第一问建图后直接最大流即可得出。
酿酒代价为二次函数不易于计算，一个自然的想法是将这个二次函数从定义域上切割为若干段，将每一段内的部分近似为一个一次函数，然后就可以对于每一段建立一条对应的边，跑费用流即可。由于此处二次函数斜率递增，定义域靠前的段在代价上优于靠后的段，因此不需要考虑取这些段的先后顺序而可能带来的不合法取法。
但是此题要求输出分数，也就是不允许误差的存在。我们发现上面的做法分的段数越多，结果误差就越小，当每一段的长度无线接近于零，段数接近正无穷时误差即可消除。此时每一段内的一次函数就成为了该二次函数的导数：。
虽然解决了误差问题，但是段数达到了正无穷，我们无法直接对于每一段建边跑费用流。但是我们发现，若假设存酒点容量无穷，即只考虑产酒点总产量而不考虑存酒点限制的情况下，所有的最优方案一定是这样的：存在一个实数 作为阈值，每一个产酒点对应的花费二次函数上导数小于 的部分对应的定义域大小即为该产酒点产量。贪心策略下显然成立。
因此我们考虑构建函数 表示当阈值为 时，不考虑存酒点限制情况下的产酒点总产量。若令 表示阈值为 时第 个产酒点的产量，可以发现 $F_i(x) = \frac 1 {2a_i} x - \frac {b_i} {2a_i} (x \in [b_i,~2 a_i c_i + b_i])$。而 ，所以 应当由 个一次函数首尾相连形成。
该阈值与费用流 SPFA 跑出的 功能类似，若要模拟费用流过程，我们可以令阈值从 开始不断增长，每次更改阈值后重新通过 计算每条边的对应流量。费用流过程中还可将存酒点的流量限制加入，从而算出考虑存酒点限制情况下的总产量。
由于不允许存在精度误差因此我们无法做到真正模拟该过程，但是通过这个思路我们发现在阈值不断增加的过程中，存酒点总是先尽可能多地存酒，直至其容量达到上限后对部分酿酒点的产量产生限制。也就是说，我们可以通过 结合网络流得到 表示考虑存酒点容量限制的情况下，阈值为 时的总产量。 只会在 的基础上多 个端点，其图像由 个一次函数首尾相连形成。
但是 不像 可以直接通过计算得出， 的每一个点都需要网络流计算得出。不过我们发现 的大部分图像呈现上凸壳的形态，我们可以在定义域上分治得到整个图像：令 过程查找横坐标在 间的所有端点位置，我们在 和 上分别用网络流算出坐标，并结合残量网络算出斜率，可得两个端点处的一次函数。取这两个一次函数的交点，令其为 ，计算 处的一次函数，若与两端的一次函数相同则说明 范围内已再无端点，否则向 和 递归求解。但是注意到 可能等于零，也就是说一些一次函数可能出现斜率无穷的情况，因此需要在 处强制断开，在 段分开分治求解。
计算出 的图像后，通过计算其积分即可得到最终答案。
Code
/** * @file 2138.cpp * @author Macesuted (i@macesuted.moe) * @date 2022-07-05 * * @copyright Copyright (c) 2022 * */ #include <bits/stdc++.h> using namespace std; #ifndef LOCAL #define endl '\n' #endif bool mem1; #define maxn 105 #define eps 1e-9 #define feps 1e-11 bool con[maxn][maxn]; int n, m, a[maxn], b[maxn], c[maxn], d[maxn]; class Frac { private: int64_t x, y; int64_t gcd(int64_t a, int64_t b) { return b ? gcd(b, a % b) : a; } public: Frac(int64_t x_ = 0, int64_t y_ = 1) { int64_t g = gcd(x_, y_); x = x_ / g, y = y_ / g; } operator double() { return (double)x / y; } operator int64_t() { return x / y; } Frac operator+(const Frac& o) const { return Frac(x * o.y + y * o.x, y * o.y); } Frac operator-(const Frac& o) const { return Frac(x * o.y - y * o.x, y * o.y); } Frac operator*(const Frac& o) const { return Frac(x * o.x, y * o.y); } Frac operator/(const Frac& o) const { return Frac(x * o.y, y * o.x); } bool operator==(const Frac& o) const { return x == o.x && y == o.y; } Frac& operator+=(const Frac& o) { return *this = *this + o; } Frac& operator-=(const Frac& o) { return *this = *this - o; } Frac& operator*=(const Frac& o) { return *this = *this * o; } Frac& operator/=(const Frac& o) { return *this = *this / o; } void print(void) { if (y < 0) x = -x, y = -x; return cout << x << '/' << y, void(); } }; typedef pair<Frac, Frac> pff; class Dinic { private: struct Edge { int to, rev; double cap; }; vector<vector<Edge>> graph; vector<vector<Edge>::iterator> cur; vector<int> dist; queue<int> que; bool bfs(void) { for (int i = 1; i <= n + m + 2; i++) dist[i] = -1, cur[i] = graph[i].begin(); que.push(n + m + 1), dist[n + m + 1] = 0; while (!que.empty()) { int p = que.front(); que.pop(); for (auto i : graph[p]) if (i.cap > feps && !~dist[i.to]) dist[i.to] = dist[p] + 1, que.push(i.to); } return ~dist[n + m + 2]; } double dfs(int p, double rest) { if (rest < feps || p == n + m + 2) return rest; double use = 0, c; for (auto i = cur[p]; i != graph[p].end() && rest > feps; i++) { cur[p] = i; if (dist[p] + 1 != dist[i->to] || i->cap < feps) continue; if ((c = dfs(i->to, min(rest, i->cap))) < feps) dist[i->to] = -1; i->cap -= c, graph[i->to][i->rev].cap += c, use += c, rest -= c; } return use; } public: void addEdge(int from, int to, double cap) { return graph[from].push_back(Edge{to, (int)graph[to].size(), cap}), graph[to].push_back(Edge{from, (int)graph[from].size() - 1, 0}); } pff dinic(double lim) { graph.clear(), graph.resize(n + m + 3), cur.resize(n + m + 3), dist.resize(n + m + 3); for (int i = 1; i <= n; i++) if (a[i] == 0) { if (b[i] < lim) addEdge(n + m + 1, i, c[i]); } else addEdge(n + m + 1, i, min((lim - b[i]) / 2. / a[i], (double)c[i])); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (con[i][j]) addEdge(i, n + j, 1e18); for (int i = 1; i <= m; i++) addEdge(n + i, n + m + 2, d[i]); while (bfs()) dfs(n + m + 1, 1e18); Frac K, B; for (int i = 1; i <= n; i++) if (dist[i] == -1) { if (a[i] == 0) { if (b[i] < lim) B += Frac(c[i]); } else if (lim > 2 * a[i] * c[i] + b[i]) B += Frac(c[i]); else if (lim > b[i]) K += Frac(1, 2 * a[i]), B -= Frac(b[i], a[i] * 2); } for (int i = 1; i <= m; i++) if (~dist[n + i]) B += Frac(d[i]); return {K, B}; } } net; vector<pff> nodes; void solve(pff l, pff r) { if (l == r) return; Frac mid = (l.second - r.second) / (r.first - l.first); pff fml = net.dinic((double)mid - eps), fmr = net.dinic((double)mid + eps); if (l == fml) return nodes.emplace_back(mid, fml.first * mid + fml.second), void(); return solve(l, fml), solve(fmr, r); } void solve(void) { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i]; for (int i = 1; i <= m; i++) cin >> d[i]; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> con[i][j]; cout << int64_t(net.dinic(1e18).second) << endl; nodes.emplace_back(Frac(), Frac()); for (int i = 1; i <= 3; i++) { auto l = net.dinic(i - 1 + eps), r = net.dinic(i - eps); solve(l, r); nodes.emplace_back(Frac(i), Frac(i) * r.first + r.second); } solve(net.dinic(3 + eps), net.dinic(1e18)); Frac ans; for (int i = 1; i < (int)nodes.size(); i++) { pff f1 = net.dinic((double)nodes[i - 1].first + eps), f2 = net.dinic((double)nodes[i].first - eps), f3 = net.dinic((double)nodes[i].first + eps); ans += Frac(1, 2) * (nodes[i].second - f1.first * nodes[i - 1].first - f1.second) * (nodes[i - 1].first + nodes[i].first) + nodes[i].first * (f3.first * nodes[i].first + f3.second - f2.first * nodes[i].first - f2.second); } ans.print(), cout << endl; return; } bool mem2; int main() { ios::sync_with_stdio(false), cin.tie(nullptr); #ifdef LOCAL cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl; #endif int _ = 1; while (_--) solve(); #ifdef LOCAL cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl; #endif return 0; }❤️ 6👍 6-
@ 2022-7-12 16:30:18
是网络流还是网络瘤啊
-
-
@ 2022-6-30 7:29:45
#033 2022.6.30
标签：构造，*3500
给定一个 的方格图，每个格子都是黑色或白色。有些格子已经被涂色了，你要给剩下的格子涂色，使得黑色格子和白色格子分别组成连通块。构造一种方案或判断无解。
保证已经被涂色的格子没有公共点或公共边。
，多组数据，数据组数 ，保证 。
题解
如果四个边界上没有格子被染色，是一个经典套路，考虑构造“梳子”状的图案，如图 1：
因为任意两个限制颜色的格子不八联通，这种方案一定是可行的。
然后考虑如果边界上有限制颜色的格子。若边界上存在形如
BWBW的序列，是一定无解的，如图 2（格子上有“限制”二字表示这个格子颜色固定）：
对于不存在形如
BWBW序列的情况，不难发现，我们一定可以找到完整的一个边界（上/下/左/右），这条边上可以全部赋成同一个颜色，而且它对面那条边界上至少有一个点是不同的颜色。不妨把这个完整的边界上的颜色当成蓝色，参考图 1 “梳子”型构造的蓝色部分，给它安排好。以保证蓝色的格子相互之间可以连通了。现在处理红色格子，可以列举出如下三个不合法的情况，我们一一解决：- 边框被蓝色包围了，部分边框上的红色与梳子的条纹不联通。
- 接近边框位置（第 和第 行）的格子不联通。
- 红色梳子条纹不联通。
图 3 的三个例子分别对应了上面的三种不合法情况：
实际上这三种情况都可以通过简单的调整实现：
- 把下面也变成蓝色。（显然）
- 直接把道路打通就可以了，因为旁边的蓝色一定是连通的（考虑
BWBW情况已经没有了，如果不联通就扩充直到顶到一个限制红色的格子门口）。 - 打穿一个蓝色条纹即可，这一步在实现情况二之后进行，就无需考虑被打穿的蓝色条纹左右不联通了（两边的条纹会沿着一条边界连起来）。
此外还有很多零零散散的细节，例如解决这三种情况的顺序，等等。
代码（长代码注意）
#include<bits/stdc++.h> #define int long long using namespace std; bool Begin; const int max_n=502; inline int read(){ int x=0;bool w=0;char c=getchar(); while(c<'0' || c>'9') w|=c=='-',c=getchar(); while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return w?-x:x; } inline void write(int x){ putchar(x==2?'B':'W'); } inline int reads(){ char c=getchar(); while(c!='B' && c!='W' && c!='.') c=getchar(); if(c=='B') return 2; if(c=='W') return 3; return 0; } int n,m,cntr; int a[max_n][max_n],ans[max_n][max_n]; int Tmp[max_n][max_n]; inline void rotate(){ for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j) Tmp[i][j]=a[i][j]; for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j) a[j][n-i+1]=Tmp[i][j]; for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j) Tmp[i][j]=ans[i][j]; for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j) ans[j][n-i+1]=Tmp[i][j]; swap(n,m),++cntr; } inline void clear(){ cntr=0; for(register int i=0;i<=n;++i) for(register int j=0;j<=m;++j) a[i][j]=ans[i][j]=a[j][i]=ans[j][i]=0; } inline int calc(){ int res=0; for(register int p=1;p<=2;++p){ for(register int i=2;i<=m;++i) if(!ans[1][i]) ans[1][i]=ans[1][i-1]; for(register int i=2;i<=n;++i) if(!ans[i][m]) ans[i][m]=ans[i-1][m]; for(register int i=m-1;i;--i) if(!ans[n][i]) ans[n][i]=ans[n][i+1]; for(register int i=n-1;i;--i) if(!ans[i][1]) ans[i][1]=ans[i+1][1]; if(!ans[1][1]) ans[1][1]=2; } for(register int i=2;i<=m;++i) if(ans[1][i]!=ans[1][i-1]) ++res; for(register int i=2;i<=n;++i) if(ans[i][m]!=ans[i-1][m]) ++res; for(register int i=m-1;i;--i) if(ans[n][i]!=ans[n][i+1]) ++res; for(register int i=n-1;i;--i) if(ans[i][1]!=ans[i+1][1]) ++res; return res; } inline bool Nice(){ bool ok=0; for(register int i=1;i<=n;++i){ if(ans[i][1]!=ans[1][1]) return 0; if(i>1 && i<n && ans[i][m]!=ans[1][1]) ok=1; } return ok; } int Red,Blue; inline void findroad(int x,int y){ if(ans[x-1][y]==Red || ans[x+1][y]==Red || ans[x][y+1]==Red) return; int X1=(x==2?1:n); if(y<=m-2 && ans[X1][y+2]==Red){ ans[X1][y]=ans[X1][y+1]=Red; return; } int X2=(x==2?2:n-1); if(y<=m-2 && ans[X2][y+2]==Red){ ans[X2][y+1]=Red; return; } int X3=(x==2?3:n-2),X4=(x==2?4:n-3); if(a[X4][y]!=Blue){ ans[X3][y]=Red; return; } int Y=(y<=m-2?y+1:y-1); ans[X2][Y]=ans[X3][Y]=Red; } inline void bigroad(int x){ for(register int j=2;j<=4;++j){ bool ok=1; for(register int i=x-1;i<=x+2;++i) if(a[i][j]==Blue){ ok=0; break; } if(ok){ ans[x][j]=ans[x+1][j]=Red; return; } } for(register int i=x-1;i<=x+2;++i) if(!a[i][3]) ans[i][3]=Red; if(a[x-1][3]){ ans[x-1][2]=Blue, ans[x][4]=Red; } if(a[x+2][3]){ ans[x+2][2]=Blue, ans[x+1][4]=Red; } if(a[x][3] || a[x+1][3]){ ans[x][2]=ans[x+1][2]=Red; } } inline void buildroad(){ int fr=0,ls=0; for(register int i=1;i<=n;++i) if(ans[i][m]==Red){ if(!fr) fr=i; ls=i; } if(!fr || (ls>3 && fr<n-2)) return; if(ls<=3 && a[4][m-1]==Blue){ ans[3][m]=ans[4][m]=ans[5][m]=Red; return; } if(fr>=n-2 && a[n-3][m-1]==Blue){ ans[n-4][m]=ans[n-3][m]=ans[n-2][m]=Red; return; } int x=(ls<=3?2:n-2); for(register int i=x;i<=x+1;++i) for(register int j=m-1;j<=m;++j) if(!a[i][j]) ans[i][j]=Red; } bool End; #define File "" signed main(){ // #ifndef ONLINE_JUDGE // freopen(File ".in","r",stdin); // freopen(File ".out","w",stdout); // #endif for(register int T=read();T;--T,clear()){ n=read(),m=read(); for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j) a[i][j]=ans[i][j]=reads(); int tmp=calc(); if(tmp>=4){ puts("NO"); continue; } if(tmp>0) while(!Nice()) rotate(); Blue=ans[1][1],Red=Blue^1; for(register int i=2;i<n;++i) for(register int j=2;j<m;++j) if(!a[i][j]) ans[i][j]=(i%4>1?Blue:Red); for(register int i=1;i<n;++i) if(ans[i][m-1]==ans[i+1][m] && ans[i+1][m-1]==ans[i][m] && ans[i][m]!=ans[i+1][m]){ if(!a[i][m]) ans[i][m]^=1; else ans[i+1][m]^=1; } buildroad(); for(register int i=2;i<m;++i){ if(a[2][i]==Red) findroad(2,i); if(a[n-1][i]==Red) findroad(n-1,i); } for(register int i=6;i<=n-6;i+=4) if(ans[i][m]==Blue || ans[i+1][m]==Blue) bigroad(i); while(cntr%4!=0) rotate(); puts("YES"); for(register int i=1;i<=n;++i){ for(register int j=1;j<=m;++j) write(ans[i][j]); putchar('\n'); } } return 0; }👍 7❤️ 3 -
@ 2022-6-29 8:58:29
#032 2022.6.29
标签:字符串，lyndon 分解，exkmp。
Statement
给定一个串 ，求每个前缀的最小表示法。
。
Solution
Solution
考虑 lyndon 分解，如果我们对每个前缀都跑一遍 lyndon 分解的话，答案应该是最后一个开头 的 lyndon 串。
这样不优秀啊，但是我们仍然考虑 lyndon 分解。
假设我们现在维护的是 ，仍然维护指针 。
我们其实当前位置要加入的一个字符 的最小表示法的开头只会有两种情况，一种是在我的当前开始的位置 ，一种是在我加入的这个 里面的。
在 里面的话，你考虑他最终的表示法会是什么样子，比如 ，那么最终他会是 。
你仔细发现，反正我没发现，然后你发现如果你去掉最后的 个字符，他就会变成 ，然后这就是一个已经求解过的答案了，他是 的最小表示法。
现在我们需要根据 和 的大小进行分类。
如果 ，那么根据 lyndon 串的性质，那么 仍然是一个 lyndon 串，那么此时的 就是我们的 。
如果 ，那么之前的 lyndon 串被划分了出来，但是当前位置仍然不知道，于是我们将其放到后面进行求解。
如果 ，那么可以选择两种位置，首先就是当前的 可以作为 ，另一种是，先前循环节中 的对应位置 的答案向后移一个循环节的对应位置 。
那么需要比较的为 和 $S[(ans_j + k - j) \dots k] + S[1\dots ans_{j} + k - j - 1]$ 的字典序大小。
首先我们只会在 的时候遇到这种情况，那么 和 肯定都是相同的。
如下图：
也就是说上面的 和 一定是相同的。
然后你分着来比较，先比较 和与他对应长度的那一部分。
也就是图中画着绿线的那一部分，然后再比较后面的剩下部分就好了。
这样你发现，每次都是将一个子串 与原串的一个前缀 进行比较。
那么我们可以使用 函数，判断后缀 与原串的一个 lcp 长度判断是否再比较范围内，并找到这个不同即可。
使用 可以求解。
于是直接跑 Duval 算法就好了，复杂度 ，真神仙。
// 德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱 // 德丽莎的可爱在于德丽莎很可爱，德丽莎为什么很可爱呢，这是因为德丽莎很可爱！ // 没有力量的理想是戏言，没有理想的力量是空虚 // Problem: P5334 [JSOI2019]节日庆典 // Contest: Luogu // Memory Limit: 500 MB // Time Limit: 1000 ms // The Author : Pt #include <bits/stdc++.h> using namespace std; namespace io { const int SIZE = (1 << 21) + 1; char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr; #define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++) inline void flush () { fwrite (obuf, 1, oS - obuf, stdout); oS = obuf; } inline void putc (char x) { *oS ++ = x; if (oS == oT) flush (); } template <class I> inline void gi (I &x) { for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1; for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f; } string getstr(void) { string s = ""; char c = gc(); while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = gc(); while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF))s.push_back(c), c = gc(); return s;} template <class I> inline void print (I x) { if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x; while (x) qu[++ qr] = x % 10 + '0', x /= 10; while (qr) putc (qu[qr --]); } struct Flusher_ {~Flusher_(){flush();}}io_flusher_; } using io :: gi; using io :: putc; using io :: print; #define V inline void #define I inline int template<class T> bool chkmin(T &a, T b) { return a > b ? (a = b, true) : false; } template<class T> bool chkmax(T &a, T b) { return a < b ? (a = b, true) : false; } #define rep(i, l, r) for (int i = (l); i <= (r); i++) #define repd(i, l, r) for (int i = (l); i >= (r); i--) const int N = 3e6 + 5; char S[N]; int z[N], n, ans[N]; void exkmp() { z[1] = n; for (int i = 2, l = 0, r = 0; i <= n; i++) { if (i <= r) z[i] = min(z[i - l + 1], r - i + 1); while (i + z[i] <= n && S[i + z[i]] == S[1 + z[i]]) ++ z[i]; if (i + z[i] - 1 > r) r = i + z[l = i] - 1; } } int compare(int x,int y,int r) { if (x == y) return x; int zz = z[x + r - y + 1]; if (zz < y - x) return S[x + r - y + 1 + zz] < S[1 + zz] ? x : y; zz = z[y - x + 1]; if (zz < x - 1) return S[1 + zz] < S[y - x + 1 + zz] ? x : y; return x; } void solve() { int i = 1; while (i <= n) { int j = i, k = i + 1; if (!ans[i]) ans[i] = i; while (k <= n && S[j] <= S[k]) { if (S[j] < S[k]) { if (!ans[k]) ans[k] = i; j = i; ++k; } else { if (!ans[k]) { if (ans[j] < i) ans[k] = i; else ans[k] = compare(i, ans[j] + k - j, k); } ++k; ++j; } } int len = k - j; while (i <= j) i += len; } } signed main () { #ifdef LOCAL_DEFINE freopen("input.txt", "r", stdin); #endif cin >> (S + 1); n = strlen(S + 1); exkmp(); solve(); rep (i, 1, n) cout << ans[i] << " "; #ifdef LOCAL_DEFINE cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; #endif return 0; }👍 9❤️ 5-
@ 2022-6-29 12:26:32好耶 终于更新了
-
-
@ 2022-5-4 15:30:47#031 2022.5.4
标签：背包，笛卡尔树。
题目大意
给一个异形的棋盘，底对齐宽为 ，高度 互不相同，求放置 个车互不攻击的方案数。这里攻击定义为两车处在同一行或同一列，而且中间有连续的格子。
。
题解
考虑一个较低的列，它将区间划分为左右两边，高于这个列高的位置在左右两边互不攻击。
找到全局最低的列，递归地跑两边的背包（棋子数，方案数），然后合并左右区间的背包，剩下的部分是在一个与该最低列同高的，宽度为区间长度减去已经选的列的矩形上放置 个车，这个东西可以很快地组合数（选 行 列然后选择一种排列代表棋子的位置）：
将合并得到的背包和当前的决策再做一遍卷积，得到当前区间的背包。
由于 比较小，暴力卷就行了。
找区间最小值的过程实际上就是一个小根笛卡尔树，所以 预先建立笛卡尔树然后在树上跑这个背包的过程即可。
注意在递归过程中子区间当前结点的决策高度应该是当前列的高度减去上次划分的高度（笛卡尔树的父节点）。
然后如果刚开始想到用最小值划分区间类似的东西，就可以建出笛卡尔树来辅助思考。
code
const int maxn = 510, maxc = 1e6 + 10, mod = 1e9 + 7; inline int inc(int x, int y) { return (x += y) < mod ? x : x - mod; } inline int dec(int x, int y) { return (x -= y) < 0 ? x + mod : x; } inline int mul(int x, int y) { return 1ll * x * y % mod; } inline int qp(int x, int y) { int ret = 1 % mod; for(; y; y >>= 1) { if(y & 1) ret = mul(ret, x); x = mul(x, x); } return ret; } int a[maxn], ls[maxn], rs[maxn], siz[maxn], root; int f[maxn][maxn], tmp[maxn]; int fac[maxc], invF[maxc]; int n, k; inline int C(int x, int y) { return mul(fac[x], mul(invF[x - y], invF[y])); } inline int calc(int x, int y, int k) { if(min(x, y) < k) return 0; return mul(mul(C(x, k), C(y, k)), fac[k]); } void dfs(int cur, int pre) { siz[cur] = 1; if(ls[cur]) dfs(ls[cur], cur), siz[cur] += siz[ls[cur]]; if(rs[cur]) dfs(rs[cur], cur), siz[cur] += siz[rs[cur]]; memset(tmp,0,sizeof(tmp)); rep(i,0,min(siz[ls[cur]],k)) rep(j,0,min(k - i,siz[rs[cur]])) tmp[i + j] = inc(tmp[i + j], mul(f[ls[cur]][i], f[rs[cur]][j])); rep(i,0,min(siz[cur],k)) rep(j,0,min(siz[cur] - 1, i)) f[cur][i] = inc(f[cur][i], mul(tmp[j], calc(siz[cur] - j, a[cur] - a[pre], i - j))); } signed main() { n = read(); k = read(); int c = n; rep(i,1,n) a[i] = read(), c = max(c, a[i]); if(n < k) { puts("0"); return 0; } // factor & inv_factor fac[0] = 1; rep(i,1,c) fac[i] = mul(fac[i - 1], i); invF[c] = qp(fac[c], mod - 2); per(i,c - 1,0) invF[i] = mul(invF[i + 1], i + 1); // build cartesian tree stack<int> stk; rep(x,1,n) { int lst = 0; while(!stk.empty() && a[stk.top()] > a[x]) lst = stk.top(), stk.pop(); if(stk.empty()) root = x; else rs[stk.top()] = x; ls[x] = lst; stk.push(x); } f[0][0] = 1; dfs(root, 0); printf("%d\n", f[root][k]); return 0; }👍 10👀 2-
@ 2022-6-1 14:36:48
Hydro 每月一题。
-
@ 2022-6-22 15:04:06
每月一题
-
-
@ 2022-4-5 7:04:10
#030 2022.4.5
标签：最短路。
Statement
给出一个 个点 条边的无向图，每条边在 时刻出现， 时刻消失。 时刻时你在 号点上，每一时刻你都需要经过一条边移动到距离为 的另一个点上，不能停留在一个点上不动。每个点和每条边均可经过多次。问最早到达 号点的时间，或判断无法到达 号点。
Solution
Solution
我们发现若我们在 时刻从 走到 ，我们可以在这一条边上反复横跳让我们在 时刻均能到达 ，直到该边消失。由于这些能到达 的时刻奇偶性均相同，因此考虑将每个点拆分为两个，一个为奇点一个为偶点，每次到达奇点时的时刻为奇数，到达偶点的时刻为偶数。对于一条 向 的边，拆点后即为 的奇点向 的偶点连边和 的偶点向 的奇点连边。
考虑在拆完点后得到的图上跑最短路，但是将最短路状态记在点上是不妥的，因为点是不会消失的，因此无法判断长于最短路的某一个路径长度是否合法。考虑将最短路状态记在边上，对每条有向边记录其最早的到达这条边起点的时间。到达一个点的最早时间即为他的所有入边的最短路的最小值加一。
Code
/** * @file 827F.cpp * @author Macesuted (i@macesuted.moe) * @date 2022-04-03 * * @copyright Copyright (c) 2022 * @brief * My Tutorial: https://macesuted.moe/article/cf827f * */ #include <bits/stdc++.h> using namespace std; namespace IO { const int SIZE = 1 << 20; char Ibuf[SIZE], *Il = Ibuf, *Ir = Ibuf, Obuf[SIZE], *Ol = Obuf, *Or = Ol + SIZE - 1; int cache1[100], cache2[100]; char isspace(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\v' || c == '\f' || c == '\r'; } char iseoln(char c) { return c == '\n' || c == '\r'; } void fill(void) { return Ir = (Il = Ibuf) + fread(Ibuf, 1, SIZE, stdin), void(); } void flush(void) { return fwrite(Obuf, 1, Ol - Obuf, stdout), Ol = Obuf, void(); } char buftop(void) { return Ir == Il && (fill(), 1), *Il; } char getch(void) { return Il == Ir ? fill(), Il == Ir ? EOF : *Il++ : *Il++; } void putch(char x) { return *Ol++ = x, Ol == Or && (flush(), 1), void(); } template <typename T = int> T read(void) { T x = 0, f = +1; char c = getch(); while (c < '0' || c > '9') (c == '-') && (f = -f), c = getch(); while ('0' <= c && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getch(); return x * f; } template <typename T> void write(T x) { if (!x) return putch('0'); if (x < 0) putch('-'), x = -x; int top = 0; while (x) cache1[top++] = x % 10, x /= 10; while (top) putch(cache1[--top] ^ 48); return; } template <typename T> void writeDouble(T x, int dep = 10) { if (x < 0) putch('-'), x = -x; int64_t fx = x; x -= fx; for (int i = 0; i < dep; i++) cache2[i] = (x *= 10), x -= int(x); if (int(x * 10) > 4) { cache2[dep - 1]++; for (int i = dep - 1; i; i--) if (cache2[i] == 10) cache2[i] = 0, cache2[i - 1]++; if (cache2[0] == 10) cache2[0] = 0, fx++; } write(fx), putch('.'); for (int i = 0; i < dep; i++) putch(cache2[i] ^ 48); return; } string getstr(const string& suf = "") { string s = suf; while (isspace(buftop())) getch(); for (char* p = Il; Il != Ir; fill(), p = Il) { while (Il < Ir && !isspace(*Il) && *Il != EOF) Il++; s.append(p, Il); if (Il < Ir) break; } return s; } string getline(const string& suf = "") { string s = suf; while (iseoln(buftop())) getch(); for (char* p = Il; Il != Ir; fill(), p = Il) { while (Il < Ir && !iseoln(*Il) && *Il != EOF) Il++; s.append(p, Il); if (Il < Ir) break; } return s; } void putstr(string str, int begin = 0, int end = -1) { if (end == -1) end = str.size(); for (int i = begin; i < end; i++) putch(str[i]); return; } struct Flusher_ { ~Flusher_() { flush(); } } io_flusher_; } // namespace IO using IO::getch; using IO::getline; using IO::getstr; using IO::putch; using IO::putstr; using IO::read; using IO::write; using IO::writeDouble; bool mem1; #define maxn 500005 typedef tuple<int, int, int> tiii; vector<vector<tiii>> graph; vector<vector<tiii>::iterator> cur; int dist[maxn]; void addEdge(int x, int y, int l, int r) { return l <= r && (graph[x].emplace_back(l + (l & 1), r - (r & 1), y), graph[y].emplace_back(l + !(l & 1), r - !(r & 1), x), 1), void(); } void solve(void) { int n = read(), m = read(); graph.resize(2 * n + 1), cur.resize(2 * n + 1); for (int i = 1; i <= m; i++) { int x = read(), y = read(), l = read(), r = read() - 1; addEdge(x, y + n, l, r), addEdge(y, x + n, l, r); } for (int i = 1; i <= 2 * n; i++) sort(cur[i] = graph[i].begin(), graph[i].end()); memset(dist, 0x3f, sizeof(dist)), dist[1] = 0; static priority_queue<tiii, vector<tiii>, greater<tiii>> que; while (!que.empty()) que.pop(); while (cur[1] != graph[1].end() && get<0>(*cur[1]) == 0) que.emplace(1, get<1>(*cur[1]) + 1, get<2>(*cur[1])), cur[1]++; while (!que.empty()) { auto [l, r, x] = que.top(); que.pop(), dist[(x - 1) % n + 1] = min(dist[(x - 1) % n + 1], l); for (auto& i = cur[x]; i != graph[x].end() && get<0>(*i) <= r; i++) if (get<1>(*i) >= l) que.emplace(max(l, get<0>(*i)) + 1, get<1>(*i) + 1, get<2>(*i)); } return write(dist[n] == 0x3f3f3f3f ? -1 : dist[n]), putch('\n'); } bool mem2; int main() { ios::sync_with_stdio(false); #ifdef MACESUTED cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl; #endif int _ = 1; while (_--) solve(); #ifdef MACESUTED cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl; #endif return 0; }👍 10❤️ 6-
@ 2022-4-15 22:18:26弱弱地问一下，后面的标签是如何打出来的啊？
-
@ 2022-5-3 9:13:15
Hydro 每月一题（逃
-
-
@ 2022-3-30 9:07:40
#029 2022.3.30
标签：数论。
题目大意
给一个正整数 ,求 。
。
题解
设 , 对于满足题意的 有 ，其中 。
此时 。
对 ，枚举 ，求 的非 约数个数和即可。
对 实际上就是约数。
这种枚举是不漏的，因为我们对于每个 求出了所有可能的 。
这种枚举是不重的，首先每个 对应唯一的 ，而对于每个 ，不同的 又能得到不同的 。
这种枚举的复杂度的表达式大概是
看起来是 (能过) ，我在 vp 的时候对着那张约数个数级别表格看了好久一度以为很难过，实际上是不高于 。而且随机数据下跑的非常快。
code
int test(ll x) { if(x == 0) return 0; int ret = 0; for(ll i = 1; i * i <= x; ++ i) { if(x % i == 0) ret += 2; if(x == i * i) -- ret; } return ret - 1; } int main() { ll n, ans = 0; scanf("%lld", &n); for(ll i = 1; i * i <= n; ++ i) { if(n % i != 0) continue; ll t = n / i; ans += test(i - 1) + 1; if(n == i * i) continue; ans += test(t - 1) + 1; } printf("%lld\n", ans); return 0; }关于复杂度
约数和函数：
这个东西在 的时候的阶的估计大概是这样的：
$$\sigma_k(n) \leq n ^ k \exp \{ (1 + o(1)) \frac{(\log n)^{1 - k}}{(1 - k)\log \log n} \} $$感觉这个东西没有初阶的证明方法。
姑且认为 $\sum_{d \mid n} \sqrt d \sim \mathcal{O}(\sqrt n \log n)$ 。
👍 9❤️ 5 -
@ 2022-3-29 7:27:40
#028 2022.3.29
标签：构造。
Statement
这是一道交互题。
已知 ，有一个未知数 （ ），你需要求出 的值。
有一个集合 。你可以进行不超过 次操作。每次操作可以是如下三种之一：
，表示求出 中 的倍数的个数 （）
，表示求出 中 的倍数的个数并将这些数从 中删去（ 是不会被删掉的） （）
，表示你知道了 （）
所有的 均为整数
Solution
Solution
交互题考虑分析操作和规模，对于 操作，我们发现如果 的倍数中有 ，那么最后删除的时候是不会删除 的，但是我们又可以使用 操作来得到集合中 的倍数。
如果 不是 的倍数，那么使用 操作之后再使用一次 操作得到的回复应该是 ，否则为 。
因此，我们有了一种暴力的思路，我们考虑对于 内所有质数，都执行一遍上面的操作，然后我们可以确定出 是由哪些质因子构成的，然后最后我们再询问这些质因子的次幂即可。
那么，这么做的操作次数为多少呢？
范围内的质数有 个，我们至少对每个质数都执行了两遍操作，然后还有最后找出数 又需要一些次数，超出规定的 操作次数。
考虑优化我们的交互策略，对质数进行根号分治。
将大于 的质数和小于 的质数分别进行处理。
对于大于 的质数，任何 都最多只会有一个 这么的质因数出现，否则就超出了值域 。
对于小于 的质数，只有 个质数。
对于这些质数，我们先进行之前的策略，得到 的小质数因子，并且询问出他应有的次幂。
可以计算出，这部分操作次数最多为 次。
然后执行完之后只会有 和 的大质数因子。
然后对于大质数，还拥有 个。
假设之前得到的小质数因子乘积 大于 。
那么这个数是个合数，直接询问所有大质数 是否存在，如果存在那么 。
这部分的操作次数最多为 。
如果 的话，那么证明我们的数 是个质数或者为 ，他就在后面的大质数因子中。
那么不能照搬上面的做法了，而直接暴力操作次数要乘二，就超了。
人类智慧，接下来的序列中只有 和大质数。
对大质数进行分块，每 个大质数分一块，每次连续删 个大质数。
然后询问 可以得到现在序列中数量，按理来说应该是每次减少 个，如果有一次减少的是 个，证明 在这一块中，然后暴力递归找即可。
这部分的操作次数最终也不会超过 。
实际上我调了一下块长为 ，因为我写丑了。
Code
// 德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱 // 德丽莎的可爱在于德丽莎很可爱，德丽莎为什么很可爱呢，这是因为德丽莎很可爱！ #include <bits/stdc++.h> #define int long long using namespace std; #define FOR(i, l, r) for(int i = (l); i <= r; ++i) #define REP(i, l, r) for(int i = (l); i < r; ++i) #define DFR(i, l, r) for(int i = (l); i >= r; --i) #define DRP(i, l, r) for(int i = (l); i > r; --i) #define FORV(i, ver) for(int i = 0; i < ver.size(); i++) #define FORP(i, ver) for(auto i : ver) template<class T>T wmin(const T &a, const T &b) {return a < b ? a : b;} template<class T>T wmax(const T &a, const T &b) {return a > b ? a : b;} template<class T>bool chkmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;} template<class T>bool chkmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;} inline int read() { int x = 0, f = 1; char ch = getchar(); while( !isdigit(ch) ) { if(ch == '-') f = -1; ch = getchar(); } while( isdigit(ch) ) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } return x * f; } const int N = 2e6; int n, vis[N], pr[N], tot, c[N], num; void prime(int n) { FOR (i, 2, n) { if (vis[i]) continue; pr[++tot] = i; for (int j = i; j <= n; j += i) vis[j] = 1; } } int A(int x) { cout << "A " << x << "\n"; cout.flush(); int qwq; cin >> qwq; return qwq; } void B(int x) { cout << "B " << x << "\n"; cout.flush(); int qwq; cin >> qwq; } void C(int x) { cout << "C " << x << "\n"; cout.flush(); exit(0); } signed main () { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); n = read(); prime(n); if (n == 1) { C(1); } int now = 1; FOR (i, 1, tot) { if (pr[i] > 316) break; int x = pr[i]; B(x); if ( A(x) == 1 ) { now = now * x; int gtr = x; while (1) { gtr *= x; if (gtr > n) break; if ( A(gtr) == 1 ) now *= x; else break; } } } if (now == 1) { int ans = 1; FOR (i, 1, tot) { if (pr[i] < 316) continue; c[++num] = pr[i]; } int siz = 86, bel = (num - 1) / siz + 1; int cnt = A(1); FOR (i, 1, bel) { int l = (i - 1) * siz + 1; int r = wmin(num, i * siz); int len = r - l + 1; FOR (j, l, r) { int x = c[j]; B(x); } int qaq = A(1); if (qaq == cnt - len) { cnt -= len; continue; } FOR (j, l, r) { int x = c[j]; int qwq = A(x); if (qwq) C(x); } } C(1); } FOR (i, 1, tot) { if (pr[i] < 316) continue; int x = pr[i]; if (x * now > n) break; if (A(x * now) == 1) C(x * now); } C(now); return 0; }❤️ 8👍 4👎 3👀 3🤣 3😕 2🌿 2🤔 2🕊️ 2🍋 2😄 2 -
@ 2022-3-27 7:49:49
#027 2022.3.27
标签：数据结构，平衡树，模拟。
Statement
维护一个长为 的 0/1 序列 ，有 个操作：
1 l r：把区间 的数变成 。2 l r：把区间 的数变成 。3 l r： 内所有数 ，变为 与 按位或的值，这些数同时进行这个操作。4 l r： 内所有数 ，变为 与 按位或的值，这些数同时进行这个操作。5 l r： 内所有数 ，变为 与 按位与的值，这些数同时进行这个操作。6 l r： 内所有数 ，变为 与 按位与的值，这些数同时进行这个操作。7 l r：查询区间 内的元素和。
强制在线。
Solution
Solution
我们显然无法使用平衡树直接维护每个点的单点信息，因为题目中给出的操作对于区间中的每一个元素均与它两边的元素进行了运算，难以直接维护每个单点的信息。
所以我们考虑将原序列拆分为一些区间，使之可以较方便地处理题目中给出的这些操作。
一个比较显然的想法是将原序列拆分为若干段同色的极长段。比如将 划分为 。容易发现这样划分之后，如果一个操作覆盖了某一个区间，我们可以方便地计算出该操作对该区间的影响：
- 1 操作： 所覆盖的 1 区间均变为 0 区间。
- 2 操作： 所覆盖的 0 区间均变为 1 区间。
- 3 操作： 所覆盖的 0 区间右端点 ，所覆盖的 1 区间左端点 。
- 4 操作： 所覆盖的 0 区间左端点 ，所覆盖的 1 区间右端点 。
- 5 操作： 所覆盖的 0 区间左端点 ，所覆盖的 1 区间右端点 。
- 6 操作： 所覆盖的 0 区间右端点 ，所覆盖的 1 区间左端点 。
同时，由于我们需要在下放标记前计算出某个询问区间对应的元素和，所以我们需要保证每一个区间均为极长区间，也就是不能让空区间留在平衡树中。
由于在整个过程中于平衡树上出现的区间数量是 级别的，所以我们可以在每个平衡树结点上记录其子树内最短的 0/1 区间的长度，在该长度达到 0 时暴力地向下搜索找到空区间并删除，对于每个空区间我们需要花费 的时间复杂度，因此总共花费在删除空区间操作上的时间是 级别的，可以接受。
根据上面提到的方法维护平衡树即可。
Code
编写代码用时 3h，调试用时 2h，使用指针版 FhqTreap，由于卡常使用了内存池并省去了回收内存操作。
下面是一些注意事项和建议：
- 写代码时务必多画图，仔细考虑每一个操作的边界情况。（即操作区间的左右端点所在区间是否需要被修改的情况）
- 由于代码较长建议每写完几个操作就进行简单的测试以检验其正确性。
- 如果 WA 并且找不到显然的错误，可以在每次操作结束后输出整棵平衡上的所有区间的信息，配合手动模拟或是暴力代码测试几组数据。
/** * @author Macesuted (i@macesuted.moe) * @copyright Copyright (c) 2021 * @brief * My solution: https://www.macesuted.cn/article/lg5066/ */ #include <bits/stdc++.h> using namespace std; namespace io { #define SIZE (1 << 20) char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr; inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); } inline char getch(void) { return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++); } inline void putch(char x) { *oS++ = x; if (oS == oT) flush(); return; } string getstr(void) { string s = ""; char c = getch(); while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch(); while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch(); return s; } void putstr(string str, int begin = 0, int end = -1) { if (end == -1) end = str.size(); for (register int i = begin; i < end; i++) putch(str[i]); return; } template <typename T> inline T read() { register T x = 0; for (f = 1, c = getch(); c < '0' || c > '9'; c = getch()) if (c == '-') f = -1; for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15); return x * f; } template <typename T> inline void write(const T& t) { register T x = t; if (!x) putch('0'); if (x < 0) putch('-'), x = -x; while (x) qu[++qr] = x % 10 + '0', x /= 10; while (qr) putch(qu[qr--]); return; } struct Flusher_ { ~Flusher_() { flush(); } } io_flusher_; } // namespace io using io::getch; using io::getstr; using io::putch; using io::putstr; using io::read; using io::write; #define maxn 3000005 #define INF 0x3f3f3f3f class FhqTreap { private: struct Node { int rank; int col; // 区间颜色 int sum; // 子树和 int siz[2]; // 子树内 0/1 区间数量 int tl, tr; // 区间左右端点 int deltaL, deltaR; // 1 区间左右端点偏移量 int minLen[2]; // 子树内最短 0/1 区间长度 Node *l, *r; // 平衡树左右孩子 Node(void) {} Node(int _rank, int _col, int _tl, int _tr) { rank = _rank; col = _col; tl = _tl, tr = _tr; l = r = NULL; reset(); } // 重新计算该点的单点信息 void reset(void) { siz[col] = 1, siz[!col] = 0; sum = col * (tr - tl + 1); deltaL = deltaR = 0; minLen[col] = tr - tl + 1, minLen[!col] = INF; return; } Node operator+(const Node& b) const { Node a = *this; a.sum += b.sum; a.siz[0] += b.siz[0], a.siz[1] += b.siz[1]; a.minLen[0] = min(a.minLen[0], b.minLen[0]), a.minLen[1] = min(a.minLen[1], b.minLen[1]); return a; } }; Node pool[10000000]; int tail = 0; Node* root; queue<Node*> needErase; // 需要被删除的结点 static const long long kMul = 0x9ddfea08eb382d69ULL; long long Seed = 1145141919810; inline long long fingerPrint(long long x) { return x *= kMul, x ^= x >> 47, x *= kMul, x ^= x >> 47, x *= kMul, x ^= x >> 47, x * kMul; } inline int frand(void) { return Seed += fingerPrint(Seed); } inline Node* newNode(int val, int l, int r) { return &(pool[tail++] = Node(frand(), val, l, r)); } inline void update(Node* p, int dl, int dr) { if (p == NULL) return; p->deltaL += dl, p->deltaR += dr; p->minLen[0] -= dl + dr, p->minLen[1] += dl + dr; p->sum += (dl + dr) * p->siz[1]; if (p->col == 1) p->tl -= dl, p->tr += dr; else p->tl += dr, p->tr -= dl; return; } void findEmpty(Node* p) { if (p == NULL) return; if (p->minLen[0] && p->minLen[1]) return; pushDown(p); if (p->tl > p->tr) needErase.push(p); findEmpty(p->l), findEmpty(p->r); return; } void eraseEmpty(void) { while (!needErase.empty()) { Node* p = needErase.front(); needErase.pop(); Node *nodeL = NULL, *treeM = NULL, *nodeR = NULL, *treeR = NULL; split1(root, root, treeR, p->tl - 1), split1(treeR, treeM, treeR, p->tl); split2(root, root, nodeL, p->tl - 2); if (p == treeM) nodeR = (p->l == NULL) ? p->r : p->l; else nodeR = treeM, nodeR->l = nodeR->r = NULL; // delete p; if (nodeL != NULL && nodeR != NULL) nodeL->tr = nodeR->tr, nodeL->reset(), /* delete nodeR, */ nodeR = NULL; merge(root, root, nodeL), merge(root, root, nodeR), merge(root, root, treeR); } return; } // void destroy(Node* p) { // if (p == NULL) return; // if (p->l != NULL) destroy(p->l); // if (p->r != NULL) destroy(p->r); // delete p; // return; // } void pushDown(Node* p) { if (!p->deltaL && !p->deltaR) return; if (p->l != NULL) update(p->l, p->deltaL, p->deltaR); if (p->r != NULL) update(p->r, p->deltaL, p->deltaR); p->deltaL = p->deltaR = 0; return; } inline void pushUp(Node* p) { p->reset(); if (p->l != NULL) *p = *p + *(p->l); if (p->r != NULL) *p = *p + *(p->r); return; } // 将对应区间左端点 <= p 的部分划分到 tree1，左端点 > p 的部分划分到 tree2 void split1(Node* root, Node*& tree1, Node*& tree2, int p) { if (root == NULL) return tree1 = tree2 = NULL, void(); pushDown(root); if (root->tl <= p) tree1 = root, split1(root->r, tree1->r, tree2, p); else tree2 = root, split1(root->l, tree1, tree2->l, p); return pushUp(root); } // 将对应区间右端点 <= p 的部分划分到 tree1，右端点 > p 的部分划分到 tree2 void split2(Node* root, Node*& tree1, Node*& tree2, int p) { if (root == NULL) return tree1 = tree2 = NULL, void(); pushDown(root); if (root->tr <= p) tree1 = root, split2(root->r, tree1->r, tree2, p); else tree2 = root, split2(root->l, tree1, tree2->l, p); return pushUp(root); } void merge(Node*& root, Node* tree1, Node* tree2) { if (tree1 == NULL) return root = tree2, void(); if (tree2 == NULL) return root = tree1, void(); if (tree1->rank < tree2->rank) pushDown(root = tree1), merge(root->r, tree1->r, tree2); else pushDown(root = tree2), merge(root->l, tree1, tree2->l); return pushUp(root); } void print(Node* root) { if (root == NULL) return; pushDown(root); if (root->l != NULL) print(root->l); cerr << '[' << root->tl << '~' << root->tr << ':' << root->col << ']'; if (root->r != NULL) print(root->r); return; } public: FhqTreap(void) { root = NULL; } void pushBack(int l, int r, int val) { Node* p = newNode(val, l, r); merge(root, root, p); return; } void opt1_2(int l, int r, int val) { Node *nodeL = NULL, *p = NULL, *nodeR = NULL, *treeR = NULL; split2(root, root, p, l - 1), split1(p, p, treeR, r); split1(p, nodeL, p, l - 1), split2(p, p, nodeR, r); if (nodeL != NULL) { if (nodeL->tr > r) nodeR = newNode(nodeL->col, r, nodeL->tr); nodeL->tr = l - 1, nodeL->reset(); } else split2(root, root, nodeL, l - 2); if (nodeR != NULL) nodeR->tl = r + 1, nodeR->reset(); else split1(treeR, nodeR, treeR, r + 1); // destroy(p); p = newNode(val, l, r); if (nodeL != NULL && p->col == nodeL->col) { p->tl = nodeL->tl, p->reset(); // delete nodeL; nodeL = NULL; } if (nodeR != NULL && p->col == nodeR->col) { p->tr = nodeR->tr, p->reset(); // delete nodeR; nodeR = NULL; } merge(root, root, nodeL), merge(root, root, p), merge(root, root, nodeR), merge(root, root, treeR); return; } void opt3(int l, int r) { r--; Node *treeM = NULL, *treeR = NULL, *node = NULL; split2(root, root, treeM, l - 1), split1(treeM, treeM, treeR, r); split1(treeM, node, treeM, l); if (node != NULL && node->col == 1) merge(root, root, node); else merge(treeM, node, treeM); node = NULL; split2(treeM, treeM, node, r - 1); if (node != NULL && node->col == 0) { if (node->tr > r) merge(treeR, node, treeR); else { merge(treeM, treeM, node); Node* nodeR = NULL; split1(treeR, nodeR, treeR, r + 1); merge(treeM, treeM, nodeR); } } else merge(treeM, treeM, node); if (treeM != NULL) update(treeM, 1, 0); merge(root, root, treeM), merge(root, root, treeR); findEmpty(root), eraseEmpty(); return; } void opt4(int l, int r) { l++; Node *treeM = NULL, *treeR = NULL, *node = NULL; split2(root, root, treeM, l - 1), split1(treeM, treeM, treeR, r); split1(treeM, node, treeM, l); if (node != NULL && node->col == 0) { if (node->tl < l) merge(root, root, node); else { merge(treeM, node, treeM); Node* nodeL = NULL; split2(root, root, nodeL, l - 2); merge(treeM, nodeL, treeM); } } else merge(treeM, node, treeM); node = NULL; split2(treeM, treeM, node, r - 1); if (node != NULL && node->col == 1) merge(treeR, node, treeR); else merge(treeM, treeM, node); if (treeM != NULL) update(treeM, 0, 1); merge(root, root, treeM), merge(root, root, treeR); findEmpty(root), eraseEmpty(); return; } void opt5(int l, int r) { r--; Node *treeM = NULL, *treeR = NULL, *node = NULL; split2(root, root, treeM, l - 1), split1(treeM, treeM, treeR, r); split1(treeM, node, treeM, l); if (node != NULL && node->col == 0) merge(root, root, node); else merge(treeM, node, treeM); node = NULL; split2(treeM, treeM, node, r - 1); if (node != NULL && node->col == 1) { if (node->tr > r) merge(treeR, node, treeR); else { merge(treeM, treeM, node); Node* nodeR = NULL; split1(treeR, nodeR, treeR, r + 1); merge(treeM, treeM, nodeR); } } else merge(treeM, treeM, node); if (treeM != NULL) update(treeM, 0, -1); merge(root, root, treeM), merge(root, root, treeR); findEmpty(root), eraseEmpty(); return; } void opt6(int l, int r) { l++; Node *treeM = NULL, *treeR = NULL, *node = NULL; split2(root, root, treeM, l - 1), split1(treeM, treeM, treeR, r); split1(treeM, node, treeM, l); if (node != NULL && node->col == 1) { if (node->tl < l) merge(root, root, node); else { merge(treeM, node, treeM); Node* nodeL = NULL; split2(root, root, nodeL, l - 2); merge(treeM, nodeL, treeM); } } else merge(treeM, node, treeM); node = NULL; split2(treeM, treeM, node, r - 1); if (node != NULL && node->col == 0) merge(treeR, node, treeR); else merge(treeM, treeM, node); if (treeM != NULL) update(treeM, -1, 0); merge(root, root, treeM), merge(root, root, treeR); findEmpty(root), eraseEmpty(); return; } int opt7(int l, int r) { Node *node = NULL, *p = NULL, *treeR = NULL; split2(root, root, p, l - 1), split1(p, p, treeR, r); int answer = 0; if (p != NULL) answer += p->sum; split1(p, node, p, l - 1); if (node != NULL) answer -= node->col * (l - node->tl); merge(p, node, p); node = NULL; split2(p, p, node, r); if (node != NULL) answer -= node->col * (node->tr - r); merge(p, p, node); merge(root, root, p), merge(root, root, treeR); return answer; } inline void print(void) { return print(root), cerr << endl, void(); } }; FhqTreap treap; int a[maxn]; int main() { int n = read<int>(), m = read<int>(); for (register int i = 1; i <= n; i++) a[i] = read<int>(); int last = 1; for (register int i = 2; i <= n; i++) if (a[i] != a[i - 1]) treap.pushBack(last, i - 1, a[i - 1]), last = i; treap.pushBack(last, n, a[n]); last = 0; while (m--) { int opt = read<int>(), l = last ^ read<int>(), r = last ^ read<int>(); if (opt == 1) treap.opt1_2(l, r, 0); else if (opt == 2) treap.opt1_2(l, r, 1); else if (opt == 3) treap.opt3(l, r); else if (opt == 4) treap.opt4(l, r); else if (opt == 5) treap.opt5(l, r); else if (opt == 6) treap.opt6(l, r); else write(last = treap.opt7(l, r)), putch('\n'); } return 0; }👍 6 -
@ 2022-3-26 7:08:42
#026 2022.3.26
标签：构造，贪心。
Statement
在数轴上给出 个点和 个询问，每个询问给出一个线段，初始放在 上，你需要移动该线段使得该线段能够依次包含所有的 个点，问线段移动总距离的最小值。
$1 \le n,m \le 2 \times 10^5,~0 \le l_i,r_i \le 10^9$
Solution
Solution
由于 与 相同，因此在固定询问线段长度 的情况下，可以将原问题中的询问线段变为位置在 上的单点， 个点变为 的线段，问题即转换为求移动该点使其依次经过每个区间的最短总距离。
结论 1：在一种移动方案中，若 时刻向 时刻移动的方向与 时刻向 时刻移动的方向相同，则 时刻的限制可以无视。
证明：令 时刻点所在位置为 ，以向右移动为例则若条件满足则说明 。固定 和 时所有在该两点间的移动方案总会经过 ，在经过 时满足 时刻限制即可。
结论 2：若两个相邻限制线段 ， 有交，则这两条线段的限制条件与一条 线段相同。
证明： 向 移动的过程中必定会经过他们交线段上的至少一个点，因此满足两条线段限制条件的方案必定满足交线段的限制条件。所有满足交线段限制条件的方案显然满足 时刻和 时刻的限制，因此满足交线段限制条件的方案必定满足原来的两条线段的限制条件。
当我们固定询问区间长度 时，通过结论 2 的约束，我们可以使得最终限制条件中任意两条相邻线段均不交。因此我们能够确定每一条线段（除了最后一条），该线段与下一条线段之间的移动方向。
结论 3：对于线段 ，若其到线段 的移动方向为左，则线段 的限制条件与 相同。
证明显然，根据贪心，离下一条线段最近的点必然不劣。
根据结论 3，我们可以把所有线段限制缩为点，问题转化为：询问一点与 个给定点依次相交的移动路径和。我们令第 个限制为 。
根据结论 1，我们发现若出现 的情况，则 将不会起约束作用。我们按上述限制删除无用限制后，发现限制总是满足： 或 。此时询问 的答案即为 $|lim_1 - l_q| + \sum_{i = 1}^{m - 1} | lim_i - lim_{i + 1} |$。
在固定 的情况下我们已经能够求解原问题了，考虑在不固定 时我们应该怎么做。我们考虑将所有询问离线后按照 排序，从小到达枚举 的同时维护限制条件下对应的答案。
我们可以将所有 分为左右两半，满足 的为左点，满足 的为右点。最终移动路径上的点一定为左右点相邻。所有的左点为原区间的右端点，所有的右点为原区间的左端点。由于原区间为 ，在 增大时左端点会向左移动，即所有右点在 增大 时会向左移动 。因此在询问的 增大时我们只要给全局所有的右点通过懒标记整体向左移即可。
但是由于右点向左移动最终会与左点相交，相交后根据结论 2 我们需要删除相交的两个点中的一个，删除一个点后会出现两个同类点相邻的情况，令未删除的点为 。当 为第一个限制或是最后一个限制时令 从左点变为右点或是从右点变为左点， 不为第一个或最后一个时删除 因为其值在 与 之间。上述操作完后即可重新回到正常状态。
令相邻两限制间的距离为他们初始时刻的距离，使用 维护所有相邻两限制间的距离，处理时间 时将所有距离不超过 的限制按照上述操作处理即可。由于每个时刻相邻两限制间的距离都会减一，因此最终答案即为 $|lim_1 - l_q| + \sum_{i = 1}^{m - 1} | lim_i - lim_{i + 1} | - (m - 1) \times tim$。全局维护相邻限制距离和即可。
需要注意的是当只剩下一个限制时，由于不存在所谓“下一步移动方向”，随时间推移该点会逐渐展开为线段。
时间复杂度 ，常数较大。
Code
/** * @file 4249.cpp * @author Macesuted (i@macesuted.moe) * @date 2022-03-25 * * @copyright Copyright (c) 2022 * @brief * My Tutorial: https://macesuted.moe/article/bzoj4249 * */ #include <bits/stdc++.h> using namespace std; namespace IO { const int SIZE = 1 << 20; char Ibuf[SIZE], *Il = Ibuf, *Ir = Ibuf, Obuf[SIZE], *Ol = Obuf, *Or = Ol + SIZE - 1, stack[32]; char isspace(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\v' || c == '\f' || c == '\r'; } void fill(void) { return Ir = (Il = Ibuf) + fread(Ibuf, 1, SIZE, stdin), void(); } void flush(void) { return fwrite(Obuf, 1, Ol - Obuf, stdout), Ol = Obuf, void(); } char buftop(void) { return Ir == Il ? fill(), *Il : *Il; } char getch(void) { return Il == Ir ? fill(), Il == Ir ? EOF : *Il++ : *Il++; } void putch(char x) { return *Ol++ = x, Ol == Or ? flush() : void(); } template <typename T> T read(void) { T x = 0, f = +1; char c = getch(); while (c < '0' || c > '9') c == '-' ? void(f = -f) : void(), c = getch(); while ('0' <= c && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getch(); return x * f; } template <typename T> void write(T x) { if (!x) putch('0'); if (x < 0) putch('-'), x = -x; int top = 0; while (x) stack[top++] = (x % 10) ^ 48, x /= 10; while (top) putch(stack[--top]); return; } string getstr(const string& suf = "") { string s = suf; while (isspace(buftop())) getch(); while (Il != Ir) { char* p = Il; while (Il < Ir && !isspace(*Il) && *Il != EOF) Il++; s.append(p, Il); if (Il < Ir) break; fill(); } return s; } void putstr(string str, int begin = 0, int end = -1) { if (end == -1) end = str.size(); for (int i = begin; i < end; i++) putch(str[i]); return; } struct Flusher_ { ~Flusher_() { flush(); } } io_flusher_; } // namespace IO using IO::getch; using IO::getstr; using IO::putch; using IO::putstr; using IO::read; using IO::write; bool mem1; #define maxn 200005 typedef pair<int, int> pii; set<pii> S, Sd; map<int, vector<pii>> ques; int a[maxn]; long long ans[maxn], answer = 0; template <typename T> T dec(T a) { return --a; } template <typename T> T inc(T a) { return ++a; } void insert(set<pii>::iterator p) { return answer += abs(p->second - inc(p)->second), Sd.emplace(abs(p->second - inc(p)->second), p->first), void(); } void erase(set<pii>::iterator p) { return answer -= abs(p->second - inc(p)->second), Sd.erase({abs(p->second - inc(p)->second), p->first}), void(); } void check(pii x, int tim) { auto p = S.find(x); if (p == S.begin() && p == dec(S.end())) return; if (p == S.begin()) { if (p->second == inc(p)->second) return S.erase(p), void(); if (inc(p)->second < p->second) S.erase(p), p = S.emplace(x.first, x.second + tim).first; return insert(p); } if (p == dec(S.end())) { if (p->second == dec(p)->second) return S.erase(p), void(); if (dec(p)->second < p->second) S.erase(p), p = S.emplace(x.first, x.second + tim).first; return insert(dec(p)); } return insert(--S.erase(p)); } void solve(void) { int n = read<int>(), m = read<int>(); for (int i = 1; i <= n; i++) { int l = read<int>(), r = read<int>(); ques[r - l].emplace_back(l, i); } for (int i = 1; i <= m; i++) S.emplace(i, a[i] = read<int>()); for (auto i = ++S.begin(); inc(i) != S.end(); i++) if ((dec(i)->second < i->second) == (i->second < inc(i)->second) || dec(i)->second == i->second || i->second == inc(i)->second) i = --S.erase(i); for (auto i = S.begin(); inc(i) != S.end(); i++) Sd.emplace(abs(i->second - inc(i)->second), i->first), answer += abs(i->second - inc(i)->second); int last = 0; while (!Sd.empty()) { int tim = Sd.begin()->first, ip = Sd.begin()->second; Sd.erase(Sd.begin()); if (tim != last) for (auto i = ques.begin(); i != ques.end() && i->first < tim; i = ques.erase(i)) { int t = S.begin()->second; if (S.begin()->second > inc(S.begin())->second) t -= i->first; for (auto j : i->second) ans[j.second] = answer + abs(t - j.first) - 1LL * ((int)S.size() - 1) * i->first; } last = tim; auto p = S.lower_bound({ip, 0}), q = inc(p); erase(p); if (p->second > q->second) { if (p != S.begin()) erase(dec(p)); q = S.erase(p); if (q != dec(S.end())) erase(q); check(*q, tim); } else { if (q != dec(S.end())) erase(q); p = --S.erase(q); if (p != S.begin()) erase(dec(p)); check(*p, tim); } } for (auto i : ques) for (auto j : i.second) if (S.begin()->second - (i.first - last) <= j.first && j.first <= S.begin()->second) ans[j.second] = 0; else ans[j.second] = min(abs(S.begin()->second - j.first), abs(S.begin()->second - (i.first - last) - j.first)); for (int i = 1; i <= n; i++) write(ans[i]), putch('\n'); return; } bool mem2; int main() { ios::sync_with_stdio(false); #ifdef MACESUTED cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl; #endif int _ = 1; while (_--) solve(); #ifdef MACESUTED cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl; #endif return 0; }❤️ 2 -
@ 2022-3-25 7:22:15
#025 2022.3.25
标签：数据结构，线段树，可持久化，珂朵莉树。
Statement
有 匹魔法小马，第 匹小马在初始时具有 的魔法值，每秒钟回复 魔法值，魔法值上限为 。
你会进行 次操作，每次操作在 时刻会将 到 范围内的所有小马的魔法值吸走，吸走后此范围内小马魔法值归零，请你求出每次操作吸走的魔法值总和。
Solution
Solution
对于有区间归零操作的问题，我们的常用方法是记录每个位置上次被清零的时间。考虑一个最简单的简化问题版本：所有操作均为全局操作（即 ）。此时每次询问时所有位置离上次清零的时间均相同，令该时间为 ，我们发现所有 的小马的魔法值都会达到上限 ，其他小马的魔法值则为 。因此我们可以将所有小马按照 排序，二分找到序列中 的最大位置 ，则 $\sum_{1 \le i \le p} m_i + t \times (\sum_{p < i \le n} r_i)$ 即为答案。
考虑在清零操作为全局而询问操作为区间时该怎么做，即想要求得 的所有元素的 和与 和。经典的静态二维数点问题，为降低复杂度可以在 一维上进行可持久化。具体的，将所有小马的 排序，可持久化线段树的第 个版本中插入排序后的前 个元素。则二维数点问题转换为在排序后的数组上二分找到最大的 的位置，在其对应的版本上询问 区间信息，复杂度 。
再考虑原问题，若全局的清零时间不同时应该怎么做。发现使用珂朵莉树维护每个连续清零时间相同的连续段即可。因为每次修改后会将区间内的所有元素的清零时间归零，每次询问时暴力扫描的每一块在询问后会被合并为一块，因此全局暴力扫描的时间复杂度为珂朵莉上块数的总和，而每次操作最多只会新建两个块，因此复杂度得以保证。对于珂朵莉树上的每个连续段，由于段内清零时间相同，做上述的可持久化线段树上查询即可。
另外，一个比较好的处理初始值 的方法是将第 个小马的初始上次清零时间设为 。
总时间复杂度 。
Code
/** * @file 453E.cpp * @author Macesuted (i@macesuted.moe) * @date 2022-03-20 * * @copyright Copyright (c) 2022 * */ #include <bits/stdc++.h> using namespace std; namespace IO { const int SIZE = 1 << 20; char Ibuf[SIZE], *Il = Ibuf, *Ir = Ibuf, Obuf[SIZE], *Ol = Obuf, *Or = Ol + SIZE - 1, stack[32]; char isspace(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\v' || c == '\f' || c == '\r'; } void fill(void) { return Ir = (Il = Ibuf) + fread(Ibuf, 1, SIZE, stdin), void(); } void flush(void) { return fwrite(Obuf, 1, Ol - Obuf, stdout), Ol = Obuf, void(); } char buftop(void) { return Ir == Il ? fill(), *Il : *Il; } char getch(void) { return Il == Ir ? fill(), Il == Ir ? EOF : *Il++ : *Il++; } void putch(char x) { return *Ol++ = x, Ol == Or ? flush() : void(); } template <typename T> T read(void) { T x = 0, f = +1; char c = getch(); while (c < '0' || c > '9') c == '-' ? void(f = -f) : void(), c = getch(); while ('0' <= c && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getch(); return x * f; } template <typename T> void write(T x) { if (!x) putch('0'); if (x < 0) putch('-'), x = -x; int top = 0; while (x) stack[top++] = (x % 10) ^ 48, x /= 10; while (top) putch(stack[--top]); return; } string getstr(const string& suf = "") { string s = suf; while (isspace(buftop())) getch(); while (Il != Ir) { char* p = Il; while (Il < Ir && !isspace(*Il) && *Il != EOF) Il++; s.append(p, Il); if (Il < Ir) break; fill(); } return s; } void putstr(string str, int begin = 0, int end = -1) { if (end == -1) end = str.size(); for (int i = begin; i < end; i++) putch(str[i]); return; } struct Flusher_ { ~Flusher_() { flush(); } } io_flusher_; } // namespace IO using IO::getch; using IO::getstr; using IO::putch; using IO::putstr; using IO::read; using IO::write; bool mem1; #define maxn 100005 typedef pair<long long, long long> pll; class SegmentTree { private: struct Node { Node *l, *r; long long sumR, sumM; Node(void) { l = r = NULL, sumR = sumM = 0; } }; vector<Node*> roots; int n; Node* newRoot(void) { return roots.push_back(roots.back()), roots.back(); } void exist(Node*& p, Node* o) { if (p != o && p != NULL) return; return p = new Node(), *p = *o, void(); } void pushUp(Node* p) { p->sumR = p->sumM = 0; if (p->l != NULL) p->sumR += p->l->sumR, p->sumM += p->l->sumM; if (p->r != NULL) p->sumR += p->r->sumR, p->sumM += p->r->sumM; return; } pll merge(pll a, pll b) { return {a.first + b.first, a.second + b.second}; } void insert(Node*& p, Node* o, int l, int r, int qp, int vr, int vm) { if (o == NULL) p = o = new Node(); exist(p, o); if (l == r) return p->sumR = vr, p->sumM = vm, void(); int mid = (l + r) >> 1; qp <= mid ? insert(p->l, o->l, l, mid, qp, vr, vm) : insert(p->r, o->r, mid + 1, r, qp, vr, vm); return pushUp(p); } pll query(Node* p, int l, int r, int ql, int qr) { if (p == NULL) return {0, 0}; if (ql <= l && r <= qr) return {p->sumR, p->sumM}; int mid = (l + r) >> 1; if (qr <= mid) return query(p->l, l, mid, ql, qr); if (ql > mid) return query(p->r, mid + 1, r, ql, qr); return merge(query(p->l, l, mid, ql, qr), query(p->r, mid + 1, r, ql, qr)); } public: SegmentTree(void) { roots.push_back(NULL); } void resize(int _n) { return n = _n, void(); } void insert(int p, int r, int m) { return newRoot(), insert(roots.back(), roots[(int)roots.size() - 2], 1, n, p, r, m); } pll query(int ver, int l, int r) { return query(roots[ver], 1, n, l, r); } } ST; pair<double, int> t[maxn]; long long rsum[maxn]; class OldDriverTree { private: struct Node { int l, r; double tim; bool operator<(const Node& oth) const { return this->l < oth.l; } }; set<Node> S; int n; void split(Node p, int v) { S.erase(p), S.insert({p.l, v, p.tim}); if (v < p.r) S.insert({v + 1, p.r, p.tim}); return; } public: void build(int _n, double b[]) { n = _n; for (int l = 1, r; l <= n; l = r + 1) { r = l; while (r < n && b[r + 1] == b[r]) r++; S.insert({l, r, b[l]}); } return; } long long query(int T, int l, int r) { auto x = --S.lower_bound({l + 1, 0, 0}); if (x->l != l) split(*x, l - 1); x = --S.lower_bound({r + 1, 0, 0}); if (x->r != r) split(*x, r); long long ans = 0; for (auto i = S.lower_bound({l, 0, 0}); i != S.end() && i->r <= r; i = S.erase(i)) { double tim = T - i->tim; int p = lower_bound(t + 1, t + n + 1, make_pair(tim, 0)) - t; pll ret = ST.query(p - 1, i->l, i->r); ans += ret.second + (long long)((rsum[i->r] - rsum[i->l - 1] - ret.first) * tim + 0.5); } S.insert({l, r, (double)T}); return ans; } } ODT; int s[maxn], m[maxn], r[maxn]; double b[maxn]; set<pll> S; void solve(void) { int n = read<int>(); for (int i = 1; i <= n; i++) { s[i] = read<int>(), m[i] = read<int>(), r[i] = read<int>(); if (r[i]) t[i] = {1. * m[i] / r[i], i}, b[i] = -1. * s[i] / r[i]; else S.emplace(i, s[i]), t[i] = {1e18, i}, b[i] = 0; } for (int i = 1; i <= n; i++) rsum[i] = rsum[i - 1] + r[i]; sort(t + 1, t + n + 1); ST.resize(n), ODT.build(n, b); for (int i = 1; i <= n; i++) ST.insert(t[i].second, r[t[i].second], m[t[i].second]); int q = read<int>(); while (q--) { int t = read<int>(), l = read<int>(), r = read<int>(); long long ans = ODT.query(t, l, r); for (auto i = S.lower_bound({l, 0}); i != S.end() && i->first <= r; i = S.erase(i)) ans += i->second; write(ans), putch('\n'); } return; } bool mem2; int main() { ios::sync_with_stdio(false); #ifdef MACESUTED cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl; #endif int _ = 1; while (_--) solve(); #ifdef MACESUTED cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl; #endif return 0; } -
@ 2022-3-22 7:36:02
#024 2022.3.22
标签：树链剖分，扫描线。
Statement
给出一个 个点的树。现在有 个人，每个人在 时刻出现在树上，以每秒 条边的速度从 走到 。请你求出最早的有两人相遇的时间，没有则输出 。
Solution
Solution
考虑树为一条链时怎么做。发现若以时间为横坐标，每个人所处的在链上的位置为纵坐标，每个人可以被表示为一条线段，问题即为求线段交点横坐标最小值。在横坐标上做扫描线，维护一个
set存放当前时刻所有出现的线段即可。相交线段在相交前一定相邻，每次插入删除时对相邻两线段求交点并于答案取较小值即可。关于set如何按照当前横坐标上每条线段对应的纵坐标排序，重载小于号令其按照当前时刻线段横坐标大小排序即可。虽然随扫描线推移过程原来为小于关系的两条线段不一定一直小于，但是这样打乱相对顺序的情况表示其已经出现了交点，不需要继续向后做扫描线了。因此直接按照当前时刻横坐标来比对是正确的。至于树上情况应该怎么做，在树上进行树链剖分后，将每一个人的行动轨迹拆分到每条路径上的轻重链上即可。最终对每条轻重链执行上述操作，将所得的每条链的答案取最小值即可得到答案。
Code
/** * @file 704E.cpp * @author Macesuted (i@macesuted.moe) * @date 2022-03-20 * * @copyright Copyright (c) 2022 * @brief * My Tutorial: https://macesuted.moe/article/cf704e * */ #include <bits/stdc++.h> using namespace std; namespace IO { const int SIZE = 1 << 20; char Ibuf[SIZE], *Il = Ibuf, *Ir = Ibuf, Obuf[SIZE], *Ol = Obuf, *Or = Ol + SIZE - 1, stack[32]; char isspace(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\v' || c == '\f' || c == '\r'; } void fill(void) { return Ir = (Il = Ibuf) + fread(Ibuf, 1, SIZE, stdin), void(); } void flush(void) { return fwrite(Obuf, 1, Ol - Obuf, stdout), Ol = Obuf, void(); } char buftop(void) { return Ir == Il ? fill(), *Il : *Il; } char getch(void) { return Il == Ir ? fill(), Il == Ir ? EOF : *Il++ : *Il++; } void putch(char x) { return *Ol++ = x, Ol == Or ? flush() : void(); } template <typename T> T read(void) { T x = 0, f = +1; char c = getch(); while (c < '0' || c > '9') c == '-' ? void(f = -f) : void(), c = getch(); while ('0' <= c && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getch(); return x * f; } template <typename T> void write(T x) { if (!x) putch('0'); if (x < 0) putch('-'), x = -x; int top = 0; while (x) stack[top++] = (x % 10) ^ 48, x /= 10; while (top) putch(stack[--top]); return; } string getstr(const string& suf = "") { string s = suf; while (isspace(buftop())) getch(); while (Il != Ir) { char* p = Il; while (Il < Ir && !isspace(*Il) && *Il != EOF) Il++; s.append(p, Il); if (Il < Ir) break; fill(); } return s; } void putstr(string str, int begin = 0, int end = -1) { if (end == -1) end = str.size(); for (int i = begin; i < end; i++) putch(str[i]); return; } struct Flusher_ { ~Flusher_() { flush(); } } io_flusher_; } // namespace IO using IO::getch; using IO::getstr; using IO::putch; using IO::putstr; using IO::read; using IO::write; bool mem1; #define maxn 100005 #define eps 1e-10 typedef pair<int, int> pii; typedef tuple<int, long double, int, long double> tidid; long double TIM, ans = numeric_limits<long double>::max(); struct comp { long double getPos(const tidid& a) const { return get<1>(a) == get<3>(a) ? get<0>(a) : get<0>(a) + (TIM - get<1>(a)) * (get<2>(a) - get<0>(a)) / (get<3>(a) - get<1>(a)); } bool operator()(const tidid& a, const tidid& b) const { return getPos(a) < getPos(b); } }; vector<vector<int>> graph; int fa[maxn], siz[maxn], son[maxn], top[maxn], dep[maxn]; vector<tidid> heav[maxn], ligh[maxn]; void dfs1(int p) { siz[p] = 1; for (auto i : graph[p]) if (i != fa[p]) { fa[i] = p, dep[i] = dep[p] + 1, dfs1(i), siz[p] += siz[i]; if (!son[p] || siz[i] > siz[son[p]]) son[p] = i; } return; } void dfs2(int p, int top_) { top[p] = top_; if (son[p]) dfs2(son[p], top_); for (auto i : graph[p]) if (i != fa[p] && i != son[p]) dfs2(i, i); return; } int LCA(int x, int y) { while (top[x] != top[y]) { if (dep[top[x]] < dep[top[y]]) swap(x, y); x = fa[top[x]]; } return dep[x] < dep[y] ? x : y; } void calcCross(tidid a, tidid b) { long double ak = (get<2>(a) - get<0>(a)) / (get<3>(a) - get<1>(a)), bk = (get<2>(b) - get<0>(b)) / (get<3>(b) - get<1>(b)), ad = get<0>(a) - get<1>(a) * ak, bd = get<0>(b) - get<1>(b) * bk; if ((ad < bd) != (ad + ak * TIM < bd + bk * TIM)) return; long double ret = (ad - bd) / (bk - ak); if (ret < max(get<1>(a), get<1>(b)) - eps || ret > min(get<3>(a), get<3>(b)) + eps) return; return ans = min(ans, ret), void(); } void calc(vector<tidid>& a) { static vector<long double> pos; static vector<vector<tidid>> in, out; pos.clear(), pos.reserve(2 * a.size()), in.clear(), out.clear(); for (auto i : a) pos.push_back(get<1>(i)), pos.push_back(get<3>(i)); sort(pos.begin(), pos.end()), pos.resize(unique(pos.begin(), pos.end()) - pos.begin()); in.resize(pos.size()), out.resize(pos.size()); for (auto i : a) in[lower_bound(pos.begin(), pos.end(), get<1>(i)) - pos.begin()].push_back(i), out[lower_bound(pos.begin(), pos.end(), get<3>(i)) - pos.begin()].push_back(i); static set<tidid, comp> S1; S1.clear(); for (int i = 0; i < (int)pos.size(); i++) { TIM = pos[i]; if (TIM > ans) return; for (auto j : in[i]) { auto ret = S1.emplace(j); if (!ret.second) return ans = min(ans, pos[i]), void(); auto pl = ret.first, pr = pl; if (pl != S1.begin()) calcCross(*--pl, j); if (++pr != S1.end()) calcCross(j, *pr); } for (auto j : out[i]) { auto p2 = S1.erase(S1.find(j)), p1 = p2; if (p1 != S1.begin() && p2 != S1.end()) calcCross(*--p1, *p2); } } return; } void solve(void) { int n = read<int>(), m = read<int>(); graph.resize(n + 1); for (int i = 1; i < n; i++) { int x = read<int>(), y = read<int>(); graph[x].push_back(y), graph[y].push_back(x); } dfs1(1), dfs2(1, 1); for (int i = 1; i <= m; i++) { long double tim = read<int>(), c = read<int>(); int x = read<int>(), y = read<int>(), t = LCA(x, y); while (top[x] != top[t]) { heav[top[x]].emplace_back(x, tim, top[x], tim + (dep[x] - dep[top[x]]) / c), tim += (dep[x] - dep[top[x]]) / c, x = top[x]; ligh[x].emplace_back(x, tim, fa[x], tim + 1 / c), tim += 1 / c, x = fa[x]; } static stack<pii> cache; while (!cache.empty()) cache.pop(); while (top[y] != top[t]) cache.emplace(y, top[y]), y = fa[top[y]]; heav[top[y]].emplace_back(x, tim, y, tim + abs(dep[x] - dep[y]) / c), tim += abs(dep[x] - dep[y]) / c; while (!cache.empty()) { pii p = cache.top(); cache.pop(); ligh[p.second].emplace_back(fa[p.second], tim, p.second, tim + 1 / c), tim += 1 / c; heav[p.second].emplace_back(p.second, tim, p.first, tim + (dep[p.first] - dep[p.second]) / c), tim += (dep[p.first] - dep[p.second]) / c; } } for (int i = 1; i <= n; i++) { for (auto& j : heav[i]) get<0>(j) = dep[get<0>(j)] - dep[i] + 1, get<2>(j) = dep[get<2>(j)] - dep[i] + 1; for (auto& j : ligh[i]) get<0>(j) = dep[get<0>(j)] - dep[i] + 2, get<2>(j) = dep[get<2>(j)] - dep[i] + 2; calc(heav[i]), calc(ligh[i]); } if (ans == numeric_limits<long double>::max()) return putstr("-1\n"); cout << setiosflags(ios::fixed) << setprecision(30) << ans << endl; return; } bool mem2; int main() { ios::sync_with_stdio(false); #ifdef MACESUTED cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl; #endif int _ = 1; while (_--) solve(); #ifdef MACESUTED cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl; #endif return 0; }❤️ 1 -
@ 2022-3-21 7:27:08
#023 2022.3.21
标签：数据结构，线段树。
Statement
给定一个长为 的序列 ，需要实现 次操作：
1 l r x： 表示将区间 中所有 的元素减去 。2 l r： 表示询问区间 的和，最小值，最大值。
强制在线，。
Solution
Solution
考虑以 进制进行值域分块，第 块开动态开点线段树存储所有满足 的位置的信息。
考虑对于 操作，我们枚举每一个值域块，将该块内下标在 之间的元素拿出，进行判断：
- 若该块所有元素值均 ： 对这些元素打上 标记即可。
- 若该块所有元素值均 ： 不进行任何操作。
- 若不满足上述两个条件： 在线段树上向子树递归进行修改操作。
考虑分析此处暴力递归的时间复杂度，容易发现在某块内每次成功的修改都会让被修改元素减少至少一半。显然单个元素最多被修改 次，因此全局总共花在暴力递归上的复杂度为 。
在每次修改后，一些 值减小后可能会因为过小而需要被分配到编号更小的块中，我们可以在线段树每个节点上维护子树最小值，每次修改完成后暴力二分找出过小的位置，将其从当前块线段树上暴力拆出，插入到更小编号的块的线段树内。考虑此操作总时间复杂度，因为一共只有 个块而每次结点只会从当前块到编号更小的块，因此每个元素最多只会在块间移动 次，所以花在此操作上的全局总时间复杂度为 。
对于 2 操作，我们只要将每块内的 部分答案取出合并起来就可以了。
此时总时间复杂度 ，空间复杂度 。
我们发现这样的空间复杂度不足以通过此题，我们考虑线段树底层以 块长分块，则每棵线段树叶子节点数量为 ，空间复杂度降为 ，可以通过此题。
由于此题较卡常，可以考虑根据代码运行情况调整分块的进制和线段树底层分块块长。
Code
本人代码使用指针版动态开点线段树，线段树底层块内使用链表储存，14 进制值域分块，线段树底层块长 500（由于常数比较大，小块长一直 TLE 一个点，但是这个接近 的块长出乎意料地跑得飞快）。
/** * @author Macesuted (i@macesuted.moe) * @copyright Copyright (c) 2021 * @brief * My solution: https://www.macesuted.cn/article/lg7447/ */ #include <bits/stdc++.h> using namespace std; namespace io { #define SIZE (1 << 20) char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr; inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); } inline char getch(void) { return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++); } inline void putch(char x) { *oS++ = x; if (oS == oT) flush(); return; } string getstr(void) { string s = ""; char c = getch(); while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch(); while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch(); return s; } void putstr(string str, int begin = 0, int end = -1) { if (end == -1) end = str.size(); for (register int i = begin; i < end; i++) putch(str[i]); return; } template <typename T> inline T read() { register T x = 0; for (f = 1, c = getch(); c < '0' || c > '9'; c = getch()) if (c == '-') f = -1; for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15); return x * f; } template <typename T> inline void write(const T& t) { register T x = t; if (!x) putch('0'); if (x < 0) putch('-'), x = -x; while (x) qu[++qr] = x % 10 + '0', x /= 10; while (qr) putch(qu[qr--]); return; } struct Flusher_ { ~Flusher_() { flush(); } } io_flusher_; } // namespace io using io::getch; using io::getstr; using io::putch; using io::putstr; using io::read; using io::write; #define maxn 500005 #define blockLen 500 typedef pair<int, int> pii; vector<pii> empty; class SegmentTree { public: struct AnsType { long long sum; int minVal, maxVal; AnsType(void) { sum = 0, minVal = 0x3f3f3f3f, maxVal = 0; } AnsType(long long _sum, int _minVal, int _maxVal) { sum = _sum, minVal = _minVal, maxVal = _maxVal; } inline AnsType operator+(const AnsType& oth) const { return (AnsType){sum + oth.sum, min(minVal, oth.minVal), max(maxVal, oth.maxVal)}; } }; private: struct Node { int minVal, maxVal, size; long long sum, lazy; Node *l, *r; vector<pii> rec; Node(void) { l = r = NULL, minVal = 0x3f3f3f3f, maxVal = sum = lazy = size = 0; } }; Node* root; int n; void update(Node* p, int l, int r, long long delta) { if (r - l + 1 <= blockLen) { for (vector<pii>::iterator i = p->rec.begin(); i != p->rec.end(); i++) i->second -= delta; return recalc(p, l, r); } p->lazy += delta, p->minVal -= delta, p->maxVal -= delta, p->sum -= p->size * delta; return; } void recalc(Node* p, int l, int r) { p->minVal = 0x3f3f3f3f, p->maxVal = 0, p->sum = 0, p->size = p->rec.size(); for (vector<pii>::iterator i = p->rec.begin(); i != p->rec.end(); i++) p->sum += i->second, p->minVal = min(p->minVal, i->second), p->maxVal = max(p->maxVal, i->second); return; } void pushDown(Node* p, int l, int r) { if (p == NULL) return; if (!p->lazy) return; int mid = (l + r) >> 1; if (p->l != NULL) update(p->l, l, mid, p->lazy); if (p->r != NULL) update(p->r, mid + 1, r, p->lazy); p->lazy = 0; return; } inline void pushUp(Node* p) { p->minVal = 0x3f3f3f3f, p->maxVal = 0, p->sum = 0, p->size = 0; if (p->l != NULL) p->minVal = min(p->minVal, p->l->minVal), p->maxVal = max(p->maxVal, p->l->maxVal), p->sum += p->l->sum, p->size += p->l->size; if (p->r != NULL) p->minVal = min(p->minVal, p->r->minVal), p->maxVal = max(p->maxVal, p->r->maxVal), p->sum += p->r->sum, p->size += p->r->size; return; } void insert(Node*& p, int l, int r, int qp, int val) { if (p == NULL) p = new Node(); if (r - l + 1 <= blockLen) { bool find = false; for (vector<pii>::iterator i = p->rec.begin(); !find && i != p->rec.end(); i++) if (i->first == qp) i->second = val, find = true; if (!find) p->rec.push_back((pii){qp, val}); return recalc(p, l, r); } pushDown(p, l, r); int mid = (l + r) >> 1; qp <= mid ? insert(p->l, l, mid, qp, val) : insert(p->r, mid + 1, r, qp, val); return pushUp(p); } void update(Node* p, int l, int r, int ql, int qr, long long val) { if (p == NULL) return; if (p->maxVal <= val) return; if (ql <= l && r <= qr && p->minVal > val) return update(p, l, r, val); if (r - l + 1 <= blockLen) { for (vector<pii>::iterator i = p->rec.begin(); i != p->rec.end(); i++) if (ql <= i->first && i->first <= qr && i->second > val) i->second -= val; return recalc(p, l, r); } pushDown(p, l, r); int mid = (l + r) >> 1; if (ql <= mid) update(p->l, l, mid, ql, qr, val); if (qr > mid) update(p->r, mid + 1, r, ql, qr, val); return pushUp(p); } AnsType getAns(Node* p, int l, int r, int ql, int qr) { if (p == NULL) return (AnsType){}; if (ql <= l && r <= qr) return (AnsType){p->sum, p->minVal, p->maxVal}; if (r - l + 1 <= blockLen) { AnsType ans = (AnsType){0, 0x3f3f3f3f, 0}; for (vector<pii>::iterator i = p->rec.begin(); i != p->rec.end(); i++) if (ql <= i->first && i->first <= qr) ans.sum += i->second, ans.minVal = min(ans.minVal, i->second), ans.maxVal = max(ans.maxVal, i->second); return ans; } pushDown(p, l, r); int mid = (l + r) >> 1; AnsType answer; if (ql <= mid) answer = answer + getAns(p->l, l, mid, ql, qr); if (qr > mid) answer = answer + getAns(p->r, mid + 1, r, ql, qr); return answer; } void findEmpty(Node*& p, int l, int r, int limit) { if (p == NULL) return; if (p->minVal >= limit) return; if (r - l + 1 <= blockLen) { static vector<pii> cache; cache.clear(); for (vector<pii>::iterator i = p->rec.begin(); i != p->rec.end(); i++) (i->second < limit ? empty : cache).push_back(*i); p->rec = cache; recalc(p, l, r); if (p->size == 0) delete p, p = NULL; return; } pushDown(p, l, r); int mid = (l + r) >> 1; findEmpty(p->l, l, mid, limit), findEmpty(p->r, mid + 1, r, limit); pushUp(p); if (p->size == 0) delete p, p = NULL; return; } public: SegmentTree(void) { root = NULL; } inline void resize(int _n) { return n = _n, void(); } inline void insert(int p, int val) { return insert(root, 1, n, p, val); } inline void update(int l, int r, long long delta) { return update(root, 1, n, l, r, delta); } inline AnsType getAns(int l, int r) { return getAns(root, 1, n, l, r); } inline void findEmpty(int limit) { return findEmpty(root, 1, n, limit); } }; SegmentTree tree[8]; long long pow14[8]; int log14(int x) { int t = 0; while (t < 7 && pow14[t + 1] <= x) t++; return t; } int main() { pow14[0] = 1; for (register int i = 1; i < 8; i++) pow14[i] = pow14[i - 1] * 14; int n = read<int>(), m = read<int>(); for (register int i = 0; i < 8; i++) tree[i].resize(n); for (register int i = 1, t; i <= n; i++) { t = read<int>(); tree[log14(t)].insert(i, t); } int lastans = 0; while (m--) { if (read<int>() == 1) { int l = read<int>(), r = read<int>(), x = read<int>(); l ^= lastans, r ^= lastans, x ^= lastans; for (register int i = 0; i < 8; i++) tree[i].update(l, r, x), tree[i].findEmpty(1 << (2 * i)); for (vector<pii>::iterator i = empty.begin(); i != empty.end(); i++) tree[log14(i->second)].insert(i->first, i->second); empty.clear(); } else { int l = read<int>(), r = read<int>(); l ^= lastans, r ^= lastans; SegmentTree::AnsType answer; for (register int i = 0; i < 8; i++) answer = answer + tree[i].getAns(l, r); write(answer.sum), putch(' '), write(answer.minVal), putch(' '), write(answer.maxVal), putch('\n'); lastans = answer.sum & ((1 << 20) - 1); } } return 0; }👍 3 -
@ 2022-3-20 7:52:09
#022 2022.3.20
标签：数据结构，线段树，树链剖分。
Statement
给定一棵 个点的树，每个节点上均有一个二进制运算符（
&、|或^）和一个在 之间的数值。接下来给定 个操作，每个操作分为两类：
- 修改某个结点上的运算符与数值。
- 给定 ，你可以先任意指定一个值 ，然后在树上沿 与 之间的简单路径从 向 移动，每次到达一个结点后将 变为 ， 为该节点上运算符， 为该节点上数值。最大化到达 结点时的 值并输出。
Solution
Solution
由于询问时询问的是树上两点间路径的信息，不难想到通过树链剖分将每条路径转化为 个区间。
由于每个结点上的运算符均为二进制位运算符，运算过程中不同二进制位之间互不影响。我们可以考虑对于每一个二进制位分开来考虑其运算结果，即对于每一个二进制位都求出其为 时经过路径后的结果，最后通过类似数位 DP 的计算方法即可求出 区间内的初值可产生的最大运算结果。
而由于询问时两点间的路径是有向的，从 的路径是向上的，从 的路径是向下的。将树上移动的顺序对应到区间上移动的顺序，不难发现 的路径对应的区间都是从右向左经过的， 的路径对应的区间都是从左向右经过的。因此我们需要对于每一个区间都求出每一个二进制位初始为 时从左向右或是从右向左经过该区间之后的值。
考虑如何维护，建立一棵线段树，每个线段树结点都记录 分别表示：
- 二进制第 位为 时从左向右经过该区间后该位的值。
- 二进制第 位为 时从左向右经过该区间后该位的值。
- 二进制第 位为 时从右向左经过该区间后该位的值。
- 二进制第 位为 时从右向左经过该区间后该位的值。
每次合并两个结点 的信息时令：
ans.l0[i] = a.l0[i] && b.l1[i] || !a.l0[i] && b.l0[i]ans.l1[i] = a.l1[i] && b.l1[i] || !a.l1[i] && b.l0[i]ans.r0[i] = b.r0[i] && a.r1[i] || !b.r0[i] && a.r0[i]ans.r1[i] = b.r1[i] && a.r1[i] || !b.r1[i] && a.r0[i]
即枚举某一位在经过第一个区间后的值，将其以初值代入第二个区间得到结果。
此时对于每一个询问我们将路径拆为 个区间，每个区间对应 个线段树结点，每次合并结点需要花费 的时间，因此此时的总时间复杂度为 ，无法通过本题。
Optimization
我们仔细分析上面的时间复杂度，发现两个 在该算法中都难以去除，因此我们考虑优化掉 的时间复杂度。容易发现 的时间复杂度来自线段数结点合并。
仔细观察我们发现对于 位分别进行逻辑运算是非常浪费的，我们考虑将四个大小为 的数组压为四个大小为 的数字，将逻辑运算转变为二进制位运算即可。对应的四个转移变为：
ans.l0 = (a.l0 & b.l1) | (~a.l0 & b.l0)ans.l1 = (a.l1 & b.l1) | (~a.l1 & b.l0)ans.r0 = (b.r0 & a.r1) | (~b.r0 & a.r0)ans.r1 = (b.r1 & a.r1) | (~b.r1 & a.r0)
因此合并结点信息的复杂度优化到 ，总复杂度达到 ，足以通过此题。
Code
/** * @author Macesuted (i@macesuted.moe) * @copyright Copyright (c) 2021 * @brief * My Solution: https://macesuted.moe/article/h1034 */ #include <bits/stdc++.h> using namespace std; namespace io { #define SIZE (1 << 20) char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr; inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); } inline char getch(void) { return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++); } inline void putch(char x) { *oS++ = x; if (oS == oT) flush(); return; } string getstr(void) { string s = ""; char c = getch(); while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch(); while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch(); return s; } void putstr(string str, int begin = 0, int end = -1) { if (end == -1) end = str.size(); for (register int i = begin; i < end; i++) putch(str[i]); return; } template <typename T> inline T read() { register T x = 0; for (f = 1, c = getch(); c < '0' || c > '9'; c = getch()) if (c == '-') f = -1; for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15); return x * f; } template <typename T> inline void write(const T& t) { register T x = t; if (!x) putch('0'); if (x < 0) putch('-'), x = -x; while (x) qu[++qr] = x % 10 + '0', x /= 10; while (qr) putch(qu[qr--]); return; } struct Flusher_ { ~Flusher_() { flush(); } } io_flusher_; } // namespace io using io::getch; using io::getstr; using io::putch; using io::putstr; using io::read; using io::write; #define maxn 100005 class SegmentTree { public: struct Node { unsigned long long l0, l1, r0, r1; Node(void) { l0 = 0, l1 = ~0, r0 = 0, r1 = ~0; } Node operator+(const Node& b) const { Node a = *this, ans; ans.l0 = (a.l0 & b.l1) | (~a.l0 & b.l0); ans.l1 = (a.l1 & b.l1) | (~a.l1 & b.l0); ans.r0 = (b.r0 & a.r1) | (~b.r0 & a.r0); ans.r1 = (b.r1 & a.r1) | (~b.r1 & a.r0); return ans; } }; Node tree[maxn << 2]; int n; void update(int p, int l, int r, int qp, int opt, unsigned long long val) { if (l == r) { if (opt == 1) tree[p].l0 = tree[p].r0 = 0, tree[p].l1 = tree[p].r1 = val; else if (opt == 2) tree[p].l0 = tree[p].r0 = val, tree[p].l1 = tree[p].r1 = ~0; else tree[p].l0 = tree[p].r0 = val, tree[p].l1 = tree[p].r1 = ~val; return; } int mid = (l + r) >> 1; qp <= mid ? update(p << 1, l, mid, qp, opt, val) : update(p << 1 | 1, mid + 1, r, qp, opt, val); tree[p] = tree[p << 1] + tree[p << 1 | 1]; return; } Node merge(int p, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return tree[p]; int mid = (l + r) >> 1; Node answer; if (ql <= mid) answer = answer + merge(p << 1, l, mid, ql, qr); if (qr > mid) answer = answer + merge(p << 1 | 1, mid + 1, r, ql, qr); return answer; } inline void resize(int tn) { return n = tn, void(); } inline void update(int p, int opt, unsigned long long val) { return update(1, 1, n, p, opt, val); } inline Node merge(int l, int r) { return merge(1, 1, n, l, r); } }; SegmentTree tree; int opt[maxn]; unsigned long long val[maxn]; vector<vector<int> > graph; int dep[maxn], siz[maxn], son[maxn], top[maxn], fa[maxn], dfn[maxn]; void dfs1(int p, int pre = 0) { dep[p] = dep[pre] + 1, fa[p] = pre, siz[p] = 1; for (vector<int>::iterator i = graph[p].begin(); i != graph[p].end(); i++) if (*i != pre) { dfs1(*i, p); if (!son[p] || siz[*i] > siz[son[p]]) son[p] = *i; siz[p] += siz[*i]; } return; } int tim = 0; void dfs2(int p, int t) { dfn[p] = ++tim, top[p] = t; if (son[p]) dfs2(son[p], t); for (vector<int>::iterator i = graph[p].begin(); i != graph[p].end(); i++) if (*i != fa[p] && *i != son[p]) dfs2(*i, *i); return; } int lca(int x, int y) { while (top[x] != top[y]) { if (dep[top[x]] < dep[top[y]]) swap(x, y); x = fa[top[x]]; } return dep[x] < dep[y] ? x : y; } int main() { int n = read<int>(), m = read<int>(), k = read<int>(); graph.resize(n + 1); for (register int i = 1; i <= n; i++) opt[i] = read<int>(), val[i] = read<unsigned long long>(); for (register int i = 1, from, to; i < n; i++) { from = read<int>(), to = read<int>(); graph[from].push_back(to), graph[to].push_back(from); } dfs1(1), dfs2(1, 1); tree.resize(n); for (register int i = 1; i <= n; i++) tree.update(dfn[i], opt[i], val[i]); while (m--) if (read<int>() == 1) { int x = read<int>(), y = read<int>(), t = lca(x, y); unsigned long long z = read<unsigned long long>(); SegmentTree::Node record1, record2; while (top[x] != top[t]) record1 = tree.merge(dfn[top[x]], dfn[x]) + record1, x = fa[top[x]]; record1 = tree.merge(dfn[t], dfn[x]) + record1; while (top[y] != top[t]) record2 = tree.merge(dfn[top[y]], dfn[y]) + record2, y = fa[top[y]]; if (y != t) record2 = tree.merge(dfn[t] + 1, dfn[y]) + record2; swap(record1.l0, record1.r0), swap(record1.l1, record1.r1); SegmentTree::Node record = record1 + record2; bool up = true; unsigned long long answer = 0; for (register int i = k - 1; ~i; i--) { unsigned long long l0 = (record.l0 >> i & 1), l1 = (record.l1 >> i & 1), t = (z >> i & 1); if (!up) answer |= max(l0, l1) << i; else if (t == 0) answer |= l0 << i; else if (l0 >= l1) answer |= l0 << i, up = false; else answer |= l1 << i; } cout << answer << endl; } else { int p = read<int>(), opt = read<int>(); unsigned long long val = read<unsigned long long>(); tree.update(dfn[p], opt, val); } return 0; }👍 4 -
@ 2022-3-19 7:02:33
#021 2022.3.19
标签：数据结构，珂朵莉树，CDQ分治。
Statement
维护一个长为 的序列 ，有 次操作。
- 将区间 的值修改为 。
- 询问区间 出现了多少种不同的数，也就是说同一个数出现多次只算一个。
Solution
Solution
区间数不同颜色数量问题我们常用的解决方案是记 等于最大的 满足 且 ，数区间内满足 的数量即为区间内的颜色数量。
此题的难点在于区间修改操作，经分析不难发现当一个区间 被修改为 时 ，所以在每次操作后我们只需要：
- 将 修改为上一个 区间的右端点。
- 将下一个 区间的左端点的 改为 。
- 将 区间内的所有 改为 。
考虑 3 操作，如果我们在每次修改时将所有 的位置找出并修改为 ，全局花在 3 操作上的修改次数为 ：初始时每个 可能都不等于 ，而后面的 个操作中每个操作最多只会让两个 修改得不等于 ，所以全局出现过 不等于 情况的次数为 ，所以花在 3 操作上的修改次数也就为 。
考虑如何快速找出 的位置。容易发现这样的位置一定是一个连续颜色段的开头。因此我们对原序列建一颗 ODT，每次修改 时，1 操作和 2 操作直接单点修改，3 操作找到 ODT 上被 包含的所有连续颜色段，将它们全部删除并把它们的左端点的 设为 即可。
我们可以使用树套树在线维护修改操作并 解决查询操作。
考虑使用复杂度不变但空间更小的做法。
我们现在是在使用树套树在线解决带修改二维数点问题，考虑再开一维表示数据修改的时间，问题就转变为静态三维数点问题，离线 CDQ 分治即可。
时间复杂度仍旧为 ，空间复杂度优化到 。
Code
/** * @author Macesuted (macesuted@qq.com) * @copyright Copyright (c) 2021 * @brief * My Solution: https://macesuted.moe/article/h1065 */ #include <bits/stdc++.h> using namespace std; namespace io { #define SIZE (1 << 20) char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr; inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); } inline char getch(void) { return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++); } inline void putch(char x) { *oS++ = x; if (oS == oT) flush(); return; } string getstr(void) { queue<char> que; char c = getch(); while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch(); while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) que.push(c), c = getch(); string s; s.resize(que.size()); for (register int i = 0; i < (int)s.size(); i++) s[i] = que.front(), que.pop(); return s; } void putstr(string str, int begin = 0, int end = -1) { if (end == -1) end = str.size(); for (register int i = begin; i < end; i++) putch(str[i]); return; } template <typename T> inline T read() { register T x = 0; for (f = 1, c = getch(); c < '0' || c > '9'; c = getch()) if (c == '-') f = -1; for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15); return x * f; } template <typename T> inline void write(const T& t) { register T x = t; if (!x) putch('0'); if (x < 0) putch('-'), x = -x; while (x) qu[++qr] = x % 10 + '0', x /= 10; while (qr) putch(qu[qr--]); return; } struct Flusher_ { ~Flusher_() { flush(); } } io_flusher_; } // namespace io using io::getch; using io::getstr; using io::putch; using io::putstr; using io::read; using io::write; #define maxn 100005 typedef pair<int, int> pii; struct Node { int tim, pos, pre, delta; inline bool operator<(const Node& oth) const { return this->pre < oth.pre; } }; struct Ask { int id, tim, l, r; inline bool operator<(const Ask& oth) const { return this->l < oth.l; } }; vector<Node> nodes; vector<Ask> asks; map<int, set<pii> > record; int a[maxn], pre[maxn]; class ODT { private: map<pii, int> color; void split(int l, int mid, int r) { int col = color[(pii){l, mid}] = color[(pii){mid + 1, r}] = color[(pii){l, r}]; color.erase((pii){l, r}); record[col].erase((pii){l, r}), record[col].insert((pii){l, mid}), record[col].insert((pii){mid + 1, r}); return; } void erase(int tim, int l, int r) { int col = color[(pii){l, r}]; color.erase((pii){l, r}); set<pii>::iterator i = ++record[col].find((pii){l, r}); if (i != record[col].end()) nodes.push_back((Node){tim, i->first, pre[i->first], -1}), nodes.push_back((Node){tim, i->first, pre[i->first] = pre[l], +1}); nodes.push_back((Node){tim, l, pre[l], -1}), nodes.push_back((Node){tim, l, pre[l] = l - 1, +1}); record[col].erase((pii){l, r}); return; } public: inline void build(int l, int r, int col) { return color[(pii){l, r}] = col, record[col].insert((pii){l, r}), void(); } void insert(int tim, int l, int r, int col) { map<pii, int>::iterator t = --color.lower_bound((pii){l + 1, 0}); if (t->first.first != l) split(t->first.first, l - 1, t->first.second); t = --color.lower_bound((pii){r + 1, 0}); if (t->first.second != r) split(t->first.first, r, t->first.second); while (true) { map<pii, int>::iterator i = color.lower_bound((pii){l, 0}); if (i == color.end() || i->first.second > r) break; erase(tim, i->first.first, i->first.second); } record[col].insert((pii){l, r}); set<pii>::iterator i = record[col].find((pii){l, r}), il = i, ir = i; int p = 0; if (il != record[col].begin()) p = (--il)->second; nodes.push_back((Node){tim, l, pre[l], -1}), nodes.push_back((Node){tim, l, pre[l] = p, +1}); if (++ir != record[col].end()) nodes.push_back((Node){tim, ir->first, pre[ir->first], -1}), nodes.push_back((Node){tim, ir->first, pre[ir->first] = r, +1}); color[(pii){l, r}] = col; // t = color.find((pii){l, r}); // if (t != color.begin() && (--t)->second == col) { // int nl = t->first.first; // record[col].erase((pii){t->first.first, t->first.second}), record[col].erase((pii){l, r}); // color.erase(t), color.erase((pii){l, r}); // record[col].insert((pii){l = nl, r}); // color[(pii){l, r}] = col; // } // t = ++color.find((pii){l, r}); // if (t != color.end() && t->second == col) { // int nr = t->first.second; // record[col].erase((pii){t->first.first, t->first.second}), record[col].erase((pii){l, r}); // color.erase(t), color.erase((pii){l, r}); // record[col].insert((pii){l, r = nr}); // color[(pii){l, r}] = col; // } return; } }; class BIT { private: int tree[maxn]; public: void add(int p, int val) { for (register int i = p; i < maxn; i += i & -i) tree[i] += val; return; } int sum(int p) { int sum = 0; for (register int i = p; i; i -= i & -i) sum += tree[i]; return sum; } }; ODT tree; BIT bit; int answer[maxn]; void CDQ(int nl, int nr, int ql, int qr, int tl, int tr) { if (nl > nr || ql > qr) return; int tmid = (tl + tr) >> 1, nmid = nl - 1, qmid = ql - 1; while (nmid < nr && nodes[nmid + 1].tim <= tmid) nmid++; while (qmid < qr && asks[qmid + 1].tim <= tmid) qmid++; CDQ(nl, nmid, ql, qmid, tl, tmid), CDQ(nmid + 1, nr, qmid + 1, qr, tmid + 1, tr); if (nl > nmid || qmid + 1 > qr) return; sort(nodes.begin() + nl, nodes.begin() + nmid + 1), sort(asks.begin() + qmid + 1, asks.begin() + qr + 1); int j = nl; for (register int i = qmid + 1; i <= qr; i++) { while (j <= nmid && asks[i].l > nodes[j].pre) bit.add(nodes[j].pos, nodes[j].delta), j++; answer[asks[i].id] += bit.sum(asks[i].r) - bit.sum(asks[i].l - 1); } for (register int i = nl; i < j; i++) bit.add(nodes[i].pos, -nodes[i].delta); return; } int main() { int n = read<int>(), m = read<int>(); for (register int i = 1; i <= n; i++) a[i] = read<int>(); for (register int i = 1, j; i <= n; i = j + 1) { j = i; while (j < n && a[j + 1] == a[i]) j++; tree.build(i, j, a[i]); set<pii>::iterator t = record[a[i]].find((pii){i, j}); int p = 0; if (t != record[a[i]].begin()) p = (--t)->second; pre[i] = p; for (register int k = i + 1; k <= j; k++) pre[k] = k - 1; } for (register int i = 1; i <= n; i++) nodes.push_back((Node){0, i, pre[i], +1}); for (register int i = 1; i <= m; i++) if (read<int>() == 1) { int l = read<int>(), r = read<int>(), col = read<int>(); tree.insert(i, l, r, col); } else { int l = read<int>(), r = read<int>(); asks.push_back((Ask){(int)asks.size(), i, l, r}); } // for (vector<Node>::iterator i = nodes.begin(); i != nodes.end(); i++) // cerr << i->tim << ' ' << i->pos << ' ' << i->pre << ' ' << i->delta << endl; CDQ(0, (int)nodes.size() - 1, 0, (int)asks.size() - 1, 0, m); for (register int i = 0; i < (int)asks.size(); i++) write(answer[i]), putch('\n'); return 0; }👍 6❤️ 1 -
@ 2022-3-18 6:50:57
#020 2022.3.18
标签：数据结构，线段树。
Statement
现在有一个数字序列 和一个运算符序列 。
定义 表示 对 取模后的结果。
现有 个操作：
- 将 修改为 。
- 将 修改为 。
- 求 的值。
$1 \le n,~m \le 10^5,~1 \le a_i < 2^{32},~p_i \in \{+,~\times\}$
Solution
Solution
考虑我们如何暴力计算 ，我们会先将 区间切分为若干满足每段内所有符号均为 的极长段。如 将被分割为 。分割完后我们对每个极长段求出段内乘积，再将所有段的结果加起来即为我们所求的 。
先考虑没有修改操作只有查询操作的情况，对于每一个查询区间我们需要知道区间内所有极长段的乘积之和，容易想到使用线段树维护。线段树上每一个结点维护对应区间的最左端极长段乘积，最右端极长段乘积和其他极长段乘积之和。合并两个区间信息时判断左结点的最右端极长段与右结点的最左端极长段是否能够连接即可。
考虑加入 1 操作，对 序列的区间修改操作在线段树上体现为对 个区间的整段修改操作。我们发现对于一个线段树结点，当他对应的区间被整段修改后其所有极长段左右端点均没有发生变化，而所有极长段的段内乘积会发生改变。我们考虑对于每个节点维护一个桶维护其所有非最左端也非最右端的极长段长度，在将该节点整段修改为 时只需要将答案更新为 即可。同时我们也需要记录最左端极长段长度和最右端极长段长度，这样在合并线段树结点信息时即可将左结点的最右端极长段与右结点的最左端极长段合并后构成的新极长段长度加入桶中。
考虑加入 2 操作，同样我们也可以将对 序列的区间修改在线段树上体现为对 个区间的整段修改操作。由于修改为 和修改为 的情况不同，我们分开讨论：
- 整段修改为 ： 修改后该区间内会产生 个长为 的极长段， 将变为 。为此对每个节点我们维护整段元素和以快速维护此修改操作。
- 整段修改为 ： 修改后该区间内会产生 个长为 的极长段，此时该极长段的乘积为 。为此对每个节点我们维护整段元素乘积以快速维护此修改操作。
在线段树上维护上述所有信息即可，此时时间复杂度为 ，空间复杂度为 。时间复杂度与空间复杂度均无法通过此题。
优化 1
对于每个线段树结点，其区间内所有极长段的长度之和为 ，因此最多只会存在 种不同的极长段长度，将相同长度的极长段的信息在一起存储，使用大小为 的
vector存储即可。此时时间复杂度 ，空间复杂度 。时间复杂度仍无法通过此题。
优化 2
在区间修改元素值时我们对 个长度都 求该长度对应区间修改后的乘积。考虑存储连续段长度时按连续段长度升序存储，需要对第 个长度求值时从第 个长度对应的答案转移过来。因为 $O(\sum_{i} \log (a_i - a_{i-1})) = O(\log a_n) = O(\sqrt {len})$，所以花在对 个长度求值的时间复杂度转为 。
此时时间复杂度 ，空间复杂度 ，可以通过此题。
也可以考虑以恰当块长对线段树底层进行分块以继续减少空间占用。
Code
/** * @author Macesuted (i@macesuted.moe) * @copyright Copyright (c) 2021 * @brief * My solution: https://macesuted.moe/article/lg5608 */ #include <bits/stdc++.h> using namespace std; namespace io { #define SIZE (1 << 20) char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr; inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); } inline char getch(void) { return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++); } inline void putch(char x) { *oS++ = x; if (oS == oT) flush(); return; } string getstr(void) { string s = ""; char c = getch(); while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch(); while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch(); return s; } void putstr(string str, int begin = 0, int end = -1) { if (end == -1) end = str.size(); for (register int i = begin; i < end; i++) putch(str[i]); return; } template <typename T> inline T read() { register T x = 0; for (f = 1, c = getch(); c < '0' || c > '9'; c = getch()) if (c == '-') f = -1; for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15); return x * f; } template <typename T> inline void write(const T& t) { register T x = t; if (!x) putch('0'); if (x < 0) putch('-'), x = -x; while (x) qu[++qr] = x % 10 + '0', x /= 10; while (qr) putch(qu[qr--]); return; } struct Flusher_ { ~Flusher_() { flush(); } } io_flusher_; } // namespace io using io::getch; using io::getstr; using io::putch; using io::putstr; using io::read; using io::write; #define maxn 100005 #define sqrtn 320 #define mod 1000000007 #define leafLen 50 typedef pair<int, int> pii; long long Pow(long long a, long long x) { long long ans = 1; while (x) { if (x & 1) ans = ans * a % mod; a = a * a % mod; x >>= 1; } return ans; } inline int Mod(int x) { return x >= mod ? x - mod : x; } pii cache[sqrtn]; class SegmentTree { private: struct Node { bool op, hasLazyOp, lazyOp, hasLazyNum; long long allMul, lMul, rMul; int allPlus, ans, lazyNum; int lNum, rNum, lLen, rLen; pii midLen[sqrtn]; int tail; int len, sqrtLen; Node *l, *r; Node(void) { hasLazyOp = hasLazyNum = false, l = r = NULL, tail = 0; } void add(int val, int cnt = 1) { if (val == 0) return; for (register int i = 1; i <= tail; i++) if (midLen[i].first == val) return midLen[i].second += cnt, void(); int p = tail++; while (p > 0 && midLen[p].first > val) swap(midLen[p], midLen[p + 1]), p--; midLen[p + 1] = (pii){val, cnt}; return; } Node operator+(const Node& oth) const { Node a = *this, b = oth; a.hasLazyOp = a.hasLazyNum = false; a.allMul = a.allMul * b.allMul % mod; a.allPlus = Mod(a.allPlus + b.allPlus); a.rNum = b.rNum; a.sqrtLen = sqrt(a.len += b.len); int ctail = a.tail; for (register int i = 1; i <= a.tail; i++) cache[i] = a.midLen[i]; int pb = 1, pc = 1; a.tail = 0; while (pb <= b.tail && pc <= ctail) if (b.midLen[pb].first == cache[pc].first) a.midLen[++a.tail] = (pii){b.midLen[pb].first, b.midLen[pb].second + cache[pc].second}, pb++, pc++; else if (b.midLen[pb].first < cache[pc].first) a.midLen[++a.tail] = b.midLen[pb], pb++; else a.midLen[++a.tail] = cache[pc], pc++; while (pb <= b.tail) a.midLen[++a.tail] = b.midLen[pb], pb++; while (pc <= ctail) a.midLen[++a.tail] = cache[pc], pc++; if (!a.op) { if (!a.lLen) swap(a.lLen, a.rLen), swap(a.lMul, a.rMul); if (!b.rLen) swap(b.lLen, b.rLen), swap(b.lMul, b.rMul); a.ans = Mod(Mod(a.ans + b.ans) + Mod(a.rMul + b.lMul)); a.add(a.rLen), a.add(b.lLen); a.rLen = b.rLen, a.rMul = b.rMul; } else { if (!a.rLen) swap(a.lLen, a.rLen), swap(a.lMul, a.rMul); if (!b.lLen) swap(b.lLen, b.rLen), swap(b.lMul, b.rMul); int nLen = a.rLen + b.lLen, nMul = a.rMul * b.lMul % mod; a.ans = Mod(a.ans + b.ans); a.rLen = b.rLen, a.rMul = b.rMul; if (!a.lLen) a.lLen = nLen, a.lMul = nMul; else if (!a.rLen) a.rLen = nLen, a.rMul = nMul; else a.ans = Mod(a.ans + nMul), a.add(nLen); } a.op = b.op; return a; } int getAns(void) { int ans = this->ans; if (lLen) ans = Mod(ans + lMul); if (rLen) ans = Mod(ans + rMul); return ans; } }; Node* root; int a[maxn], op[maxn]; int n; Node merge(Node* l, Node* r) { Node ans = *l + *r; ans.l = l, ans.r = r; return ans; } Node reCalc(int l, int r) { Node p; p.op = op[r], p.ans = 0; p.tail = 0; p.lNum = a[l], p.rNum = a[r]; p.lLen = 1, p.lMul = a[l], p.rLen = 0, p.rMul = 0; p.sqrtLen = sqrt(p.len = r - l + 1); while (l + p.lLen <= r && op[l + p.lLen - 1]) p.lMul = p.lMul * a[l + p.lLen] % mod, p.lLen++; if (l + p.lLen - 1 < r) { p.rLen = 1, p.rMul = a[r]; while (op[r - p.rLen]) p.rMul = p.rMul * a[r - p.rLen] % mod, p.rLen++; int tl = l + p.lLen, tr = r - p.rLen; if (tl <= tr) { long long last = a[tl]; int lastPos = tl; for (register int i = tl; i < tr; i++) if (op[i]) last = last * a[i + 1] % mod; else p.ans = Mod(p.ans + last), p.add(i - lastPos + 1), last = a[lastPos = i + 1]; p.add(tr - lastPos + 1), p.ans = Mod(p.ans + last); } } p.allMul = 1, p.allPlus = 0; for (register int i = l; i <= r; i++) p.allMul = p.allMul * a[i] % mod, p.allPlus = Mod(p.allPlus + a[i]); return p; } void modifyNum(Node* p, int l, int r, int num) { if (r - l + 1 < leafLen) { for (register int i = l; i <= r; i++) a[i] = num; *p = reCalc(l, r); return; } p->allMul = Pow(num, r - l + 1), p->allPlus = 1LL * (r - l + 1) * num % mod, p->ans = 0; long long lastPow = 1; int lastPos = 0; for (register int i = 1; i <= p->tail; i++) lastPow = lastPow * Pow(num, p->midLen[i].first - lastPos) % mod, lastPos = p->midLen[i].first, p->ans = (p->ans + lastPow * p->midLen[i].second) % mod; p->lNum = p->rNum = num; if (p->lLen) p->lMul = Pow(num, p->lLen); if (p->rLen) p->rMul = Pow(num, p->rLen); p->hasLazyNum = true, p->lazyNum = num; return; } inline void modifyOp(Node* p, int l, int r, bool _op) { if (r - l + 1 < leafLen) { for (register int i = l; i <= r; i++) op[i] = _op; *p = reCalc(l, r); return; } p->op = _op; if (!_op) { p->ans = Mod(Mod(p->allPlus + mod - p->lNum) + mod - p->rNum); p->lLen = 1, p->lMul = p->lNum; p->rLen = 1, p->rMul = p->rNum; p->tail = 0, p->add(1, r - l - 1); } else { p->ans = 0; p->lLen = r - l + 1, p->lMul = p->allMul; p->rLen = 0, p->rMul = 0; p->tail = 0; } p->hasLazyOp = true, p->lazyOp = _op; return; } inline void pushDown(Node* p, int l, int r) { int mid = (l + r) >> 1; if (p->hasLazyOp) { p->hasLazyOp = false; modifyOp(p->l, l, mid, p->lazyOp), modifyOp(p->r, mid + 1, r, p->lazyOp); } if (p->hasLazyNum) { p->hasLazyNum = false; modifyNum(p->l, l, mid, p->lazyNum), modifyNum(p->r, mid + 1, r, p->lazyNum); } return; } void build(Node*& p, int l, int r, int _a[], bool _op[]) { if (p == NULL) p = new Node(); if (r - l + 1 < leafLen) { for (register int i = l; i <= r; i++) a[i] = _a[i], op[i] = _op[i]; p->sqrtLen = sqrt(p->len = r - l + 1); *p = reCalc(l, r); return; } int mid = (l + r) >> 1; build(p->l, l, mid, _a, _op), build(p->r, mid + 1, r, _a, _op); *p = merge(p->l, p->r); return; } void updateNum(Node* p, int l, int r, int ql, int qr, int val) { if (ql <= l && r <= qr) return modifyNum(p, l, r, val); if (r - l + 1 < leafLen) { for (register int i = max(l, ql); i <= min(r, qr); i++) a[i] = val; *p = reCalc(l, r); return; } pushDown(p, l, r); int mid = (l + r) >> 1; if (ql <= mid) updateNum(p->l, l, mid, ql, qr, val); if (qr > mid) updateNum(p->r, mid + 1, r, ql, qr, val); *p = merge(p->l, p->r); return; } void updateOp(Node* p, int l, int r, int ql, int qr, bool _op) { if (ql <= l && r <= qr) return modifyOp(p, l, r, _op); if (r - l + 1 < leafLen) { for (register int i = max(l, ql); i <= min(r, qr); i++) op[i] = _op; *p = reCalc(l, r); return; } pushDown(p, l, r); int mid = (l + r) >> 1; if (ql <= mid) updateOp(p->l, l, mid, ql, qr, _op); if (qr > mid) updateOp(p->r, mid + 1, r, ql, qr, _op); *p = merge(p->l, p->r); return; } Node getAns(Node* p, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return *p; if (r - l + 1 < leafLen) return reCalc(max(l, ql), min(r, qr)); int mid = (l + r) >> 1; pushDown(p, l, r); if (qr <= mid) return getAns(p->l, l, mid, ql, qr); if (ql > mid) return getAns(p->r, mid + 1, r, ql, qr); return getAns(p->l, l, mid, ql, qr) + getAns(p->r, mid + 1, r, ql, qr); } public: SegmentTree(void) { root = NULL; } inline void resize(int _n) { return n = _n, void(); } inline void build(int a[], bool op[]) { return build(root, 1, n, a, op); } inline void updateNum(int l, int r, int val) { return updateNum(root, 1, n, l, r, val); } inline void updateOp(int l, int r, bool op) { return updateOp(root, 1, n, l, r, op); } inline int getAns(int l, int r) { return getAns(root, 1, n, l, r).getAns(); } }; SegmentTree tree; int a[maxn]; bool op[maxn]; int main() { int n = read<int>(), m = read<int>(); for (register int i = 1; i <= n; i++) a[i] = read<long long>() % mod; for (register int i = 1; i < n; i++) op[i] = read<int>(); tree.resize(n), tree.build(a, op); while (m--) { int opt = read<int>(); if (opt == 1) { int l = read<int>(), r = read<int>(); tree.updateNum(l, r, read<long long>() % mod); } else if (opt == 2) { int l = read<int>(), r = read<int>(); tree.updateOp(l, r, read<int>()); } else { int l = read<int>(), r = read<int>(); write(tree.getAns(l, r)), putch('\n'); } } return 0; }👍 3 -
@ 2022-3-17 6:46:57
#019 2022.3.17
标签：构造，高斯消元。
Statement
给出 个可以让你使用的变量，其中前两个变量分别为 。你并不知道 具体值，请你利用下面两中运算令某一变量值为 :
+ a b c：将变量 与变量 相加，结果输出到变量 。^ a b：将变量 的 次方输出到变量 ， 为题目初始时给出的定值。
所有运算均在模 意义下进行。
Solution
Solution
考虑 时怎么做。
容易发现答案即为 ，需要支持减法和除以二操作。容易发现 即为 ， 为 。即我们只需要额外实现乘法，使用龟速乘实现即可。即要求 （ 为常数），仅通过加法即可计算出 ，最终将 二进制拆分后将对应位置上的值加起来即可。
考虑 的情况，我们尝试构造 使满足 。其为 $\sum_{i = 0}^{d} x^t \times \sum_{j = 0}^{d} a_j \times j^{d - j} \times {d \choose j}$，我们想要使得 次项系数为 ，其余均为 ，其构成 个线性方程，使用高斯消元求解出一组合法的 即可。
因此我们可以通过上述方法完成平方操作，再使用 时的做法即可求出最终答案。龟速乘操作复杂度 ，平方操作复杂度 ，最终复杂度 。
Code
/** * @file 1060H.cpp * @author Macesuted (i@macesuted.moe) * @date 2022-03-09 * * @copyright Copyright (c) 2022 * */ #include <bits/stdc++.h> using namespace std; namespace io { const int SIZE = 1 << 20; char Ibuf[SIZE], *Il = Ibuf, *Ir = Ibuf, Obuf[SIZE], *Ol = Obuf, *Or = Ol + SIZE - 1, stack[32]; char isspace(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\v' || c == '\f' || c == '\r'; } void fill(void) { return Ir = (Il = Ibuf) + fread(Ibuf, 1, SIZE, stdin), void(); } void flush(void) { return fwrite(Obuf, 1, Ol - Obuf, stdout), Ol = Obuf, void(); } char buftop(void) { return Ir == Il ? fill(), *Il : *Il; } char getch(void) { return Il == Ir ? fill(), Il == Ir ? EOF : *Il++ : *Il++; } void putch(char x) { return *Ol++ = x, Ol == Or ? flush() : void(); } template <typename T> T read(void) { T x = 0, f = +1; char c = getch(); while (c < '0' || c > '9') c == '-' ? void(f = -f) : void(), c = getch(); while ('0' <= c && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getch(); return x * f; } template <typename T> void write(T x) { if (!x) putch('0'); if (x < 0) putch('-'), x = -x; int top = 0; while (x) stack[top++] = (x % 10) ^ 48, x /= 10; while (top) putch(stack[--top]); return; } string getstr(const string& suf = "") { string s = suf; while (isspace(buftop())) getch(); while (Il != Ir) { char* p = Il; while (Il < Ir && !isspace(*Il) && *Il != EOF) Il++; s.append(p, Il); if (Il < Ir) break; fill(); } return s; } void putstr(string str, int begin = 0, int end = -1) { if (end == -1) end = str.size(); for (int i = begin; i < end; i++) putch(str[i]); return; } struct Flusher_ { ~Flusher_() { flush(); } } io_flusher_; } // namespace io using io::getch; using io::getstr; using io::putch; using io::putstr; using io::read; using io::write; bool mem1; int a[12][12], c[12], binom[12][12], d, mod; long long Pow(long long a, long long x) { long long ans = 1; while (x) { if (x & 1) ans = ans * a % mod; a = a * a % mod, x >>= 1; } return ans; } void opPlus(int x, int y, int to) { return putstr("+ "), write(x), putch(' '), write(y), putch(' '), write(to), putch('\n'); } void opPow(int x, int to) { return putstr("^ "), write(x), putch(' '), write(to), putch('\n'); } int empt = 50; int multi(int x, int v) { vector<int> cache; if (v & 1) cache.push_back(x), v--; for (int i = 1, last = x; v; i++) { opPlus(last, last, empt); if (v >> i & 1) cache.push_back(empt), v -= 1 << i; last = empt++; } if (cache.size() == 1) return cache.front(); int to = empt++; opPlus(cache[0], cache[1], to); for (int i = 2; i < (int)cache.size(); i++) opPlus(to, cache[i], to); return to; } int pow2(int p) { vector<int> cache; for (int i = 0; i <= d; i++, opPlus(p, 5000, p)) { int x = empt++; opPow(p, x); if (c[i]) cache.push_back(multi(x, c[i])); } if (cache.size() == 1) return cache.front(); int to = empt++; opPlus(cache[0], cache[1], to); for (int i = 2; i < (int)cache.size(); i++) opPlus(to, cache[i], to); return to; } void solve(void) { d = read<int>(), mod = read<int>(); for (int i = 0; i <= d; i++) { binom[i][0] = binom[i][i] = 1; for (int j = 1; j < i; j++) binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % mod; } for (int i = 0; i <= d; i++) { for (int j = 0; j <= d; j++) a[i][j] = Pow(j, d - i) * binom[d][i] % mod; a[i][d + 1] = (i == 2); } for (int i = 0; i <= d; i++) { int p = i; for (int j = i + 1; j <= d; j++) if (a[j][i] > a[p][i]) p = j; for (int j = 0; j <= d + 1; j++) swap(a[i][j], a[p][j]); long long inv = Pow(a[i][i], mod - 2); for (int j = 0; j <= d + 1; j++) a[i][j] = a[i][j] * inv % mod; for (int j = 0; j <= d; j++) { if (i == j) continue; long long x = a[j][i]; for (int k = 0; k <= d + 1; k++) a[j][k] = (a[j][k] + mod - x * a[i][k] % mod) % mod; } } for (int i = 0; i <= d; i++) c[i] = a[i][d + 1]; opPlus(1, 2, 3); int p1 = multi(pow2(1), mod - 1), p2 = multi(pow2(2), mod - 1), p3 = pow2(3); opPlus(p3, p1, p3), opPlus(p3, p2, p3); int p = multi(p3, Pow(2, mod - 2)); putstr("f "), write(p), putch('\n'); return; } bool mem2; int main() { #ifdef MACESUTED cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl; #endif int _ = 1; while (_--) solve(); #ifdef MACESUTED cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl; #endif return 0; } -
@ 2022-3-16 6:47:53
#018 2022.3.16
标签：数据结构，线段树，线段树分治。
Statement
有一个 的矩阵 ，初始全是 ，有 次修改操作和 次查询操作，先进行所有修改操作，然后进行所有查询操作。
一次修改操作会给出 ，代表把所有满足 且 的 元素加上一个值 。
一次查询操作会给出 ，代表查询所有满足 且 的 元素的最大值。
$1 \le n,~m \le 5 \times 10^4,~1 \le q \le 5 \times 10^5$
Solution
Solution
由于询问数量远高于修改数量，考虑询问复杂度较低的算法。
考虑在 轴上分治，对于分治区间 我们求出所有 $l_1 \le mid = \lfloor \frac {l + r} 2 \rfloor \le r_1$ 的询问的答案。可以从 开始向左做一次扫描线，维护区间加减的同时维护区间历史最大值即可得到 $\max_{l_1 \le i \le mid,~l_2 \le j \le r_2} a_{i,~j}$ 的值。同理再从 开始向右做一次扫描线，将 与 的答案取较大值即可得到原询问的答案。
为保持分治结构每层增减修改操作的数量保持在 级别，考虑按该分治结构建立线段树，对于每个修改操作，按线段树插入的方法插入到线段树中。插入操作最终到达的 个被 包含的结点采用类似标记永久化的方法，线段树分治进入该结点子树时加入该修改操作贡献，离开该结点子树时减去该修改操作贡献。对于线段树上其他 个存在一部分被修改操作包含的结点，在其内分治执行扫描线过程时最多会进行 次区间修改操作，因此全局花在维护修改操作贡献上的时间复杂度为 。
总时间复杂度 。
Code
/** * @file 6109.cpp * @author Macesuted (i@macesuted.moe) * @date 2022-03-11 * * @copyright Copyright (c) 2022 * */ #include <bits/stdc++.h> using namespace std; namespace IO { const int SIZE = 1 << 20; char Ibuf[SIZE], *Il = Ibuf, *Ir = Ibuf, Obuf[SIZE], *Ol = Obuf, *Or = Ol + SIZE - 1, stack[32]; char isspace(char c) { return c == ' ' || c == 't' || c == 'n' || c == 'v' || c == 'f' || c == 'r'; } void fill(void) { return Ir = (Il = Ibuf) + fread(Ibuf, 1, SIZE, stdin), void(); } void flush(void) { return fwrite(Obuf, 1, Ol - Obuf, stdout), Ol = Obuf, void(); } char buftop(void) { return Ir == Il ? fill(), *Il : *Il; } char getch(void) { return Il == Ir ? fill(), Il == Ir ? EOF : *Il++ : *Il++; } void putch(char x) { return *Ol++ = x, Ol == Or ? flush() : void(); } template <typename T> T read(void) { T x = 0, f = +1; char c = getch(); while (c < '0' || c > '9') c == '-' ? void(f = -f) : void(), c = getch(); while ('0' <= c && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getch(); return x * f; } template <typename T> void write(T x) { if (!x) putch('0'); if (x < 0) putch('-'), x = -x; int top = 0; while (x) stack[top++] = (x % 10) ^ 48, x /= 10; while (top) putch(stack[--top]); return; } string getstr(const string& suf = "") { string s = suf; while (isspace(buftop())) getch(); while (Il != Ir) { char* p = Il; while (Il < Ir && !isspace(*Il) && *Il != EOF) Il++; s.append(p, Il); if (Il < Ir) break; fill(); } return s; } void putstr(string str, int begin = 0, int end = -1) { if (end == -1) end = str.size(); for (int i = begin; i < end; i++) putch(str[i]); return; } struct Flusher_ { ~Flusher_() { flush(); } } io_flusher_; } // namespace IO using IO::getch; using IO::getstr; using IO::putch; using IO::putstr; using IO::read; using IO::write; bool mem1; #define maxn 50005 #define maxq 500005 typedef pair<int, int> pii; typedef tuple<int, int, int> tiii; typedef tuple<int, int, int, int, int> tiiiii; vector<tiii> rec[2][maxn]; long long ans[maxq]; class SegmentTree1 { private: class SegmentTree { private: struct Node { long long maxVal, maxVal_, lazy, lazy_; bool clearHist; }; Node tree[maxn << 4]; int n; void clearHist(int p) { if (tree[p].lazy_ || tree[p].lazy) calcLazy(p << 1, tree[p].lazy_, tree[p].lazy), calcLazy(p << 1 | 1, tree[p].lazy_, tree[p].lazy); return tree[p].maxVal_ = tree[p].maxVal, tree[p].lazy_ = tree[p].lazy = 0, tree[p].clearHist = true, void(); } void calcLazy(int p, long long lazy_, long long lazy) { return tree[p].maxVal_ = max(tree[p].maxVal_, tree[p].maxVal + lazy_), tree[p].maxVal += lazy, tree[p].lazy_ = max(tree[p].lazy_, tree[p].lazy + lazy_), tree[p].lazy += lazy, void(); } void pushDown(int p) { if (tree[p].clearHist) clearHist(p << 1), clearHist(p << 1 | 1), tree[p].clearHist = false; if (tree[p].lazy_ || tree[p].lazy) calcLazy(p << 1, tree[p].lazy_, tree[p].lazy), calcLazy(p << 1 | 1, tree[p].lazy_, tree[p].lazy), tree[p].lazy_ = tree[p].lazy = 0; return; } void pushUp(int p) { return tree[p].maxVal = max(tree[p << 1].maxVal, tree[p << 1 | 1].maxVal), tree[p].maxVal_ = max(tree[p << 1].maxVal_, tree[p << 1 | 1].maxVal_), void(); } void add(int p, int l, int r, int ql, int qr, long long v) { if (ql <= l && r <= qr) return calcLazy(p, max(0LL, v), v); pushDown(p); int mid = (l + r) >> 1; if (ql <= mid) add(p << 1, l, mid, ql, qr, v); if (qr > mid) add(p << 1 | 1, mid + 1, r, ql, qr, v); return pushUp(p); } void clearHist(int p, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return clearHist(p); pushDown(p); int mid = (l + r) >> 1; if (ql <= mid) clearHist(p << 1, l, mid, ql, qr); if (qr > mid) clearHist(p << 1 | 1, mid + 1, r, ql, qr); return pushUp(p); } long long getHistMaxVal(int p, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return tree[p].maxVal_; pushDown(p); int mid = (l + r) >> 1; if (qr <= mid) return getHistMaxVal(p << 1, l, mid, ql, qr); if (ql > mid) return getHistMaxVal(p << 1 | 1, mid + 1, r, ql, qr); return max(getHistMaxVal(p << 1, l, mid, ql, qr), getHistMaxVal(p << 1 | 1, mid + 1, r, ql, qr)); } public: void resize(int _n) { return n = _n, void(); } void add(int l, int r, long long v) { return add(1, 1, n, l, r, v); } void clearHist(int l, int r) { return clearHist(1, 1, n, l, r); } long long getHistMaxVal(int l, int r) { return getHistMaxVal(1, 1, n, l, r); } } ST; struct Node { vector<tiii> whole, init; vector<tiiiii> query; }; Node tree[maxn << 2]; int n; void insRec(int p, int l, int r, int ql, int qr, tiii v) { if (ql <= l && r <= qr) return tree[p].whole.push_back(v); int mid = (l + r) >> 1; if (ql <= mid && mid <= qr) tree[p].init.push_back(v); if (ql <= mid) insRec(p << 1, l, mid, ql, qr, v); if (qr > mid) insRec(p << 1 | 1, mid + 1, r, ql, qr, v); return; } void insQues(int p, int l, int r, tiiiii ques) { int mid = (l + r) >> 1; if ((l <= get<0>(ques) && get<0>(ques) <= mid && mid < get<1>(ques) && get<1>(ques) <= r) || l == r) return tree[p].query.push_back(ques); return get<1>(ques) <= mid ? insQues(p << 1, l, mid, ques) : insQues(p << 1 | 1, mid + 1, r, ques); } void solve(int p, int l, int r) { if (l == r) { for (auto i : tree[p].whole) ST.add(get<0>(i), get<1>(i), get<2>(i)); ST.clearHist(1, n); for (auto i : tree[p].query) ans[get<4>(i)] = max(ans[get<4>(i)], ST.getHistMaxVal(get<2>(i), get<3>(i))); for (auto i : tree[p].whole) ST.add(get<0>(i), get<1>(i), -get<2>(i)); return; } for (auto i : tree[p].whole) ST.add(get<0>(i), get<1>(i), get<2>(i)); int mid = (l + r) >> 1; for (auto i : tree[p].init) ST.add(get<0>(i), get<1>(i), get<2>(i)); static vector<tiii> cache; cache.clear(), ST.clearHist(1, n); sort(tree[p].query.begin(), tree[p].query.end(), [](tiiiii a, tiiiii b) { return get<0>(a) > get<0>(b); }); auto j = tree[p].query.begin(); while (j != tree[p].query.end() && get<0>(*j) == mid) ans[get<4>(*j)] = max(ans[get<4>(*j)], ST.getHistMaxVal(get<2>(*j), get<3>(*j))), j++; for (int i = mid - 1; i >= l; i--) { for (auto j : rec[0][i + 1]) ST.add(get<0>(j), get<1>(j), -get<2>(j)), cache.emplace_back(get<0>(j), get<1>(j), -get<2>(j)); for (auto j : rec[1][i]) ST.add(get<0>(j), get<1>(j), get<2>(j)), cache.push_back(j); while (j != tree[p].query.end() && get<0>(*j) == i) ans[get<4>(*j)] = max(ans[get<4>(*j)], ST.getHistMaxVal(get<2>(*j), get<3>(*j))), j++; } for (auto i = cache.rbegin(); i != cache.rend(); i++) ST.add(get<0>(*i), get<1>(*i), -get<2>(*i)); cache.clear(), ST.clearHist(1, n); sort(tree[p].query.begin(), tree[p].query.end(), [](tiiiii a, tiiiii b) { return get<1>(a) < get<1>(b); }); j = tree[p].query.begin(); while (j != tree[p].query.end() && get<1>(*j) == mid) ans[get<4>(*j)] = max(ans[get<4>(*j)], ST.getHistMaxVal(get<2>(*j), get<3>(*j))), j++; for (int i = mid + 1; i <= r; i++) { for (auto j : rec[1][i - 1]) ST.add(get<0>(j), get<1>(j), -get<2>(j)), cache.emplace_back(get<0>(j), get<1>(j), -get<2>(j)); for (auto j : rec[0][i]) ST.add(get<0>(j), get<1>(j), get<2>(j)), cache.push_back(j); while (j != tree[p].query.end() && get<1>(*j) == i) ans[get<4>(*j)] = max(ans[get<4>(*j)], ST.getHistMaxVal(get<2>(*j), get<3>(*j))), j++; } for (auto i = cache.rbegin(); i != cache.rend(); i++) ST.add(get<0>(*i), get<1>(*i), -get<2>(*i)); for (auto i : tree[p].init) ST.add(get<0>(i), get<1>(i), -get<2>(i)); solve(p << 1, l, mid), solve(p << 1 | 1, mid + 1, r); for (auto i : tree[p].whole) ST.add(get<0>(i), get<1>(i), -get<2>(i)); return; } public: void resize(int _n) { return n = _n, void(); } void insRec(int l, int r, tiii v) { return insRec(1, 1, n, l, r, v); } void insQues(tiiiii ques) { return insQues(1, 1, n, ques); } void solve(void) { return ST.resize(n), solve(1, 1, n); } } ST; void solve(void) { ios::sync_with_stdio(false); int n = read<int>(), m = read<int>(), q = read<int>(); ST.resize(n); for (int i = 1; i <= m; i++) { int l1 = read<int>(), r1 = read<int>(), l2 = read<int>(), r2 = read<int>(), x = read<int>(); rec[0][l1].emplace_back(r1, r2, x), rec[1][l2].emplace_back(r1, r2, x), ST.insRec(l1, l2, {r1, r2, x}); } for (int i = 1; i <= q; i++) { int l1 = read<int>(), r1 = read<int>(), l2 = read<int>(), r2 = read<int>(); ST.insQues({l1, l2, r1, r2, i}); } ST.solve(); for (int i = 1; i <= q; i++) write(ans[i]), putch('n'); return; } bool mem2; int main() { #ifdef MACESUTED cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl; #endif int _ = 1; while (_--) solve(); #ifdef MACESUTED cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl; #endif return 0; }👍 2
