ZigZagK的博客 - 2022年9月
type: channel
link: https://zigzagk.top/2022/09/
description: Never give up fighting!
items: [离线+后缀自动机+LCT]2022牛客暑期多校训练营（加赛）C【Cmostp】题解
items: [离线+可持久化树+线段树分治+并查集按秩合并+哈希]2022牛客暑期多校训练营8 I【Equivalence in Connectivity】题解

[离线+后缀自动机+LCT]2022牛客暑期多校训练营（加赛）C【Cmostp】题解
type: item
date: 2022-09-25T20:14:41+08:00
description: 题目概述Cmostp解题报告建出SAM，考虑离线，每次添加一个前缀节点 $p_i$ 的时候，就是把 $p_i$ 到 $fail$ 树根路径上的节点的最右终止端点改为 $i$ 。查询 $[L,R]$ 时，只要当前最右终止端点在 $[L,R]$ 范围内的节点都可以计入答案，节点 $x$ 产生的贡献为 $MAX_x-MAX_{fail_x}$ 。考虑如何维护最右终止端点。我们可以利用LCT，每次 $p_i$ 往上更新其实就是Access操作，每次更新的均摊复杂度是 $O(\log_2n)$ 的。然后利用树状数组查询最右终止端点在 $[L,R]$ 范围内的节点贡献之和。复杂度是 $O(n\log^2_2n+q\log_2n)$ ，但其实只有Access的LCT+树状数组跑得飞快。示例程序#include<cstdio> #include<cctype> #include<algorithm> #define fr first #define sc second #define mp make_pair using namespace std; typedef long long LL; const int maxn=500000,maxt=maxn<<1,maxi=26; int n,Q,ID[maxn+5];char s[maxn+5]; int pl,ro,fai[maxt+5],son[maxt+5][maxi],MAX[maxt+5],val[maxt+5]; int fa[maxt+5],to[maxt+5][2],pos[maxt+5],tag[maxt+5];LL sum[maxt+5]; pair<pair<int,int>,int> q[maxn+5]; LL ans[maxn+5],c[maxn+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); } int reads(char *s){ int len=0;char ch=readc(); while (!islower(ch)) {if (ch==EOF) return EOF;ch=readc();} while (islower(ch)) s[++len]=ch,ch=readc(); s[len+1]=0;return len; } 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); if (ch) fo.putc(ch); } inline int newnode() {pl++;return pl;} int Extend(int p,int c,int id){ int np=newnode();MAX[np]=MAX[p]+1;ID[id]=np; while (p && !son[p][c]) son[p][c]=np,p=fai[p]; if (!p) {fai[np]=ro;return np;} int q=son[p][c];if (MAX[p]+1==MAX[q]) {fai[np]=q;return np;} int n…

[离线+可持久化树+线段树分治+并查集按秩合并+哈希]2022牛客暑期多校训练营8 I【Equivalence in Connectivity】题解
type: item
date: 2022-09-06T19:40:18+08:00
description: 题目概述Equivalence in Connectivity解题报告好像确实有维护动态图的方法……但是可能是考场上写不出的那种……考虑离线，建出可持久化树，如果用并查集维护图的连通性，会发现不能维护删边，因此我们考虑如何只进行加边操作和撤销。可持久化树中，如果在 $t$ 点加入了 $(x,y)$ 边，我们可以认为 $(x,y)$ 在 $t$ 的DFS序 $[in_t,out_t]$ 都出现了，而如果 $t$ 点是删边，则认为是把 $[in_t,out_t]$ 中的 $(x,y)$ 边删掉。因此实际上对于每条边，都可以拆成若干个连续的区间，表示含有这条边的区间。这样我们只需要利用线段树分治就可以实现只加边和撤销而不删边。考虑如何维护区间，首先先给每条边都标号，记录 $last_i$ 表示 $i$ 边当前处理到的DFS序。做DFS，处理到 $t$ 点时，假设边的标号为 $i$ ：加边：入栈时，将 $last_i$ 更新为 $in_t$ 。出栈时，说明 $last_i$ 到 $out_t$ 都含有 $i$ 边，加入线段树中。删边：入栈时，说明 $last_i$ 到 $in_t-1$ 都含有 $i$ 边，加入线段树中。出栈时，将 $last_i$ 更新为 $out_t+1$ 。由于保证了加边和删边都合法且不重复，因此入栈和出栈时就可以确定区间。而刚开始给的边可以认为是刚进入DFS时的加边操作。最后考虑如何比较两张图的连通性，可以使用这样的哈希：给每个点都随机一个权值，然后对于每个连通块 $i$ ，权值为 $sum_i\cdot MIN_i$ ，$sum_i$ 表示 $i$ 连通块所有点权值的异或，$MIN_i$ 表示 $i$ 连通块的最小值。一张图的权值为所有连通块权值的加和。示例程序#include #include<vector> #include<random> #include<cstdio> #include<cctype> #include<algorithm> #define fr first #define sc second #define mp make_pair using namespace std; typedef unsigned long long ULL; const int maxn=100000,maxm=200000,maxt=maxn<<2,maxp=5e6,BA=999917; int te,K,n,m,X[maxn+5],Y[maxn+5]; mt19937_64 mrand(164984); ULL ha[maxn+5]; int cnt;map<pair<int,int>,int> f; int E,lnk[maxn+5],nxt[maxn+5],to[maxn+5]; struct Data {int x,y,fl;} q[maxn+5]; int lt[maxn+5],rt[maxn+5],who[maxn+5]; int lst[maxm+5]; vector< pair<int,int> > e[maxt+5]; ULL fat[maxn+5],rk[maxn+5],sum[maxn+5],MIN[maxn+5],HA; int top;pair<ULL*,ULL> stk[maxp+5]; int ID[maxn+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…