现在是北京时间2022/7/27-21:20，距离比赛打完已经过去了2天，已经积累了牛客3还有杭电3没有写...明天又要打杭电4...这里就好像一个队列，当当前
size==2就在push前pop队首一样。
比赛链接:"蔚来杯"2022牛客暑期多校训练营3
这一次在封榜后怒学一手后缀自动机(SAM)，然后套了自己线段树的板子怒交一发H竟然过了，解绑后来到了史无前例的rk115。
C.Concatenation（排序）
题意：给你$n(1\leq n\leq 2e6)$的字符串，总字符串长度不超过$2e7$，求将其拼接的字典序最小的字符串。PS:出题人最后面说如果你用的算法是$O(nlogn)$，Good luck。
例如00,12,121三者应该是0012112，如果是0012121会发现比之前的要大。
思路：聪明的人一开始可能会看就是对这些排个序，然后输出，其实样例都过不去，这个题我是在OI时候做过原题，因为比较的是二者每次选最优的，其实比较a+b<b+a即可，但是这时间复杂度我一直不敢交...
听说$O(nlogn)$卡的很死，比如引用符号&没有加，则需要多两次的拷贝构造，这样常数很大过不去..
代码：
sort(s+1,s+n+1,[](const string& a,const string& b){
return a+b<b+a;
});
A.Ancestor（LCA，DFS序）
题意：给你都有$n(1\leq n\leq 10^5)$个结点的树$A$和树$B$并且两棵树每个点都有一个权值$a_i,b_i$，给你$k$个数字$x_1,x_2,...,x_k(x_i\in A,B)$，你需要删除一个点，求其他的点的在$A$树的剩下点$lca$的权值$a_{lca}$严格大于在$B$树剩下点的$b_{lca}$的删除的方案数。
思路：在这篇文章DFS序 - CarryNotKarry详细讲述了什么是DFS序，以及什么用法。这个题用到了结论就是：若干个点的$LCA$也就是DFS序最大的以及最小的两个结点的$LCA$。
所以这个题对于每一棵树不必要每次都对每个点都进行logn的$LCA$，只需要预处理出来DFS序，然后对于删除的情况分类，也就是将这$k$个点按照DFS序从小到大变成新的$x_1,x_2,...,x_k$，那么分为三种情况：
- 删除$x_1$，那么$anc=lca(x_2,x_k)$;
- 删除$x_{2...k-1}$，那么$anc=lca(x_1,x_k)$;
- 删除$x_k$，那么$anc=lca(x_1,x_{k-1})$.
所以对两个树都这样预处理之后，只需要判断删除的点是哪个即可.
我觉得这个题不应该现场过867个队伍...至少考察的挺多..
代码：
struct node
{
int to,next;
}edge1[N<<1],edge2[N<<1];
int head1[N],head2[N],cnt1,cnt2,dfn1[N],dfn2[N],dep1[N],dep2[N];
int lg2[N],f[N][21],g[N][21];
int cnte1,cnte2;
int typeA[N],typeB[N],resA,resB;
inline void add1(int x,int to)
{
edge1[++cnte1].to = to;
edge1[cnte1].next = head1[x];
head1[x] = cnte1;
}
inline void add2(int x,int to)
{
edge2[++cnte2].to = to;
edge2[cnte2].next = head2[x];
head2[x] = cnte2;
}
void build1(int x,int pre)
{
dep1[x]=dep1[pre]+1;
dfn1[x] = ++cnt1;
f[x][0]=pre;
for (int i=1;i<=20;i++)
f[x][i]=f[ f[x][i-1] ][i-1];
for (int i=head1[x];i;i=edge1[i].next)
if (edge1[i].to!=pre)
build1(edge1[i].to,x);
}
int lca1(int x,int y)
{
if (dep1[x]<dep1[y]) swap(x,y);
while (dep1[x]>dep1[y])
x=f[x][lg2[dep1[x]-dep1[y]]];
if (x==y) return x;
for (int i=lg2[dep1[x]];i>=0;i--)
if (f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
void build2(int x,int pre)
{
dep2[x]=dep2[pre]+1;
dfn2[x] = ++cnt2;
g[x][0]=pre;
for (int i=1;i<=20;i++)
g[x][i]=g[ g[x][i-1] ][i-1];
for (int i=head2[x];i;i=edge2[i].next)
if (edge2[i].to!=pre)
build2(edge2[i].to,x);
}
int lca2(int x,int y)
{
if (dep2[x]<dep2[y]) swap(x,y);
while (dep2[x]>dep2[y])
x=g[x][lg2[dep2[x]-dep2[y]]];
if (x==y) return x;
for (int i=lg2[dep2[x]];i>=0;i--)
if (g[x][i]!=g[y][i])
x=g[x][i],y=g[y][i];
return g[x][0];
}
struct node1
{
int x,id;
node1(){}
node1 (int _x,int _id):x(_x),id(_id){}
}aa[N],bb[N];
inline bool cmp(node1 &a,node1 b)
{
return a.x<b.x;
}
inline void Case_Test()
{
cin>>n>>k;
for (int i=2;i<=N-2;i++)
lg2[i]=lg2[i>>1]+1;
for (int i=1;i<=k;i++)
cin>>ky[i];
for (int i=1;i<=n;i++)
cin>>a[i];
for (int i=2;i<=n;i++)
{
cin>>x;
add1(x,i);
}
for (int i=1;i<=n;i++)
cin>>b[i];
for (int i=2;i<=n;i++)
{
cin>>x;
add2(x,i);
}
build1(1,0);
build2(1,0);
for (int i=1;i<=k;i++)
{
x = ky[i];
aa[i] = {dfn1[x],x};
bb[i] = {dfn2[x],x};
}
sort(aa+1,aa+k+1,cmp);
sort(bb+1,bb+k+1,cmp);
//----------A:1,k----------
resA = a[ lca1(aa[1].id,aa[k].id) ];//A :1~k
int res1,res2,res3;//B: (1->1~k),(2->2~k),(3->1~k-1)
res1 = b[ lca2(bb[1].id,bb[k].id) ];
res2 = b[ lca2(bb[2].id,bb[k].id) ];
res3 = b[ lca2(bb[1].id,bb[k-1].id) ];
ans = 0;
for (int i=1;i<=k;i++)//B
{
x = bb[i].id;
if (dfn1[x]==aa[1].x || dfn1[x]==aa[k].x) continue;
if (i==1) ans += (resA>res2);
else if (i==k) ans += (resA>res3);
else ans += (resA>res1);
}
//----------A:删1------------
resA = a[ lca1(aa[2].id,aa[k].id) ];//A :2~k
x = aa[1].id;
if (dfn2[x]==bb[1].x) ans += (resA>res2);
else if (dfn2[x]==bb[k].x) ans += (resA>res3);
else ans += (resA>res1);
//----------A:删k------------
resA = a[ lca1(aa[1].id,aa[k-1].id) ];//A :1~k-1
x = aa[k].id;
if (dfn2[x]==bb[1].x) ans += (resA>res2);
else if (dfn2[x]==bb[k].x) ans += (resA>res3);
else ans += (resA>res1);
cout<<ans;
}
J-Journey（01BFS）
题意：给你$n(1\leq n\leq 500000)$的十字路口，每个路口有$4$个方向，右转是不需要耗费时间的，其他需要耗费一点时间。然后给你一开始的起始位置和终止位置，求最小的时间。
思路：这个题主要是题目难读懂，在牛客反应也米有用，都想开喷了...实际上给你的$4$个方向下一个是上一个的右转，例如i=1时候0,0,3,4表示如果你现在在(3,1)的位置（这个表示在3号十字路口往1号式子路口那条有向线段上），你往右拐变成了(1,4)是不需要花费的，从(3,1)变成了(1,4)其实就是拐了个湾。理解了这个之后就好多了。
那么现在来看进行BFS，一共只有两种权值，一种是右转花费0，一种是其他选项（左转，直走，掉头）花费1。可以用Dijkstra最短路来做。
但是我这里用更快的01BFS：将权值$0$的放在双端队列(deque)前面，权值$1$的放在deque的后面。这样保证取出来每次都是当前最佳，权值最小的情况，如果当前队列首部就是终点可以直接输出退出。这里有一个01BFS的题目曾经写过：【双端队列广搜/搜索+图论】AcWing 2019.拖拉机 USACO 2012 March Contest Silver Division - CarryNotKarry。
然后不难，看代码吧，注意有一点不然会WA，就是判断的时候用map来判断是否入只队列一次，而应该是判断是否出队操作一次。因为先入队列的可能是放在后面的，不是最佳，后面进入的反而是最佳的，但是我取出来的时候是只取队列前面最佳，那么先进入放队列后面的则出栈就不操作了。
在Dijkstra中也是如此，我们用的标志数组不是判断它是否进队列一次，而是只对每个点松弛一次。
代码：
int c[N][5];
struct node
{
int x,y,sep;
};
map<PII,bool> mp;
inline void Case_Test()
{
cin>>n;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=4;j++)
cin>>c[i][j];
}
int sx,sy,tx,ty;
cin>>sx>>sy>>tx>>ty;
deque<node> q;
q.push_back({sx,sy,0});
//mp[make_pair(sx,sy)] = true;
while (!q.empty())
{
node t = q.front(); q.pop_front();
int to = t.y, fr = t.x, sep = t.sep;
if (mp[make_pair(fr,to)]) continue;
mp[make_pair(fr,to)] = true;//这样判断每个状态只进行一次操作是正确的
if (fr==tx&&to==ty) {cout<<sep;return;}
for (int i=1;i<=4;i++)
{
if (c[to][i]==0) continue;
//if (mp[make_pair(to,c[to][i])]) continue;
//mp[make_pair(to,c[to][i])] = true; 这样判断是否入队列一次就是会错
if (c[to][(i+2)%4+1]==fr)
q.push_front({to,c[to][i],sep});
else
q.push_back({to,c[to][i],sep+1});
}
}
cout<<-1;
}
H.Hacker（SAM+线段树）
题意：给你$n,m,k$表示有一个长度为$n$的原串$s$，以及有$k$个长度为$m$的字符串$b$进行询问，你将有一个长度为$m$的权值$v_i$，对于每次询问原串$s$与询问串$b$的匹配的若干个公共子串的最大子段和是多少。
例如s=carry和b=pparrpp进行判断，发现b中间的arr是第三个到第五个与s有公共子串，所以就比较$v_3+v_4+v_5$与答案进行更新，当然，b的ar也是符合条件的，所以也需要拿$v_3+v_4$进行比较。
思路：现学后缀自动机(SAM)，这里的SAM能做到以第i个位置为后缀，前面有多少个字符串能与原串匹配。例如s=carrynotkarry，b=carrypk则是以下情况：
i=0 -> 1
i=1 -> 2
i=2 -> 3
i=3 -> 4
i=4 -> 5
i=5 -> 0
i=6 -> 1
然后我用线段树维护区间最大子段和，这个有点难，不过我之前在AcWing写过该题，直接CV过来：AcWing245 线段树-单点修改+区间求最大连续子段和 - CarryNotKarry。
那我需要对于每次都进行查询吗？不，只需要对每次最长的公共子串匹配即可，也就是对于上方的5和最后的1的时候，因为如果是[2,4]是最大子段和的话，我查询[1,5]的时候也能查询出来，而不是每次匹配就进行logn的线段树查询。
代码：
- SAM部分
struct Suffix_Automata
{
int len[N << 1];
int lnk[N << 1];
int cnt[N << 1];
int sub[N << 1];
int nxt[N << 1][26];
int idx;
int last;
void init()
{
last = idx = 1;
lnk[1] = len[1] = 0;
}
void clear()
{
memset(len, 0, sizeof len);
memset(lnk, 0, sizeof lnk);
memset(cnt, 0, sizeof cnt);
memset(nxt, 0, sizeof nxt);
}
void extend(int c)
{
int x = ++idx;
len[x] = len[last] + 1;
sub[x] = 1;
int p;
for (p = last; p && !nxt[p][c]; p = lnk[p])
nxt[p][c] = x;
if (!p)
lnk[x] = 1, cnt[1]++;
else
{
int q = nxt[p][c];
if (len[p] + 1 == len[q])
lnk[x] = q, cnt[q]++;
else
{
int nq = ++idx;
len[nq] = len[p] + 1;
lnk[nq] = lnk[q];
memcpy(nxt[nq], nxt[q], sizeof nxt[q]);
for (; p && nxt[p][c] == q; p = lnk[p])
nxt[p][c] = nq;
lnk[q] = lnk[x] = nq;
cnt[nq] += 2;
}
}
last = x;
}
}sam;
void solve()
{
int len2 = strlen(b);
int u = 1, L = 0, pre;
for (int i = 0; i < len2; i++)
{
int id = b[i] - 'a';
while (!sam.nxt[u][id] && u != 1)
u = sam.lnk[u], L = sam.len[u];
if (sam.nxt[u][id] != 0)
u = sam.nxt[u][id], ++L;
pre = L;
if (L!=pre+1)
ans = Max(ans, query(1,i-L+1+1,i+1).tmax);
}
if (L) ans = Max(ans, query(1,len2-1-L+1+1,len2).tmax);
cout << ans << endl;
}
- 线段树部分
#define lson (o<<1)
#define rson (o<<1|1)
#define mid ((tr[o].l+tr[o].r)>>1)
struct node
{
int l,r,tmax,lmax,rmax,sum;
}tr[N<<2];
inline void pushup(node &o,node &lc,node &rc)
{
o.sum = lc.sum + rc.sum;
o.lmax = Max(lc.lmax,lc.sum+rc.lmax);
o.rmax = Max(rc.rmax,rc.sum+lc.rmax);
o.tmax = Max( Max(lc.tmax,rc.tmax) , lc.rmax+rc.lmax );
}
inline void pushup(int o)
{
pushup(tr[o],tr[lson],tr[rson]);
}
inline void build(int o,int l,int r)
{
tr[o].l = l; tr[o].r = r;
if (l==r)
{
tr[o].tmax = tr[o].lmax = tr[o].rmax = tr[o].sum = val[l];
return;
}
build(lson,l,mid);build(rson,mid+1,r);
pushup(o);
}
inline node query(int o,int l,int r)
{
if (l<=tr[o].l && tr[o].r<=r) return tr[o];
node left={0,0,-inf,-inf,-inf,-inf},right={0,0,-inf,-inf,-inf,-inf},res;
if (l<=mid) left = query(lson,l,r);
if (r>mid) right = query(rson,l,r);
pushup(res,left,right);
return res;
}
#undef lson
#undef rson
#undef mid
- 主函数
inline void Case_Test()
{
cin>>n>>m>>k;
cin>>a;
sam.init();
for (int i=0;i<n;i++)
sam.extend(a[i]-'a');
for (int i=1;i<=m;i++)
cin>>val[i];
build(1,1,m);
while (k--)
{
cin>>b;
ans = 0;
solve();
}
}