ZigZagK的博客 - 2022年8月
type: channel
link: https://zigzagk.top/2022/08/
description: Never give up fighting!
items: [后缀数组+复杂度分析]2022牛客暑期多校训练营7 I【Suffix Sort】题解
items: [KMP+后缀数组+主席树]2022牛客暑期多校训练营6 L【Striking String Problem】题解
items: [DP+复杂度分析]2022“杭电杯”中国大学生算法设计超级联赛（7）【Counting Good Arrays】题解
items: [Bluestein套路+多项式ln]2022“杭电杯”中国大学生算法设计超级联赛（7）1010【Connectivity of Erdős-Rényi Graph】题解
items: [容斥+多项式求逆]2022“杭电杯”中国大学生算法设计超级联赛（8）1013【Shattrath City】题解
items: [多项式exp]2022“杭电杯”中国大学生算法设计超级联赛（6）1003【Find the Number of Paths】题解
items: [珂朵莉树+线段树]2022“杭电杯”中国大学生算法设计超级联赛（5）1001【Pandaemonium Asphodelos: The First Circle (Savage)】题解
items: [回文自动机回退]2020 ICPC 昆明 F【Generating Strings】题解
items: [三维不重复数点]2022牛客暑期多校训练营4 E【Jobs (Hard Version)】题解

[后缀数组+复杂度分析]2022牛客暑期多校训练营7 I【Suffix Sort】题解
type: item
date: 2022-08-12T16:54:53+08:00
description: 题目概述Suffix Sort解题报告一直在想Hash，然后寄了……实际上应该分析一下性质。首先有一个比较显然的想法是将 $S$ 变为另一个数组，$a_i$ 表示 $S_i$ 与上一个相同字符的距离（如果不存在则为 $i$ ），然后当比较后缀 $i$ 和后缀 $j$ 时，把 $a_i$ 到 $a_n$ 中 $k-a_k<i$ 的那些位置改成 $0$ ，后缀 $j$ 同理，然后就可以直接比较 $a_{[i,n]}$ 和 $a_{[j,n]}$ 了。由于只有小写字符，因此最多只有 $26$ 个位置需要改成 $0$ ，所以如果把后缀 $i$ 和后缀 $j$ 结合起来考虑，会把 $a$ 分为 $52$ 个段，对于段的分割节点，我们特殊判断，而分割节点中间的连续段我们可以直接利用 $LCP$ 判断是否全相同。这样每次比较的复杂度就是 $O(26)$ 了，直接sort就可以得到排名，复杂度 $O(26n\log_2n)$ 。示例程序#include<cstdio> #include<algorithm> #define fr first #define sc second #define mp make_pair using namespace std; const int maxn=200000,maxi=26,LOG=17; int n,a[maxn+5],lst[maxi],ID[maxn+5];char s[maxn+5]; int SA[maxn+5],rk[maxn+5],ha[maxn+5],sc[(maxn<<1)+5]; int lg[maxn+5],RMQ[LOG+1][maxn+5]; int nxt[maxi][maxn+5],cnt[maxn+5]; pair<int,int> pos[maxn+5][maxi+5]; int who[maxn+5][maxi]; void Sort(int n,int m){ for (int i=0;i<=m;i++) ha[i]=0;for (int i=1;i<=n;i++) ha[rk[i]]++; for (int i=1;i<=m;i++) ha[i]+=ha[i-1];for (int i=n;i;i--) SA[ha[rk[sc[i]]]--]=sc[i]; } void MakeSA(int *s,int n,int m=255){ for (int i=1;i<=n;i++) rk[i]=s[i],sc[i]=i,sc[i+n]=0;Sort(n,m); for (int k=1,p=0;p<n;m=p,k<<=1){ p=0;for (int i=n-k+1;i<=n;i++) sc[++p]=i; for (int i=1;i<=n;i++) if (SA[i]>k) sc[++p]=SA[i]-k; Sort(n,m);for (int i=1;i<=n;i++) sc[i]=rk[i];rk[SA[1]]=p=1; for (int i=2;i<=n;i++) rk[SA[i]]=(p+=sc[SA[i-1]]!=sc[SA[i]] || sc[SA[i-1]+k]!=sc[SA[i]+k]); } for (int i=1,k=0;i<=n;i++){ if (k) k--; while (s[i+k]==s[SA[rk[i]-1]+k]) k++; RMQ[0][rk[i]]=k; } for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1; for (int j=1;(1<<j)<n;j++) for (int i=2;i+(1<<j)-1<=n;i++) RMQ[j][i]=min(RMQ[j-1][i],RMQ[j-1][i+(1<<j-1)]); } int LCP(int x,int y){ if (x>y) swap(x,y);x++; int k=lg[y-x+1]; return min(RMQ[k][x],RMQ[k][y-(1<<k)+1]); } bool cmp(const int &x,const int &y){ if (x==y) return false; for (int i=1;i<=cnt[x] && i<=cnt[y];i++){ if (pos[x][i].fr==n || pos[y][i].fr==n) return x>y; int Lx=pos[x][i].fr+1,Rx=(i<cnt[x]?pos[x][i+1].fr-1:n),lenx=Rx-Lx+1; int Ly=pos[y][i].fr+1,Ry=(i<cnt[y]?pos[y][i+1].fr-1:n),len…

