RainAir's Blog - 线段树
type: channel
link: http://blog.aor.sd.cn/tag/线段树/
items: CF 1437 题解
items: ZR 2020普转提七连测day5
items: contest5 题解
items: 20联赛集训day9 题解
items: 2020.09.26【NOIP提高组】模拟
items: CF 1158 题解
items: CF 1086 题解
items: CF 997 题解
items: CF 1418 题解
items: CF 666 题解

CF 1437 题解
type: item
date: 2020-10-29T19:10:12+08:00
description: A判断一下前面能否空出来就就行，也就是 $l \geq r-l+1$。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl int main(){ int T;scanf("%d",&T); while(T--){ int l,r;scanf("%d%d",&l,&r); puts(l >= r-l+1 ? "YES" : "NO"); } return 0; }B相当于不能有子串 11 和 00。那么如果有 11 肯定在后面有一个地方有 00 （反证），所以每次操作最多可以消去两个这样的连续的东西，求出有多少个相邻相同的位置 $x$，答案就是 $\lceil \frac{x}{2} \rceil$。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e5 + 5; char str[MAXN]; int main(){ int T;scanf("%d",&T); while(T--){ int n;scanf("%d",&n); scanf("%s",str+1); int ans = 0; FOR(i,2,n) if(str[i] == str[i-1]) ans++; ans = (ans+1)>>1; printf("%d\n",ans); } return 0; }C首先可以发现一个东西：将匹配方式连边，一定存在一种分配方式使得最优解没有包含关系的线段，因为包含关系可以通过交换变成相交，并且代价不变。排序后可以设 $f_{i,j}$ 表示考虑了前 $i$ 个数，最小的 $j$ 满足 $j$ 开始后面一段数字都没有被用过的代价，转移直接枚举下一个填啥就行了。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 600+5; int n,a[MAXN]; bool vis[MAXN]; int f[2][MAXN],now; int main(){ int T;scanf(…

ZR 2020普转提七连测day5
type: item
date: 2020-10-28T20:46:00+08:00
description: A. 跳石头首先我们观察一下青蛙是怎么跳的：对于一个断点 $(i,i+1)$，如果有 $x$ 只青蛙往左跳，那么一定有 $x$ 只青蛙往右跳，所以 $a_i$ 一定是偶数。并且我们发现从 $a_i$ 到 $a_{i+1}$，变化的只可能是 $i+1$ 这一个青蛙，也就是有 $|a_i-a_{i+1}| \in \{0,2,-2\}$。我们考虑 $a_i$ 到 $a_{i+1}$ 的变化：如果是 $0$ 说明一定是 $i$ 跳到自己，如果多了 $2$ 说明 $i$ 往后跳，少了 $2$ 是往前跳。所以我们可以得出每个点往哪里跳，然后用类似括号序列的方式配对就行了：遇到往右的加入栈，往左的就随便取出一个。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 2e5 + 5; int n,a[MAXN]; int ans[MAXN]; int main(){ scanf("%d",&n); FOR(i,1,n-1) scanf("%d",a+i); bool flag = 1; FOR(i,1,n){ flag &= !(a[i]&1); flag &= (std::abs(a[i]-a[i-1]) == 2 || a[i] == a[i-1]); } if(!flag){ puts("No"); return 0; } std::vector<int> S; FOR(i,1,n){ if(a[i] == a[i-1]+2){// 左括号 S.pb(i); } else if(a[i] == a[i-1]){ ans[i] = i; } else{ // 右括号 if(S.empty()){ puts("No"); return 0; } ans[S.back()] = i; ans[i] = S.back(); S.pop_back(); } } if(!S.empty()){ puts("No"); return 0; } puts("Yes"); FOR(i,1,n) printf("%d%c",ans[i]," \n"[i==n]); return 0; } /* 1. a[i] 都是偶数 并且正好一半往左一半往右 2. 考虑 a[i] 和 a[i+1]:如果中间不动 a[i]==a[i+1],如果中间往右 a[i+1] = a[i]+2,如果中间往左 a[i+1] = a[i]-2 往右必然要有一个往左 所以遇到往右的可以看成左括号 往左的可以看成右括号 就行了 */B. 树先把颜色相同的缩成一个树，感性理解操作肯定是每次操作同一个联通块，让他的影响不断增大。我们设第一次操作的点是 $x$ ，以 $x$ 为根建树，发现操作最大深度次就能完成。所以我们要让最大深度尽量小，就是直径的长度除以二。稍微注意下处理重边即可。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl co…

contest5 题解
type: item
date: 2020-10-22T22:13:37+08:00
description: A. 星际穿越感觉也很神。。先将询问拆成前缀和的形式，我们要对于一组询问 $(l,r)$ 求出 $[l,r]$ 内所有点到 $r$ 的最短距离的和。考虑 $r$ 往左走的最短路径是怎么走的：引理一：往右走之前一定不会往左走反证法。如果先往左走在往右走，那么这个右边的点一定能 cover 到起点，所以可以第一步就先往右走，答案不会变劣。引理二：不会存在连续的两次往右走反证法。如果存在两次连续的往右走，那么之后一定有一次往左走，并且跨越起点的，我们可以一开始就走到这个点，答案不会变劣。所以我们的路径只有可能是先往右最多走一次，再往左走。我们观察一下一个点 $v$ 到达左边的点 $x$ 的最短距离的分布是怎么样的：如果 $dis(v,x)=1$，那么有 $l_v \leq x$。如果 $dis(v,x) \leq 2$，那么我们就会先走一步，用这个点中转，也就是问在区间 $[l_v,n]$ 内是否存在点 $y$，使得 $dis(x,y) \leq 1$。注意这里这个区间包含了一些根本不跨过 $v$ 的点，但这是显然不影响答案的。归纳可以得到：如果 $dis(v,x) \leq k$，当且仅当存在一个点 $y \in [l_v,n]$，满足 $dis(x,y) \leq k-1$。所以一个暴力的想法是每次先特判了距离为 $1$ 的点，然后每次求出最往左的距离为 $2$ 的点跳过去，以此类推。。对于跳这种东西，我们肯定想到要用倍增优化。我们想找到 $\leq k$ 的最往左的点，就要找到 $dis(x,y) \leq k-1$ 的最往左的点。。。所以我们定义在找 $dis(v,x) \leq k$ 的一次跳跃是从 $x$ 点找到最小的一个点 $z$，满足 $\exists y \in [l_v,n],dis(z,y) \leq k-1$，所以设 $f_{i,j}$ 表示从 $i$ 号点，跳了 $2^j$ 次（也就是处理了距离为 $[1,2^j+1]$ 的点），为了统计答案，设 $g_{i,j}$ 表示从 $i$ 号点跳了 $2^j$ 的所有答案，初始化 $f_{i,0} = \min_{j \geq i}\{l_j\}$，$f_{1,0} = 0,g_{i,0} = i-f_{i,0}$。转移大概写一下 ：$$ \begin{aligned} f_{i,j} &= f_{f_{i,j-1},j-1}\\ g_{i,j} &= g_{i,j-1}+g_{f_{i,j-1},j-1}+2^{j-1}(f_{i,j-1}-f_{i,j}) \end{aligned} $$查询的时候跳一下，记一下已经跳了多少长度即可。最后有一些零散的边界要判掉。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 3e5 + 5; const int MAXM = 18; int n,l[MAXN]; // 处理[i,n]跳2^j步的最远位置 和这一块的答案 int f[MAXN][MAXM+1]; LL g[MAXN][MAXM+1]; int pw[MAXM+1]; inline LL calc(int l,int p){ if(l > p) return 0; if(l >= ::l[p]) return p-l; LL res = p-::l[p],now = 1;p = ::l[p]; ROF(i,MAXM,0){ if(f[p][i] < l) continue; res += g[p][i] + now*(p-f[p][i]); now += (1<<i); p = f[p][i]; } if(l <= p) res += (now+1)*(p-l); return res; } inline LL gcd(LL x,LL y){ return !y ?…

20联赛集训day9 题解
type: item
date: 2020-10-22T21:38:00+08:00
description: A考虑枚举右端点，维护所有左端点的答案：只需要处理出 $pre_i$ 表示 $i$ 前面第一个和它一样的位置，每次让 $(pre_i,i]$ 加上 $w$，$(pre_{pre_i},pre_i]$ 减去 $w$ 即可。#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl inline char nc(){ #define SIZE 1000000+3 static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE; if(p1 == p2){ p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin); if(p1 == p2) return -1; } return *p1++; #undef SIZE } template <typename T> inline void read(T &x){ x = 0;int flag = 0;char ch = nc(); while(!isdigit(ch)){ if(ch == '-') flag = 1; ch = nc(); } while(isdigit(ch)){ x = (x<<1) + (x<<3) + (ch^'0'); ch = nc(); } if(flag) x = -x; } const int MAXN = 1e6 + 5; LL mx[MAXN<<2],tag[MAXN<<2]; #define lc ((x)<<1) #define rc ((x)<<1|1) inline void cover(int x,LL d){ mx[x] += d;tag[x] += d; } inline void pushdown(int x){ if(tag[x]){ cover(lc,tag[x]); cover(rc,tag[x]); tag[x] = 0; } } inline void modify(int x,int l,int r,int L,int R,int d){ if(l == L && r == R) return cover(x,d); int mid = (l + r) >> 1;pushdown(x); if(R <= mid) modify(lc,l,mid,L,R,d); else if(L > mid) modify(rc,mid+1,r,L,R,d); else modify(lc,l,mid,L,mid,d),modify(rc,mid+1,r,mid+1,R,d); mx[x] = std::max(mx[lc],mx[rc]); } int n,m,c[MAXN],w[MAXN]; int lst[MAXN],pre[MAXN]; int main(){ read(n);read(m); FOR(i,1,n) read(c[i]); FOR(i,1,m) read(w[i]); LL ans = 0; FOR(i,1,n){ pre[i] = lst[c[i]];lst[c[i]] = i; int p1 = pre[i],p2 = pre[p1]; modify(1,1,n,p1+1,i,w[c[i]]); if(p1) modify(1,1,n,p2+1,p1,-w[c[i]]); ans = std::max(ans,mx[1]); } printf("%lld\n",ans); return 0; }B观察一下距离一个点直接距离为 $d$ 的图像是啥：倾斜不是很好处理，于是我们旋转 $45$ 度，现在直接距离定义变成了 $\min(x_i-x_j,y_i-y_j)$。然后我彩笔直接去扫描线，结果爆零了。。我们先考虑如何求出距离最小值：…

2020.09.26【NOIP提高组】模拟
type: item
date: 2020-10-01T19:28:00+08:00
description: A. 旅游设连通块的大小为 $sz_i$，要求计算 $\sum sz_i(sz_i-1)$。离线，排序，并查集维护。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e5 + 5; struct Edge{ int u,v,w; inline bool operator < (const Edge &t) const { return w < t.w; } }e[MAXN]; int n,m,q; int f[MAXN],sz[MAXN]; inline int find(int x){ return x == f[x] ? x : f[x] = find(f[x]); } LL now = 0; inline LL C(int n){ return 1ll*n*(n-1); } inline void merge(int x,int y){ x = find(x);y = find(y); if(x == y) return; now -= C(sz[x])+C(sz[y]); sz[x] += sz[y];f[y] = x; now += C(sz[x]); } LL ans[MAXN]; P qry[MAXN]; inline void Solve(){ scanf("%d%d%d",&n,&m,&q); now = 0;FOR(i,1,n) f[i] = i,sz[i] = 1; FOR(i,1,m) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); std::sort(e+1,e+m+1); FOR(i,1,q){ scanf("%d",&qry[i].fi);qry[i].se = i; } std::sort(qry+1,qry+q+1); int tp = 1; FOR(i,1,q){ while(tp <= m && e[tp].w <= qry[i].fi) merge(e[tp].u,e[tp].v),++tp; ans[qry[i].se] = now; } FOR(i,1,q) printf("%lld\n",ans[i]); } int main(){ int T;scanf("%d",&T); while(T--) Solve(); return 0; }B. Tom显然一定是一个子树放早餐，另一个子树放晚餐。找到这样的子树后分别从下往上放即可。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e5 + 5; int n,a,b; std::vector<int> G[MAXN]; int sz[MAXN],fa[MAXN]; int ps = 0; inline void dfs(int v,int fa=0){ sz[v] = 1;::fa[v] = fa; for…

CF 1158 题解
type: item
date: 2020-09-21T21:21:00+08:00
description: A设第 $i$ 个女生的限制为 $mx_i$，意思是存在一个男生给她 $mx_i$ 的礼物。设第 $i$ 个男生的限制为 $mn_i$，意思是要给所有女生 $mn_i$ 的礼物。设男女生都根据限制大小从小到大排序，首先如果 $mx_n > b_1$ 那么就无解（所有女生至少收到了 $mx_n$ 的礼物，但是第一个女生说她没收到，矛盾了）对于每个女生，我们都要钦定好一个男生送给他礼物，我们肯定要找一个限制最宽的男生给女生送满足她限制的礼物（也就是 $n$），要注意如果 $mx_n < mn_1$ 需要留一个位置来送 $mx_n$ 的礼物来满足限制，这时候会贪心的让男 $n$ 送给女 $1$ 价值 $mx_n$ 的礼物，再让男 $n-1$ 送女 $1$ 价值 $mn_1$ 的礼物。B这题我只会找规律。为了方便找规律，先将 $k$ 的定义改为最大的 $k$ 满足 $[1 \ldots k]$ 的串要么没出现，要么出现 $\geq 2$ 次。（也就是 $k+1$ 时题目定义的实际答案）观察这样的串：10101010101010 100100100100100100 10001000100010001000 1000010000100001000010000设它们的一个循环节长度为 $d$，我们发现长度在 $\leq 3d-1$ 时答案一直是 $\leq d$，之后每增加一个长度答案就会 $+1$，所以可以得到一个式子：$3d-1+(k-d-1) = n \Rightarrow d = \frac{n-k+2}{2}$，而在题目的限制下又一定整除，就可以构造出来了。感觉完全看运气。。C相当于限定了一个数和一段区间的大小关系，线段树优化建图+拓扑排序即可。D也算是半个构造题？先考虑没有规定拐点顺序怎么做：这是个经典问题。我们一开始选取最左边的点，每次走的点只要保证所有的点都在两点连线的一边就好了。明白了这个就会有拐点顺序了：因为你选的“一边”可以是左边也可以是右边，根据题意调整即可。如果是 L 就选择最右边的点，R 就选择最左边的点。E神仙交互题。。这个询问的本质是将每个点 $i$ 距离自己 $\leq d_i$ 的点都染黑（不包含自己）然后输出来哪些点被染黑了。首先我们选取 $1$ 号点为根，我们考虑过程分两步走：求出每个点的深度一个 naive 的做法是询问出所有距离 $\leq i$ 的点，做个类似差分的东西就好了。这个询问能传入长度为 $n$ 的数组，我们只用一个未免太奢侈了，对于这种问题需要考虑如何合并询问。我们如果维护处当前还未确定的深度区间 $[l_1,r_1],[l_2,r_2],\ldots,[l_m,r_m]$，对于每个区间我们只需要询问 $mid-1,mid$ 就可以得出距离是 $mid$ 的有哪些了。如果所有询问直接扔进去一块做会怎么样？那么很有可能 $mid-1$ 会超出边界，影响到上一个的选取，所以我们考虑排序后奇偶分组，这样就不会出现边界重复问题了，我们花了 $4$ 次操作能将问题规模减小一般，这一部分操作是 $4\lceil \log_2n \rceil$。求出每个点的父亲另一个 naive 的做法是对于一个深度为 $d$ 的点 $v$，我们枚举所有深度为 $d-1$ 的点 $u$，查询 $u$ 到距离为 $1$ 的点的集合，判断是否在里面。我们先想想能不能优化到对每一层能一起判断：考虑如果选择了多个点其实相当于是能确定某个点的父亲是否在这个集合内，于是我们考虑逐位确定：假设现在考虑所有点父节点编号二进制位第 $i$ 位是啥，我们把所有 $d-1$ 层二进制第 $i$ 位是 $1$ 的扔进去查询就好了。发现询问距离为 $1$ 的询问会影响上面和下面一层，于是考虑按层 $\bmod 3$ 分类，就不会有干扰的问题了。F你觉得我会神奇 $O(\frac{n^3}{\log n})$的 $3500$ 计数题？大概省选的时候会补。现在已经补了。这种没见过的题就是要找性质然后对性质dp，具体过程是（判定性问题 $\to $ 状态和转移 $\to $ 优化）判定性问题如果判定一个串是否是 $p$ 密度的呢？我们发现如果一个串是 $p$ 密度的，首先 $1 \ldots c$ 都要出现了，然后我们删掉 $1\ldots c$ 这一段的所有的数，剩下的应该是一个 $p-1$ 密度的串。设计状态有了这个东西就可以 dp 了：考虑设 $f_{i,j}$ 表示强制最后一次选的是 $i$，$j$ 密度串的个数，转移的时候只需要预处理 $g_{l,r}$ 表示区间 $[l,r]$ 的子序列数量，满足 $1 \ldots c$ 只出现了一次，并且选择 $a_r$ 后才满足 $1 \ldots c$ 都出现了一次（否则会算重）。这个可以…

CF 1086 题解
type: item
date: 2020-09-19T00:04:00+08:00
description: 这场 C sb了敲错一个字符爆零了。。最后发现 D 也很简单。策略以后还是要先做掉简单题，然后难题调不出来就换题，先大体浏览一下题目再做（说不定后面有我擅长的题呢）A我们按照 $x$ 坐标排序，设 $y$ 坐标处于中间位置的点是 $a$，另外的点是 $b,c$，那么可以先连两条过 $b,c$ 垂直于 $a$ 所在的水平线上的两条线，然后连一下 $a$ 的水平线即可。B注意到可以设置为 $0$ 边，并且直径的两个端点一定是叶子，设叶子有 $l$ 个，可以给每个叶子上面的边分配 $\frac{s}{l}$，答案是 $2\frac{s}{l}$。C类似数位 dp 枚举卡上界/下界分别卡到哪里，能得到一堆限制区间，现在变成了将区间和区间内的点配对的问题，可以按照左端点排序每次取右端点最小的区间配对。但是我把 $n$ 和 $k$ 写反了。。。要不然早就过了D发现一个点前后是独立的，分别考虑。考虑它的前缀：这个点能胜利要么前面所有的点都和它平局或者被它打败，要么有能打败它的和能被它打败的。证明考虑每一对能打败它的和能被它打败的点即可。统计答案的时候我们枚举每种动作，如果一个点合法，当且仅当它的前缀/后缀不会出现仅存在能打败它的动作，但是发现这是若干个区间的交，不是很好做，于是我们容斥后去求不合法的区间的并，用 set 维护一下每种颜色编号最大和最小的位置，树状数组维护一下数字的排名就行了。E先思考有多少个好的矩阵：这个矩阵要求这一行是上一行的错排，设错排为 $h(n)$，那么数量就是 $n!h(n)^{n-1}$。字典序问题肯定是枚举到哪个位置失配，由于第一行没有错排限制所有可以先特判掉。接下来考虑剩下的一般情况：假设我们考虑到 $(i,j)$ 失配，首先下面的 $n-j$ 行方案都是错排，也就是 $h(n)^{n-j}$，现在只需要考虑这一行：先考虑暴力枚举 $a_{i,j}$ 是啥，然后发现这种问题相当于钦定了若干数的错排问题，而这种问题的答案只和长度与有效的限制有关（有效的限制指这个数之前都没被用过，也就是不属于可以随便放的状态）。这里有一个容斥式子可以做，但是需要 NTT。发现所有的方案乘上一个置换后是等价的，于是考虑设计 dp $f_{i,j}$ 表示长度为 $i$ 有 $j$ 条限制的方案数。那么有转移 $f_{i,j} = f_{i,j-1}-f_{i-1,j-1}$（相当于用全部的情况减去违反最后一个限制的情况）如果暴力枚举 $a_{i,j}$ 是啥能得到一个 $O(n^3)$ 的做法过不去，但是发现各种 $a_{i,j}$ 的不同之处仅在与它是不是属于一个有效的限制，所以只需要数一下可选的数有多少个是属于有效的限制并且 $< x$，多少不是并且 $<x$ ，可以用桶+树状数组维护。注意要特判一下这个位置和上一行不能相等即可。一类求排名的问题也就是求字典序比它小个数，不要被骗了。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 2000+5; const int ha = 998244353; int f[MAXN][MAXN]; inline void add(int &x,int y){ x += y;if(x >= ha) x -= ha; } // 长度为i的排列 有j个位置限制 inline void prework(){ f[0][0] = 0; f[1][0] = 1;f[1][1] = 0; FOR(i,2,MAXN-1){ f[i][0] = 1ll*f[i-1][0]*i%ha; FOR(j,1,i){ f[i][j] = f[i][j-1]; add(f[i][j],ha-f[i-1][j-1]); } } } int n,a[MAXN][MAXN]; int cnt[MAXN],now; struct …

CF 997 题解
type: item
date: 2020-09-17T21:15:00+08:00
description: A发现操作相当于花费 $x$ 消掉一个 $0$ 的连续段，或者是花费 $y$ 将两个连续段拼起来，显然如果使用了拼接操作就会拼到只剩一个，所以直接判断即可。B打表发现在 $n$ 较大的时候是个等差数列，小范围暴力即可。一个比较有理有据的做法是首先考虑我们先将集合转化为 $\{0,4,9,49\}$ 考虑，然后我们为了保证不重，必须限制 $4$ 的个数 $\leq 8$ 个，并且如果取了 $4$，那么为了去重也只能取 $\leq 4$ 个 $9$，没有取 $4$ 就可以取 $\leq \gcd(49,9)=9$ 个。剩下的用 $0$ 和 $49$ 填充即可。通过整体平移让某一个出现 $0$ 是很不错的套路，可以直接少考虑一个维度。C必然是容斥原理。我们去枚举多少行多少列是相同颜色的，设 $f(i,j)$ 表示 $i$ 行 $j$ 列每行每列相同颜色的方案数，答案就是：$$ \sum_{i=0}^n \sum_{j=0}^n [i+j \neq 0](-1)^{i+j+1}\binom n i\binom n j f(i,j) $$其中：$$ \begin{aligned} f(i,j) = \begin{cases} 3^{n(n-j)} \times 3^j ,&i=0\\ 3^{(n-i)n} \times 3^i, &j=0\\ 3^{(n-i)(n-j)} \times 3,& \text{otherwise} \end{cases} \end{aligned} $$接下来考虑如何优化：首先 $i=0$ 和 $j=0$ 的情况比较平凡，我们只需要考虑算：$$ -3\sum_{i=1}^n (-1)^i\binom n i\sum_{j=1}^n (-1)^{j}\binom n j 3^{(n-i)(n-j)} $$对后面用二项式定理，后面的式子等价于 $(3^{n-i}-1)^n-3^{(n-i)n}$，就可以 $O(n \log n)$ 计算了。同时算多个 $n$ 的答案感觉可以卷积。。不错以后出了。D首先要直观理解一下在图上怎么走路的：你从 $(u,v)$ 可以走到 $(u,w)$满足树 $2$ 上有边 $(v,w)$，树 $1$ 同理。主要是要观察到一个性质：两棵树起点确定，长度为 $x,y$ 的环能组合出长度为 $x+y$ 的环，方案是 $\binom {x+y} x$。所以我们对树分开处理，只需要对于每棵树处理出长度 $=i$ 的环的个数就行了（在环上每个点都要贡献一次），如果我们现在求 $1$ 号点的环个数，可以将这个点设为根，然后设 $f_{i,j}$ 表示从 $i$ 开始的长度为 $j$ 的环的数量。考虑写出生成函数 $F_i = \sum_{j} f_{i,j}x^j$，考虑如何用生成函数的形式刻画转移：首先我们可以算出 $G_i$ 表示经过 $i$ 一次的情况，显然有 $G_i = x^2\sum{v \in son_i} F_{v}$，$x^2$ 是因为要走回来，那么就可以得到 $F_i = \sum_{j \geq 0} G_i^j = \frac{1}{1-G_i}$，所以多项式求逆就可以求出来了。但是因为要求出所有点的答案，所以我们要考虑换根：实际上就是去掉/加入一些子树，先修改 $G$ 再修改 $F$ 即可。这样复杂度是 $O(nk \log k)$ 的，但是由于 $k$ 很小并且 NTT 常数巨大跑不过 $O(nk^2)$ 的做法。官方题解给的做法是用那个 dp 套在点分治上，也是很妙的，对这种类似路径条数和连通块的问题我们可以考虑点分治每次只 dp 分治区域内所有的点。E先考虑如果全局询问怎么做：因为是排列，限制可以拆成 $r-l = mx-mn$，并且我们发现一定有 $r-l \leq mx-mn$，也就是 $r \leq mx-mn+l$，所以我们枚举右端点，线段树维护所有左端点的 $mx-mn+l$，每次如果存在合法的区间值一定是最小值 $r$，记录最小值个数即可，维护单调栈每次更新即可。这个题是要对一个子区间全部做，相当于要维护历史贡献信息：对于这种题我们线段树上记一个值专门用来存答案，每次更新完右端点的操作后我们在根打一个答案标记，答案标记下传到某个儿子当且仅当这个点儿子的最小值和父亲的最小值相等，并且一定要在加法下传后再下传（因为前面的加法标记都是应该加完后判断的），然后查询就区间查询和就好了。建议看代码意会一下。。这个东西感觉是可以扩展的，好多利用线段树枚举左端点维护右端点的题都可以改改做了。核心思想还是每次修改前肯定先处理完标记再下传，那么统计答案的标记优先级一定小于修改的标记。#include <bits/stdc++.h> #define fi first #def…

CF 1418 题解
type: item
date: 2020-09-16T21:41:00+08:00
description: A考虑分步做合成 coal 和合成 craft 。发现我们做 $n$ 次替换后拥有的 stick 数量是 $nx-n+1$，首先要凑出 $k$ 个 coal，然后还要剩下来 $k$ 个 stick 合成，所以我们造 stick 的限制就有 $nx-n+1 \geq ky+k$，这样 $n$ 就是交易 stick 用掉的次数了，再加上 $k$（交易 coal 的次数）B把未被锁定的位置从大到小排序即可。因为无论如何放最后一个未锁定的位置的前缀和不会变，那么肯定先把所有最大的都用上去尽量 cover 掉小的贡献。Cdp。设 $f_{i,0/1}$ 表示打了前 $i$ 关，轮到玩家还是玩家的朋友打的最小代价，直接枚举转移即可。D假设两个位置选择的分别是 $x_1,x_2(x_1 < x_2)$，把坐标排好序后肯定存在一个分解点 $mid$，满足 $i \leq mid$ 都走到 $x_1$，并且 $i > mid$ 都走到 $x_2$。设第 $i$ 个坐标位置 $p_i$，发现这样的代价为 $p_n-p_1-(p_{mid+1}-p_{mid})$，所以实际上是要你支持插入，删除，维护相邻差的最大值，用两个 multiset 就可以了。E根据期望的线性性，我们只需要计算每一个 boss 对玩家的期望伤害即可。boss 可以分为两类：一类是会削玩家护盾耐久的，一类是螳臂当车的。对于会削玩家护盾耐久的，设这样的 boss 有 $m$ 个，能打到玩家的概率是 $\frac{m-a_i}{m}$（因为它在这 $m$ 个数的相对排名只有 $m$ 种情况，后面 $m-a_i$ 种是合法的）对于螳臂当车的 boss，设这样的 boss 有 $k$ 个，能打到玩家的概率是 $\frac{m+1-a_i}{m+1}$。（因为它只能选择 $m+1$ 个空插进去，后面 $m+1-a_i$ 个空是合法的）分开乘起来就行。多组询问只需要离线排序，变成了维护每次将一个削玩家耐久的变成螳臂当车的boss的操作，记录一下权值和就行了。F发现一个结论：对于任何一对 $x_1y_1 = x_2y_2(x_1 < x_2)$，都存在一对正整数 $a < b$，满足 $x_2 = \frac{x_1}{a}b,y_2 = \frac{y_1}{b}a$。[collapse status="false" title="证明"]设 $g=\gcd(x_1,x_2)$，我们构造 $a=\frac{x_1}{g},b = \frac{x_2}{g}$，不难发现 $\frac{x_1}{a}b = x_2$，接下来只需要证明 $b|y_1$即可。注意到 $b=\frac{x_2}{g} | \frac{x_2y_2}{g} = \frac{x_1y_1}{g}$，又因为有 $(b,\frac{x_1}{g}) = 1$，所以得到 $b|y_1$。[/collapse]因为 $a|x_1,b|y_1$，所以有效的 $(a,x_1)$ 只有 $O(n \log n)$ 对。现在我们去固定 $x_1$，考虑 $y_1$ 的种种限制：首先要保证 $y_1 \leq m$，其次还要保证 $\lceil \frac{L}{x_1}\rceil \leq y_1 \leq \lfloor \frac{R}{x_1} \rfloor$。我们考虑枚举一对 $(a,x_1)$，现在相当于要求快速询问是否存在一对 $(b,y_1)$ 满足如下条件：$$ \begin{aligned} y_1 \leq m\\ \lceil \frac{L}{x_1}\rceil \leq y_1 \leq \lfloor \frac{R}{x_1} \rfloor\\ \frac{x_1}{a}b \leq n\\ a < b \end{aligned} $$显然我们会贪心选择能选择的 $b$ 中最小的去判断第三个限制是否成立。第一个和第二个限制可以通过从小到大枚举 $x$ 双指针解决，第四个限制可以维护当前所有可选值的 set 解决，复杂度 $O(n \log^2 n)$。G确定性做法我们考虑枚举右端点，维护每个左端点是否合法。我们的目标是让对于每一种颜色，如果左端点区间是合法的，贡献就是 $0$，否则贡献是 $1$。那么一个左端点合法当且仅当这个位置的值是 $0$。我们每次加入一个点 $i$，设它前面第一个，第二个，第三个，第四个和它相等的是 $p_1,p_2,p_3,p_4$，我们只需要让 $(p_1,i]+1$，$(p_3,p_2]-1$，$(p_4,p_3]+1$ 即可。线段树维护最小值和最小值个数，支持区间加即可。基于这个做法我把题目小小加强了一下链接（不确定正确性详细维护方式可以见代码：#include …

CF 666 题解
type: item
date: 2020-09-15T21:48:33+08:00
description: A考虑 dp。设 $f_{i,0/1}$ 表示考虑到根是 $i$ 前缀，最后一次删除的串长度为 $2/3$ 的方案数。转移就判断一下两次长度相等是否子串相等即可。B这种最长的最短路链问题贪心超过两步都是错的。首先 $O(n^2)$ 预处理 $dis_{i,j}$ 表示 $i \to j$ 的最短路，注意到贪心一步是正确的，我们去枚举 $b,c$，预处理最远，次远，第三远的点即可（因为路径不能重复）。C首先可以写出一个dp：设 $f_{i,j}$ 表示考虑填了前 $i$ 位，匹配了 $t$ 的前 $j$ 位的方案数。转移：$$ \begin{aligned} \text{if }j \neq m :\\ f_{i,j} \to 25f_{i+1,j}\\ f_{i,j} \to f_{i+1,j+1}\\ \text{if } j = m:\\ f_{i,j} \to 26f_{i+1,j} \end{aligned} $$这种转移形式简单的计数问题可以抽象到网格图游走上：如果你当前在的坐标 $j \neq m$，可以选择走 $(1,0)$，方案 $25$，走 $(1,1)$ 方案数是 $1$；如果已经 $j=m$，那么只能走 $(1,0)$，方案数 $26$。发现 $(1,1)$ 的数量恰为 $m$；考虑整个操作序列，在最后一个 $(1,1)$ 后的 $(1.0)$ 贡献都是 $26$，前面都是 $25$。考虑枚举最后一个 $(1,1)$：$$ \sum_{i=m}^n \binom{i-1}{m-1}25^{i-m}26^{n-i} = \frac{26^n}{25^m}\sum_{i=0}^m \binom{i-1}{m-1} (\frac{25}{26})^i $$注意 $\sum m \leq 10^5$，所以本质不同的 $m$ 只会有 $\sqrt m$ 个，每次都预处理所有答案，复杂度 $O(n \sqrt m)$。D这题暴力就行了。我们先枚举每个点最终对应的点哪个坐标相等（可以看成是枚举在一条横线还是纵线上），然后分类讨论：首先如果存在交点一定选交点要不然点就不够用了。我们将所有的线去重之后分类讨论：两横两纵每个点都是确定的，判断是否是正方形后 $4!$ 枚举配对方案求答案即可。两横一纵（或两纵一横）我们确定了两个点和这个正方形的边长 $D$，所以另外两个点只有可能是坐标某一维 $\pm D$，对每一种情况 $4!$ 统计答案即可。两横或两纵我们考虑两横：首先确定了正方形的边长 $D$，一个暴力的想法枚举一个点，就能确定所有的点。假设现在上面的点是 $x_1,x_2$，下面的点是 $x_3,x_4$，不失一般性设当前枚举的两条竖线是 $x,x+D$。不失一般性我们设 $x_1,x_3$ 匹配 $x$，$x_2,x_4$ 匹配 $x+D$（这里可以通过枚举完成所有情况），那么答案就是 $\max\{|x_1-x|,|x_3-x|,|x_2-(x+D)|,|x_4-(x+D)|\}$，拆开变成四个坐标 $x_1,x_3,x_2-D,x_4-D$，只需要取最大值和最小值的中点左右挨个判断一下即可。代码太长了（170+），这里给出提交链接E先对所有的 $t$ 建出广义SAM，现在先考虑如何确定 $S[l,r]$ 对应的位置：我们先找到 $S[1,r]$ 对应的位置，不断跳 fail 并保证一直包含这个区间，需要用倍增预处理一下。然后就直接线段树合并一发维护处最大值和最大值的位置就行了。细节比较多，放一下代码：#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e5 + 5; struct Node{ int mx,ps; Node(int mx=0,int ps=-1) : mx(mx),ps(ps) {} friend N…