题解 CF526F 【Pudding Monsters】

ShuYuMo

2020-10-19 20:21:16

Solution

[MyBlog](https://shuyumo2003.github.io/2020/%E3%80%8C%E9%A2%98%E5%8D%95%E3%80%8DIOI2020%E5%9B%BD%E5%AE%B6%E9%9B%86%E8%AE%AD%E9%98%9F%E4%BD%9C%E4%B8%9A-Part-1/#CF526F-Pudding-Monsters) # CF526F Pudding Monsters - 给定一个 $n \times n$ 的棋盘,其中有 $n$ 个棋子,每行每列恰好有一个棋子。 - 求有多少个 $k \times k$ 的子棋盘中恰好有 $k$ 个棋子。 - $n \le 3 \times 10^5$。 每行每列**恰好有一个**棋子的棋盘,可以抽象成一个排列。 而操作也是对于一个排列的一段进行操作的。 题意可以转化为: - 给出一个排列 - 求连续段数量,即连续的一段,且段中的元素排好序之后必须是公差为$1$的等差数列. **连续段计数** 考虑如何刻画“**连续的一段,且段中的元素排好序之后必须是公差为$1$的等差数列**”这个条件,可以形式化的定义: $$\operatorname{MaxVal} - \operatorname{MinVal} = (R - L)$$ 即 $$f_{R}(L) = \operatorname{MaxVal} - \operatorname{MinVal} - (R - L) = 0$$ 这个条件成立的基础在于,所求数列不能有重复元素,而且也保证了函数$f_x(L) \ge 0$, 查询时只需要维护**最小值**以及最小值的**数量**即可。 可以考虑枚举一个端点,比如右端点 $R$,然后查找有多少符合条件的左端点 $L$ ,用线段树维护$f_R(x)$在每个点处的函数值。 考虑当$f_x(L)$ 移动到 $f_{x + 1}(L)$ 时, 值的变化。变化的值有 $R$ , 可能变化的有$MaxVal, MinVal$。用单调栈实时维护更新后会波及哪些元素的最小值。事实上,单调栈处理的过程就是在动态维护一个后缀最小\大值数组。 这里有几个与其有相似之处的题目,但是可能做法并不一样,遇到不要想成一样的题目: - [算术天才⑨与等差数列](https://www.luogu.com.cn/problem/P5278) (不保证序列中一定元素不重复) - 考虑判断一个序列排好序后是否为等差数列 - 准确做法 - $\max−\min=(r−l)k$ - 相邻两数差的绝对值的 $\operatorname{gcd}$是 $k$ - 区间 $[l,r]$ 内的数不重复 - 概率性做法 - hash思想,维护 $n$ 次方和 - [树上排列(ZROI)](http://www.zhengruioi.com/contest/718/problem/1615) (同样不保证元素一定不重复) - 给定一颗 $n$ 个点的树。每个点都一个正整数点权 $A_i$ ,你需要支持以下两种操作: - 1、询问点 $x$ 和点 $y$ 之间的路径上的所有点(包括点 $x$ 和点 $y$ )的点权是否构成一个从 $1$ 开始的排列(即若这条链长度为 $len$ ,那么问点权集合为 ${1,2,⋯,len}$ )。 - 2、将 $A_x$ 修改为 $y$ 。 - 由于在树上难以判断某区间内的数字不重复,Hash维护n次方和。 - 给出一个没有重复元素的序列,询问某区间中的元素是否能加入小于$k$个元素使其拍好序后构成一个等差数列。 - 条件变成了 $$f_{R}(L) = \operatorname{MaxVal} - \operatorname{MinVal} - (R - L) \ge k$$ - [count(ZROI)](http://www.zhengruioi.com/problem/1532)已知一个集合$S$中的最大元素为 $N$, 且这个集合中的元素可以构成一个等差数列,给出一些形如$x \in S$、$x \notin S$的限制。求最终的集合有多少种情况。 - 考虑刻画一个等差数列需要什么参数:公差,和每个元素$\bmod $ 公差的值。枚举这两个参数,依次计数即可。 (引用正睿的两道题目,不知道是不是有版权问题,如果有,会立即删除(~~顺便给正睿OI打个广告~~))。 ## code {% note info CF526F Pudding Monsters %} ```cpp int n; int A[_]; #define fir first #define sec second namespace SegmentTree{ const int _ = 3e6 + 100; struct Node{ int MIN; int sMIN; int tar; Node operator + (const Node & rhs) const { Node res; res.MIN = min(MIN, rhs.MIN); res.sMIN = MIN == rhs.MIN ? ( sMIN + rhs.sMIN) : (MIN < rhs.MIN ? sMIN : rhs.sMIN) ; return res; } }v[_]; int tot = 0; int ch[_][2]; #define ls(o) (ch[o][0]) #define rs(o) (ch[o][1]) #define make (tot++, ch[tot][0] = ch[tot][1] = v[tot].MIN = v[tot].sMIN = 0, tot) int Groot() { return make; } void maintain(int o) { v[o].MIN = min(v[ls(o)].MIN, v[rs(o)].MIN); v[o].sMIN = v[ls(o)].MIN == v[rs(o)].MIN ? v[ls(o)].sMIN + v[rs(o)].sMIN : ( v[ls(o)].MIN < v[rs(o)].MIN ? v[ls(o)].sMIN : v[rs(o)].sMIN ); } void tar(int o, int x) { v[o].MIN += x; v[o].tar += x; } void pushdown(int o){ if(v[o].tar){ tar(ls(o), v[o].tar); tar(rs(o), v[o].tar); v[o].tar = 0; } } void build(int o, int L, int R){ if(L == R) { v[o].MIN = 0; v[o].sMIN = 1; return; } int mid = (L + R) >> 1; ls(o) = make; rs(o) = make; build(ls(o), L, mid); build(rs(o), mid + 1, R); maintain(o); } void update(int o, int nowl, int nowr, int L, int R, int x){ if(L > R) return ; if(L <= nowl && nowr <= R) return tar(o, x); int mid = (nowl + nowr) >> 1; pushdown(o); if(L <= mid) update(ls(o), nowl, mid, L, R, x); if(R > mid) update(rs(o), mid + 1, nowr, L, R, x); maintain(o); } Node query(int o, int nowl, int nowr, int L, int R) { if(L <= nowl && nowr <= R) return v[o]; int mid = (nowl + nowr) >> 1; pushdown(o); Node Ans; Ans.MIN = INT_MAX; if(L <= mid) Ans = Ans + query(ls(o), nowl, mid, L, R); if(R > mid) Ans = Ans + query(rs(o), mid + 1, nowr, L, R); return Ans; } int query(int o, int L, int R){ Node res = query(o, 1, n, L, R); return res.MIN == 0 ? res.sMIN : 0; } } using SegmentTree::Groot; using SegmentTree::build; using SegmentTree::query; using SegmentTree::update; namespace Mon_Stack{ int t0t = 0, t1t = 0; pair<int, int> S0[_], S1[_]; int work(int *A, int n){ int Ans = 0; int root = Groot(); build(root, 1, n); S0[0].fir = S1[0].fir = 0; for(int i = 1; i <= n; i++) { update(root, 1, n, 1, i - 1, -1); while(t0t != 0 && S0[t0t].sec >= A[i]) { update(root, 1, n, S0[t0t - 1].fir + 1, S0[t0t].fir, S0[t0t].sec); t0t--; } while(t1t != 0 && S1[t1t].sec <= A[i]) { update(root, 1, n, S1[t1t - 1].fir + 1, S1[t1t].fir, -S1[t1t].sec); t1t--; } update(root, 1, n, S0[t0t].fir + 1, i, -A[i]); update(root, 1, n, S1[t1t].fir + 1, i, A[i]); int t = query(root, 1, i); Ans += t; S0[++t0t] = make_pair(i, A[i]); S1[++t1t] = make_pair(i, A[i]); } return Ans; } } using Mon_Stack::work; signed main(){ n = read(); for(int i = 1; i <= n; i++) { int x = read(), y = read(); A[x] = y; } printf("%lld\n", work(A, n)); return 0; } ``` {% endnote %} {% note info count(ZROI) %} ```cpp #include <climits> #include <cmath> #include <cstring> #include <iostream> #include <cstdio> #include <algorithm> using namespace std; #define int long long const int MOD = 1e9 + 7; const int _M = 2e5 + 100; inline int read() { char c = getchar(); int sign = 1; int x = 0; while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); } while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); } return x * sign; } int MAX, m; int have[_M], tht = 0; int none[_M], tnt = 0; int d[_M], tdt = 0; int c[_M];//tct = tdt bool CanBe[_M]; int ToL[_M]; int ToR[_M]; void divide(int s, int x) { for(int i = 1; i * i <= x; i++){ if(x % i == 0) d[++tdt] = i, c[tdt] = s % i; if(i * i != x) d[++tdt] = x / i, c[tdt] = s % d[tdt]; } for(int i = 1; i <= tdt; i++) CanBe[i] = true; } signed main(){ int t; MAX = read(), m = read(); for(int i = 1; i <= m; i++){ int type = read(); if(type == 1) have[++tht] = read(); else none[++tnt] = read(); } sort(have + 1, have + 1 + tht); sort(none + 1, none + 1 + tnt); int maxd = INT_MAX, Sta; for(int i = 2; i <= tht; i++) { if(maxd > have[i] - have[i - 1]){ maxd = have[i] - have[i - 1]; Sta = have[i - 1]; } } divide(Sta, maxd); /* 公差 及 特征 检查 */ for(int i = 1; i <= tht; i++){ for(int j = 1; j <= tdt; j++){ if(!CanBe[j]) continue; if(have[i] % d[j] != c[j]) CanBe[j] = false; } } for(int i = 2; i <= tht; i++){ int D = have[i] - have[i - 1]; for(int j = 1; j <= tdt; j++){ if(!CanBe[j]) continue; if(D % d[j] != 0) CanBe[j] = false; } } t = 0; for(int i = 1; i <= tdt; i++){ if(!CanBe[i]) continue; d[++t] = d[i]; c[ t] = c[i]; CanBe[t] = true; } tdt = t; /* 公差 及 特征 检查 完成*/ for(int i = 1; i <= tdt; i++) { if(CanBe[i]) { ToL[i] = (c[i] == 0 ? d[i] : c[i]) - 1; int t = MAX % d[i]; if(t == c[i]) ToR[i] = MAX + 1; if(t > c[i]) ToR[i] = MAX - (t - c[i]) + 1; if(t < c[i]) ToR[i] = MAX - d[i] + (c[i] - t) + 1; } } t = 0; for(int i = 1; i <= tdt; i++){ if(!CanBe[i]) continue; d[++t] = d[i]; c[ t] = c[i]; CanBe[t] = true; } tdt = t; int MINS = have[1], MAXE = have[tht]; for(int i = 1; i <= tnt; i++){ int now = none[i]; for(int j = 1; j <= tdt; j++){ if(!CanBe[j]) continue; if(now % d[j] == c[j]){ if(now < MINS) ToL[j] = max(ToL[j], now); else if(now > MAXE) ToR[j] = min(ToR[j], now); else CanBe[j] = false; } } } for(int i = 1; i <= tdt; i++) if(ToL[i] > MINS || ToR[i] < MAXE) CanBe[i] = false; else ToL[i]++, ToR[i] --; /* 非法数字存在性检查 */ int ans = 0; for(int i = 1; i <= tdt; i++){ if(!CanBe[i]) continue; int k = ( (MINS - ToL[i]) / d[i] + 1) * ( (ToR[i] - MAXE) / d[i] + 1) % MOD; // TODO; ans = (ans + k) % MOD; } printf("%lld", ans); return 0; } ``` {% endnote %} {% note info A.20联赛集训day3 树上排列(维护15次方和hash) %} ```cpp #include <climits> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <vector> inline int read() { char c = getchar(); int sign = 1; int x = 0; while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); } while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); } return x * sign; } using namespace std; const int _ = 6e5 + 100; const int base = 15; const int MOD = 1020031005; int SS[_]; int pow(int a, int b = base){ int ans = 1; while(b){ if(b & 1) ans = (ans *1ll* a) % MOD; a = (a *1ll* a) % MOD; b >>= 1; } return ans; } int head[_]; int NodeVal[_]; struct edges{ int node; int nxt; }edge[_]; int tot = 0; void add(int u, int v){ tot++; edge[tot].node = v; edge[tot].nxt = head[u]; head[u] = tot; } int n, q; int dep[_], fa[_], dfn[_], rnk[_], top[_], son[_], si[_], dfc = 0; void dfs0(int now, int f, int dp){ int &S = si[now] = 1; int &Mid = son[now] = 0; fa[now] = f; dep[now] = dp; for(int i = head[now]; i ; i = edge[i].nxt){ int ex = edge[i].node; if(ex == f) continue; dfs0(ex, now, dp + 1); S += si[ex]; if(si[ex] > si[Mid]) Mid = ex; } if(!Mid) Mid = 0; } void dfs1(int now, int f, int tp){ dfn[now] = ++dfc; rnk[dfc] = now; top[now] = tp; if(son[now]) dfs1(son[now], now, tp); for(int i = head[now]; i ; i = edge[i].nxt){ int ex = edge[i].node; if(ex == f || ex == son[now]) continue; dfs1(ex, now, ex); } } void clear(){ memset(head, 0, sizeof(head)); dfn[0] = rnk[0] = si[0] = top[0] = fa[0] = son[0] = 0; tot = 0; dfc = 0; } namespace SegmentTree{ const int _ = 3e6 + 100; int tot = 0; int ch[_][2]; int v[_]; #define make (tot++, ch[tot][0] = ch[tot][1] = v[tot] = 0, tot); #define ls(x) (ch[x][0]) #define rs(x) (ch[x][1]) #define maintain(o) (v[o] = (v[ls(o)] +0ll+ v[rs(o)]) % MOD ) void init_s() { tot = 0; } int Groot(){ return make; } void build(int o, int L, int R){ if(L == R) return (void)(v[o] = pow(NodeVal[rnk[L]])); int mid = (L + R) >> 1; ls(o) = make; rs(o) = make; build(ls(o), L, mid); build(rs(o), mid + 1, R); maintain(o); } void update(int o, int nowl, int nowr, int p, int x){ if(nowl == nowr) return (void)(v[o] = pow(x)); int mid = (nowl + nowr) >> 1; if(p <= mid) update(ls(o), nowl, mid, p, x); if(p > mid) update(rs(o), mid + 1, nowr, p, x); maintain(o); } int query(int o, int nowl, int nowr, int L, int R){ if(L > R) return 0; if(L <= nowl && nowr <= R) return v[o]; int mid = (nowl + nowr) >> 1; int ans = 0; if(L <= mid) ans = (ans +0ll+ query(ls(o), nowl, mid, L, R)) % MOD; if(R > mid) ans = (ans +0ll+ query(rs(o), mid + 1, nowr, L, R)) % MOD; return ans; } } using SegmentTree::Groot; using SegmentTree::init_s; using SegmentTree::build; using SegmentTree::update; using SegmentTree::query; int root = 0; int LCA; int QueryOnPath(int x, int y){ int ans = 0; while(top[x] != top[y]){ if(dep[top[x]] > dep[top[y]]) swap(x, y); ans = (ans +0ll+ query(root, 1, n, dfn[top[y]], dfn[y])) % MOD; y = fa[top[y]]; } if(dep[x] < dep[y]) swap(x, y); LCA = y; ans = (ans +0ll+ query(root, 1, n, dfn[y], dfn[x])) % MOD; return ans; } void doit(){ clear(); n = read(), q = read(); for(int i = 1; i <= n; i++) NodeVal[i] = read(); for(int i = 1; i < n; i++){ int u = read(), v = read(); add(u, v); add(v, u); } dfs0(1, 1, 1); dfs1(1, 1, 1); init_s(); root = Groot(); build(root, 1, n); while(q--){ int opt = read(), x = read(), y = read(); if(opt == 1){ int r = QueryOnPath(x, y); int Len = dep[x] + dep[y] - (dep[LCA] << 1) + 1; puts(SS[Len] == r ? "Yes" : "No"); } else{ update(root, 1, n, dfn[x], y); } } } int main(){ for(int i = 1; i <= 3e5; i++) SS[i] = ( SS[i - 1] +0ll+ pow(i) ) % MOD; int T = read(); while(T--) doit(); return 0; } ``` {% endnote %}