[KMP+后缀数组+主席树]2022牛客暑期多校训练营6 L【Striking String Problem】题解
type: item
date: 2022-08-12T16:42:04+08:00
description: 题目概述Striking String Problem解题报告神仙题，根本想不到。记 $n$ 为 $S$ 长度，$m$ 为 $T$ 长度，$U_i$ 表示 $S[l_1,r_1]+\cdots+S[l_i,r_i]$ ，$len_i=r_i-l_i+1$ 。处理出 $T$ 的 $fail$ 数组，对 $S$ 先做一遍KMP，记录 $pre_i$ 表示 $S[1,i]$ 与 $T$ 的最大匹配长度，$cnt_i$ 表示 $S[1,i]$ 与 $T$ 的匹配次数。考虑在这个接起来的串上做KMP，定义 $M_i$ 表示 $U_i$ 与 $T$ 的最大匹配长度（即最大的 $len$ 使得 $U_i$ 末尾 $len$ 个与 $T$ 前 $len$ 个相同）。然后考虑从 $M_{i-1}$ 推到 $M_i$ 。第一种情况：$M_i$ 和 $M_{i-1}$ 无关，则我们需要求出 $S[l_i,r_i]$ 与 $T$ 的最大匹配长度 $len(len\le len_i)$ ，可以通过 $pre_{r_i}$ 跳 $fail$ 树得到。第二种情况：$M_i$ 从 $M_{i-1}$ 接一部分过来，假设保留的长度为 $D$ ，需要满足：$D$ 是 $M_{i-1}$ 的 $fail$ 树祖先，这样才能将 $T$ 平移过来。$T[D+1,D+len_i]=S[l_i,r_i]$ ，即 $LCP(T[D+1,m],S[l_i,n])\ge len_i$ ，可以通过求 $S+T$ 串的后缀数组求出LCP。我们对于每一个 $S[l_i,n]$ ，找出 $[rkL_i,rkR_i]$ 表示和 $S[l_i,n]$ 的 $LCP\ge len_i$ 的区间，那么只要 $T[D+1,m]$ 的 $rank$ 在这个区间内就说明 $T[D+1,D+len_i]$ 可以和 $S[l_i,r_i]$ 匹配。而我们要从 $M_{i-1}$ 的祖先中找出最大的满足的 $D$ ，则 $M_i=D+len_i$ 。考虑用权值主席树，每棵树存 $rank$ 对应的信息，就可以求出 $x$ 到根中 $[rkL_i,rkR_i]$ 中的最大值 $D$ 。在这两种情况中挑个大的就可以得到 $M_i$ ，为了后面处理方便，如果 $M_i=m$ ，则令 $M_i=fail[M_i]$ 。求出 $M_i$ 之后我们考虑如何求出答案。首先为了统一询问，我们把 $[L,R]$ 拆成 $[1,R]$ 减去 $[1,L+m-2]$ 。然后考虑求 $U[1,P]$ 的答案，我们可以先求出整段的 $U_i$ ，然后最后补上不完整的一段。继续考虑KMP的过程，之前已经匹配了 $M_{i-1}$ ，定义 $Solve(M,l,r)$ 表示在 $M$ 的基础上添上了 $S[l,r]$ ，产生的匹配数。类似上面，我们讨论两种情况：第一种情况：没有用到 $M$ ，则匹配数为 $cnt_{r}-cnt_{l+m-2}$ 。第二种情况：用到了 $M$ ，假设用到长度为 $D$ ，需要满足：$D$ 是 $M$ 的祖先。$T[D+1,m]=S[l,l+(m-D)-1]$ ，即 $LCP(T[D+1,m],S[l,n])\ge m-D$ 。$l+(m-D)-1\le r$ ，即 $D\ge m-(r-l+1)$ 。这次条件只和 $D$ 有关，因此我们需要另一个权值主席树，用于数出 $M$ 的祖先中包含 $rank(S[l,n])$ 的个数，可以通过标记永久化和单点查询求出。$M$ 祖先中满足条件的范围也可以通过 $fail$ 树上倍增求出。这两种情况累加起来就是 $Solve(M,l,r)$ ，令 $ans_i$ 表示 $U_i$ 的答案，则 $ans_i=ans_{i-1}+Solve(M_{i-1},l_i,r_i)$ 。最后查询 $U[1,P]$ 就是找到对应的 $ans_i$ ，并加上不完整的一段。示例程序#include<cstdio> #include<cctype> using namespace std; typedef long long LL; const int maxn=1e6,maxm=5e5,maxk=5e5,maxl=maxn+maxm,maxt=6e7,LOG=20; int n,m,K,Q,pre[maxn+5],cnt[maxn+5]; int l[maxk+5],r[maxk+5],len[maxk+5],L[maxk+5],R[maxk+5],M[maxk+5]; char s[maxn+5],t[maxm+5],a[maxl+5]; int SA[maxl+5],rk[maxl+5],ha[maxl+5],sc[(maxl<<1)+5]; int lg[maxl+5],RM…

[DP+复杂度分析]2022“杭电杯”中国大学生算法设计超级联赛（7）【Counting Good Arrays】题解
type: item
date: 2022-08-12T15:38:45+08:00
description: 题目概述HDU7217解题报告一个显然的想法：定义 $f_{i,j}$ 表示放了 $i$ 位，第 $i$ 位为 $j$ 的方案数，那么：$$ f_{i,j}=\sum_{d|j}f_{i-1,d} $$由于这题要求二维前缀和，考虑先求一次前缀和：$f_{i,j}$ 表示放了 $i$ 位第 $i$ 位小于等于 $j$ 的方案数，那么：$$ f_{i,j}=\sum_{k=1}^{j}f_{i-1,{\lfloor{j\over k}\rfloor}} $$如果没有那个 $1$ ，我们就只需要用到 $m$ 除法分块中所有的节点，这样就可以把第二位状态降到 $O(\sqrt m)$ 。考虑除了第一次之外都至少 $\times 2$ ，这样至多只会乘 $30$ 次，然后考虑如何统计贡献，其实就是考虑把这些 $\times k$ 的部分放进长度为 $n$ 的序列中，并且规定第一个位置前面的都删掉，其他位置为 $1$ ，最后求一遍前缀积得到要求的数组，这样考虑就能求出长度为 $[1,n]$ 的所有情况。因此稍微改变一下 $f_{i,j}$ 的转移。初值 $f_{1,j}=j$ ，转移：$$ f_{i,j}=\sum_{k=2}^{j}f_{i-1,{\lfloor{j\over k}\rfloor}} $$并且 $i$ 最大只有 $30$ 。不难发现转移 $j$ 的时候也是进行除法分块，因此这个转移的复杂度和杜教筛是一致的，即 $O(m^{3\over 4})$ 。因此复杂度为 $O(30m^{3\over 4})$ ，最后答案为：$$ \sum_{i=1}^{30}{n\choose i}f_{i,m} $$示例程序略有卡常，改了下数组访问顺序就过了。#include<cmath> #include<cstdio> using namespace std; typedef long long LL; const int maxs=31622<<1,MOD=1e9+7,LOG=32; int te,n,m,S;LL f[maxs+5][LOG]; int a[maxs+5],ID[2][maxs+5]; inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;} inline int MUL(int x,int y) {return (LL)x*y%MOD;} int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;} #define P(x) ((x)<=S?ID[0][x]:ID[1][m/(x)]) int main(){ for (scanf("%d",&te);te;te--){ scanf("%d%d",&n,&m); a[0]=0;S=sqrt(m); a[++a[0]]=m;ID[1][1]=a[0]; for (int l=2,r;l<=m;l=r+1){ r=m/(m/l);a[++a[0]]=m/l; a[a[0]]<=S?ID[0][a[a[0]]]=a[0]:ID[1][m/a[a[0]]]=a[0]; } for (int i=1;i<=a[0];i++) f[i][1]=a[i]; for (int j=a[0];j;j--){ for (int i=2;i<LOG;i++) f[j][i]=0; for (int l=2,r;l<=a[j];l=r+1){ r=a[j]/(a[j]/l); int x=P(a[j]/l),len=r-l+1; for (int i=2;i<LOG;i++) f[j][i]=ADD(f[j][i],MUL(len,f[x][i-1])); } } int C=1,ans=0; for (int i=1;i<LOG && i<=n;i++){ C=MUL(C,MUL(n-i+1,Pow(i,MOD-2))); ans=ADD(ans,MUL(C,f[P(m)][i])); } printf("%d\n",ans); } return 0; }

[Bluestein套路+多项式ln]2022“杭电杯”中国大学生算法设计超级联赛（7）1010【Connectivity of Erdős-Rényi Graph】题解
type: item
date: 2022-08-12T15:17:07+08:00
description: 题目概述HDU7218解题报告这道题看起来和城市规划很像，但是由于要考虑概率，所以卷积式子和求方案数的式子不一致。定义 $f_i$ 表示 $i$ 个点成为一个连通块的概率，考虑两个连通块的概率：$$ f_if_j(1-p)^{ij}{i+j\choose i}\to g_{i+j} $$考虑指数型生成函数我们就可以把 ${i+j\choose j}$ 去掉，但是 $f_if_j(1-p)^{ij}\to g_{i+j}$ 我们还是没有办法进行卷积。这时候利用Bluestein算法里面的一个套路：$ij={i+j\choose 2}-{i\choose 2}-{j\choose 2}$ ，就可以把 $ij$ 转化成卷积的形式：$$ {f_{i}\over (1-p)^{i\choose 2}}{f_j\over (1-p)^{j\choose 2}}\to{g_{i+j}\over (1-p)^{i+j\choose 2}} $$令 $f'_i$ 表示处理过之后的概率，$F(x)$ 是 $f'_i$ 的指数型生成函数，那么类似城市规划那道题，$F^i(x)\over i!$ 就是 $i$ 个连通块的概率。令 $g_i$ 表示 $i$ 个点无向图的概率，显然 $g_i=1$ 。令 $g'_i$ 表示处理过之后的 $i$ 个点无向图的概率，$G(x)$ 表示 $g'_i$ 的指数型生成函数，则 $G(x)=e^{F(x)}$ 。所以我们就知道了 $F(x)$ ，考虑枚举块数，统计答案：$$ (1-p)^{n\choose 2}[{x^n\over n!}]\sum_{i=1}^{n}i\cdot {F^i(x)\over i!}\\ =(1-p)^{n\choose 2}[{x^n\over n!}]\sum_{i=1}^{n}\cdot {F^i(x)\over (i-1)!}\\ =(1-p)^{n\choose 2}[{x^n\over n!}]F(x)\sum_{i=0}^{n}\cdot {F^i(x)\over i!}\\ =(1-p)^{n\choose 2}[{x^n\over n!}]F(x)e^{F(x)} $$多项式exp太慢了，为了避免就用 $G(x)$ 代替，那么答案就是 $(1-p)^{n\choose 2}[{x^n\over n!}]G(x)\ln G(x)$ 。另一种做法是考虑容斥，这也是城市规划的另一种做法。定义 $f_i$ 表示 $i$ 个点成为一个连通块的概率，$g_i$ 表示 $i$ 个点的概率（ $g_i=1$ ），那么：$$ f_0=0,f_i=1-\sum_{j=0}^{i-1}{i-1\choose j-1}(1-p)^{j(i-j)}f_jg_{i-j} $$即枚举第一个点所在连通块的大小，和上面同理，我们利用Bluestein套路，令 $f'_i={f_i\over (1-p)^{i\choose 2}(i-1)!}$ ，则：$$ f'_i={1\over (1-p)^{i\choose 2}(i-1)!}-\sum_{j=0}^{i-1}f'_jg'_{i-j} $$令 $F_1(x)$ ，$G(x)$ 为 $f',g'$ 对应的生成函数，$H(x)$ 为前面那项的生成函数，则：$$ F_1(x)=H(x)-F_1(x)G(x)\\ F_1(x)={H(x)\over 1+G(x)} $$考虑答案，由于期望可以拆分，我们考虑统计连通块大小为 $i$ 时的贡献，最后求和即可：$$ ans_n=\sum_{i=0}^{n}{n\choose i}(1-p)^{i(n-i)}f_ig_{n-i} $$这个式子也可以用套路处理，卷积一遍就可以求出所有的 $ans_n$ 。示例程序多项式ln#include<cstdio> #include<cctype> #include<algorithm> using namespace std; typedef long long LL; const int maxn=500000,maxt=1<<20,MOD=998244353; int te,Q,A,B,P,a[maxn+5]; int pw[maxn+5],INV[maxn+5],fac[maxn+5]; int wn[maxt+5],tem[maxt+5],G[maxt+5],H[maxt+5]; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,…

[容斥+多项式求逆]2022“杭电杯”中国大学生算法设计超级联赛（8）1013【Shattrath City】题解
type: item
date: 2022-08-12T13:45:44+08:00
description: 题目概述HDU7232解题报告比赛的时候想的是正着做，写完DP式子发现是个看起来很可做的东西，结果实际上不能做，寄掉了。实际上应该倒着做，$f_{i}$ 表示 $[1,n]$ 排列第一次出现在 $[i-n+1,i]$ 位置的方案数，那么最终答案就是 $n^m-\sum_{i=n}^{m}f_i\cdot n^{m-i}$ 。考虑容斥转移（随便放，减去上次放和这次不重叠，减去上次放和这次重叠）：$$ f_i=n^{i-j}n!-\sum_{j=n}^{i-n}f_j\cdot n^{i-j-n}n!-\sum_{j=i-n+1}^{i-1}f_j\cdot (i-j)! $$由于 $f_i$ 下标从 $n$ 开始不方便，因此考虑令 $g_i=f_{i+n}$ ，则：$$ g_i=n^i n!-\sum_{j=0}^{i-n}g_j\cdot n^{i-j-n}n!-\sum_{j=i-n+1}^{i-1}g_j\cdot (i-j)! $$令 $G(x)$ 为 $g_i$ 的生成函数，令 $A(x)=\sum_{i=0}^{\infty}n^in!\cdot x^i,B(x)=\sum_{i=1}^{n-1}i!\cdot x^i$ ，则：$$ G(x)=A(x)-x^nA(x)G(x)-B(x)G(x)\\ G(x)={A(x)\over 1+x^nA(x)+B(x)} $$多项式求逆就行了。示例程序#include<cstdio> #include<cctype> #include<algorithm> using namespace std; typedef long long LL; const int maxn=200000,maxt=1<<19,MOD=998244353; int te,n,m,fac[maxn+5],ans; int wn[maxt+5],tem[maxt+5],A[maxt+5],B[maxt+5],G[maxt+5]; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); lst=='-'?x=-tot:x=tot;return EOLN(ch); } struct fastO{ int si;char buf[100000]; fastO() {si=0;} void putc(char ch){ if (si==100000) fwrite(buf,1,si,stdout),si=0; buf[si++]=ch; } ~fastO() {fwrite(buf,1,si,stdout);} }fo; template<typename T> void writei(T x,char ch='\n'){ int len=0,buf[100]; if (x<0) fo.putc('-'),x=-x; do buf[len++]=x%10,x/=10; while (x); while (len) fo.putc(buf[--len]+48); fo.putc(ch); } inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;} inline int MUL(int x,int y) {return (LL)x*y%MOD;} int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;} void Make(int n) {fac[0]=1;for (int i=1;i<=n;i++) fac[i]=MUL(fac[i-1],i);} void NTTPre(){ int x=Pow(3,(MOD-1)/maxt); wn[maxt/2]=1; for (int i=maxt/2+1;i<maxt;i++) wn[i]=MUL(wn[i…

[多项式exp]2022“杭电杯”中国大学生算法设计超级联赛（6）1003【Find the Number of Paths】题解
type: item
date: 2022-08-05T15:22:00+08:00
description: 题目概述HDU7199解题报告多项式套路题，需要把题目中两种路径对应到比较容易处理的多项式形式。首先是 $i\to i+1$ ，有 $n+k-i$ 条路径，这个形式不太友好，因此我们考虑把整个序列反过来，即 $i$ 点变为 $n+k-i$ 点，这样就变成了 $i\to i-1$ 有 $i$ 条路径，就和下标对应起来了。翻转过后，第二种路径就变成了 $i\to i+x$ 有 $a_x$ 条路径。接下来考虑每轮的转移，定义 $f_{i,j}$ 表示走了 $i$ 步，停在 $j$ 的方案数（初值 $f_{0,n-1}=1$ ），那么：$$ f_{i,j}=(j+1)f_{i-1,j+1}+\sum_{x=1}^{n-1}a_xf_{i-1,k-x}=(j+1)f_{i-1,j+1}+\sum_{k=0}^{j-1}a_{j-k}f_{i-1,k} $$后面是卷积形式，而前面由于我们已经把下标和权值对应了，因此不难发现如果用多项式表示，这是求导的过程。定义 $F_i(x)$ 为 $f_{i}$ 的生成函数，令 $A(x)=\sum_{i=1}^{n-1}a_ix^i$ ，那么：$$ F_i(x)=F_{i-1}'(x)+A(x)F_{i-1}(x) $$这个形式让我们想到构造 $P_i(x)=e^{G(x)}F_i(x)$ ，因为：$$ P_i'(x)=e^{G(x)}G'(x)F_i(x)+e^{G(x)}F_i'(x)=e^{G(x)}[F_i'(x)+G'(x)F_i(x)] $$因此如果让 $G'(x)=A(x),G(x)=\int A(x)dx$ 就可以让后面出现 $F_i'(x)+A(x)F_i(x)$ ，从而：$$ P_i'(x)=e^{G(x)}[F_i'(x)+A(x)F_i(x)]=e^{G(x)}F_{i+1}(x)=P_{i+1}(x) $$这样我们只要求出 $P_0(x)=e^{G(x)}F_0(x)=x^{n-1}e^{G(x)}$ ，然后求 $k$ 阶导就可以得到 $P_k(x)$ ，最后 $F_k(x)={P_k(x)\over e^{G(x)}}$ 。示例程序#include<cstdio> #include<cctype> #include<algorithm> using namespace std; typedef long long LL; const int maxt=1<<20,MOD=998244353; int te,n,K,A[maxt+5]; int fac[maxt+5],INV[maxt+5]; int wn[maxt+5],tem[maxt+5],G[maxt+5],P[maxt+5],F[maxt+5]; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); lst=='-'?x=-tot:x=tot;return EOLN(ch); } struct fastO{ int si;char buf[100000]; fastO() {si=0;} void putc(char ch){ if (si==100000) fwrite(buf,1,si,stdout),si=0; buf[si++]=ch; } ~fastO() {fwrite(buf,1,si,stdout);} }fo; template<typename T> void writei(T x,char ch='\n'){ int len=0,buf[100]; if (x<0) fo.putc('-'),x=-x; do buf[len++]=x%10,x/=10; while (x); while (len) fo.putc(buf[--len]+48); fo.putc(ch); } inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;} inline…

[珂朵莉树+线段树]2022“杭电杯”中国大学生算法设计超级联赛（5）1001【Pandaemonium Asphodelos: The First Circle (Savage)】题解
type: item
date: 2022-08-03T19:43:04+08:00
description: 题目概述HDU7185解题报告其实并不难。由于每次区间操作都是直接覆盖成一种颜色，所以我们可以考虑用set维护所有的颜色相同的线段，然后每次操作就是对set中的线段进行分裂以及合并，复杂度分析和线段树的分裂与合并是一样的，总共需要分裂或者合并 $O(q)$ 次（在随机数据下，这种做法被称为珂朵莉树，因为随机数据下块数不超过 $\log\log n$ ，虽然和这题没什么关系）。然后对于颜色整体加和单点查询，就利用经典的技巧：维护整体加的tag，然后每次区间 $[L,R]$ 颜色转换时，把更改颜色的贡献区间加到 $[L,R]$ 上，例如 $pos$ 位置从 $c$ 颜色变成了 $d$ 颜色，列出等式 $tag_c+ask(pos)=tag_d+ask'(pos)$ ，得到 $ask'(pos)-ask(pos)=tag_c-tag_d$ ，因此进行 $[L,R]$ 上整体加 $tag_c-tag_d$ 即可。示例程序这个 $1$ 操作说的最近 $2c$ 个点是真的最近 $2c$ 个点……如果顶到头就需要往另一边扩展（玩文字游戏是吧）。#include<set> #include<cstdio> #include<cctype> using namespace std; typedef long long LL; const int maxq=100000,maxt=2e7; int te,n,Q;LL tag[maxq+5]; struct node{ int L,R,c; node(int l=0,int r=0,int w=0) {L=l;R=r;c=w;} bool operator < (const node &a) const {return L<a.L;} }; typedef set<node>::iterator SI; set<node> S;SI it,l,r; int pl,ro,ls[maxt+5],rs[maxt+5];LL sum[maxt+5]; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); lst=='-'?x=-tot:x=tot;return EOLN(ch); } struct fastO{ int si;char buf[100000]; fastO() {si=0;} void putc(char ch){ if (si==100000) fwrite(buf,1,si,stdout),si=0; buf[si++]=ch; } ~fastO() {fwrite(buf,1,si,stdout);} }fo; template<typename T> void writei(T x,char ch='\n'){ int len=0,buf[100]; if (x<0) fo.putc('-'),x=-x; do buf[len++]=x%10,x/=10; while (x); while (len) fo.putc(buf[--len]+48); fo.putc(ch); } inline int newnode() {pl++;ls[pl]=rs[pl]=sum[pl]=0;return pl;} void Insert(int &p,int L,int R,LL k,int l=1,int r=n){ if (!p) p=newnode(); if (L==l && r==R) {sum[p]+=k;return;} int mid=l+(r-l>>1); if (R<=mid) Insert(ls[p],L,R,k,l,mid); else if (L>mid) Insert(rs[p],L,R,k,mid+1,r); else Insert(ls[p],L,mid,k,l,mid),Insert(rs[p],mid+1,R,k,mid+1,r); } LL Ask(int p,int…

[回文自动机回退]2020 ICPC 昆明 F【Generating Strings】题解
type: item
date: 2022-08-03T15:23:00+08:00
description: 题目概述Generating Strings解题报告裸的回文自动机回退。对于一个长度为 $len$ 的回文串，在 $s$ 中出现一次的权值为 $(N-len+1)\cdot26^{N-len}$ 。对于每个节点记录 $sum_p$ 表示 $p$ 在 $fail$ 树上所有祖先的权值和，如果插入一个字符后停在了 $p$ ，那么就会获得 $sum_p$ 的权值。为了防止暴力回退复杂度爆炸，需要记录转移数组。示例程序#include<cstdio> #include<cctype> using namespace std; typedef long long LL; const int maxn=500000,maxt=1000000,maxi=26,MOD=1e9+7; int te,N,m,n,pw[maxn+5];char s[maxt+5]; int pl,pb,son[maxt+5][maxi],qui[maxt+5][maxi],len[maxt+5],fai[maxt+5]; int sum[maxt+5],pos[maxt+5],si[maxt+5],who[maxt+5],ans; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); lst=='-'?x=-tot:x=tot;return EOLN(ch); } char getlwr() {char ch=readc();while (!islower(ch)) ch=readc();return ch;} int reads(char *s){ int len=0;char ch=getlwr(); while (islower(ch)) s[++len]=ch,ch=readc(); s[len+1]=0;return len; } struct fastO{ int si;char buf[100000]; fastO() {si=0;} inline void putc(char ch){ if (si==100000) fwrite(buf,1,si,stdout),si=0; buf[si++]=ch; } ~fastO() {fwrite(buf,1,si,stdout);} }fo; template<typename T> void writei(T x,char ch='\n'){ static int len=0,buf[100]; if (x<0) putchar('-'),x=-x; do buf[len++]=x%10,x/=10; while (x); while (len) fo.putc(buf[--len]+48); fo.putc(ch); } inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;} inline int MUL(int x,int y) {return (LL)x*y%MOD;} inline int newnode() {pl++;for (int i=0;i<maxi;i++) son[pl][i]=qui[pl][i]=0;return pl;} inline int val(int p) {return len[p]<=N?MUL(N-len[p]+1,pw[N-len[p]]):0;} void Extend(int i){ int c=s[i]-'a';if (i-len[pb]-1<1 || s[i-len[pb]-1]-'a'!=c) pb=qui[pb][c]; who[i]=pb; if (!son[pb][c]){ int u=newnode(),k=fai[pb];len[u]=len[pb]+2; if (s[i-len[k]-1]-'a'!=c) k=qui[k][c];k=son[k][c]; for (int i=0;i<m…

[三维不重复数点]2022牛客暑期多校训练营4 E【Jobs (Hard Version)】题解
type: item
date: 2022-08-03T13:43:17+08:00
description: 题目概述Jobs (Hard Version)解题报告首先我们先考虑二维不重复数点问题：不难发现按照 $x$ 排序后，只有 $y$ 递降的那些点是有用的，其他点肯定都被包含在了某些点中。假设前一个点为 $(x_1,y_1)$ ，后一个点为 $(x_2,y_2)$ ，那么可以在 $(x_1,y_1)$ 标记 $1$ ，$(x_2,y_1)$ 标记 $-1$ ，最后做一遍二位前缀和，这样就可以避免重复计数。考虑扩展到三维，按照 $x$ 递增的顺序考虑 $(y,z)$ 。对于 $x$ ，如果没有新的 $(y,z)$ ，那么 $x$ 当前的二维局面和 $x-1$ 是一致的，我们可以延续过来。但是如果需要新添加 $(y,z)$ ，在 $(y,z)$ 右上角的点都会被删除。因此考虑用set维护二维局面，当加入和删除点时，由于与上一个局面不同，因此我们需要在这些位置打上 $+1$ 或 $-1$ 标记来修正。最后做一次三维前缀和就可以得到答案。为了方便，建议刚开始向set中添加左上角点 $(0,MAX+1)$ 以及右下角点 $(MAX+1,0)$ 。示例程序#include<set> #include<cstdio> #include<cctype> #include<random> #include<algorithm> #define fr first #define sc second #define mp make_pair #define A first #define B second.first #define C second.second using namespace std; typedef long long LL; const int maxn=1000000,maxq=2000000,maxm=1000000,maxa=400,MOD=998244353; int n,Q,seed,f[maxa+5][maxa+5][maxa+5],ans[maxq+5]; int m;pair<int, pair<int,int> > a[maxm+5]; set< pair<int,int> > S;set< pair<int,int> >::iterator it; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); lst=='-'?x=-tot:x=tot;return EOLN(ch); } inline void Update(int A,set< pair<int,int> >::iterator it,int x){ f[A][it->fr][it->sc]+=x; f[A][next(it)->fr][it->sc]-=x; } inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;} inline int MUL(int x,int y) {return (LL)x*y%MOD;} int main(){ readi(n);readi(Q); for (int i=1;i<=n;i++){ readi(m); for (int i=1;i<=m;i++) readi(a[i].A),readi(a[i].B),readi(a[i].C); sort(a+1,a+1+m); S.clear();S.insert(mp(0,maxa+1));S.insert(mp(maxa+1,0)); for (int i=1;i<=m;i++){ int A=a[i].A;pair<int,int> p=a[i].sc; it=prev(S.upper_bound(p)); if (it->sc<=p.sc) continue; Update(A,it,-1); for (it++;it->sc>=p.sc;it=S.erase(it)) Update(A,it,-1); i…