模拟赛
T1
首先是曼哈顿距离到切比雪夫距离的转化，到原点曼哈顿距离为定值 $a$ 的点组成的图形为一个斜正方形，且原点到顶点的距离为 $a$，正方形边长为 $\sqrt{2} a$ ，而到原点切比雪夫距离为 $a$ 的点组成的图形为正正方形，且边长为 $2a$，那么我们可以通过把平面坐标系旋转 $45$ 度，并把边长乘上 $\sqrt 2$ 即可。反映在坐标上，即做坐标变换 $(x,y)\rightarrow (x-y,x+y)$，然后利用切比雪夫距离的横纵坐标差去最值来优化我们找的过程。
根据以上分析，所以对于每个点来说，分别在左上左下右上右下 $4$ 个方向曼哈顿距离最大的点在一条直线上。
介绍一下 Borvka 算法，大致思路是找到每个点距离其最远的点，然后连边，这样做联通块个数减少一半，至多要做 $\log n$ 轮，所以复杂度是 $(n+m)\log n$，其中 $n$ 为点数 $m$ 为边数。而对于这个题，做完一遍这个算法后，至多为有 $4$ 个连通块剩余，所以我们对这 $4$ 个集合枚举最大边连接即可，由于这些连边至少会有一个顶点为我们选定的 $4$ 条直线上的点，所以我们直接枚举的复杂度是 $O(n)$ 的。
注意，直线上选哪个点都行。
赛时写了个巨麻烦的树状数组 $n\log n$ 扫描线做法。
代码：
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define inc(a,b) (((a)+(b))>=mod?(a)+(b)-mod:(a)+(b))
#define sub(a,b) (((a)-(b))<0?(a)-(b)+mod:(a)-(b))
#define mul(a,b) 1ll*(a)*(b)%mod
#define sgn(a) (((a)&1)?(mod-1):1)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 2000100
#define M number
using namespace std;
typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
//#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;
const int INF=0x3f3f3f3f;
const dd eps=1e-9;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int n;
struct Point{
int x,y;
}a[N];
int p[5],ma[5];
ll Ans;
vi v[5];
struct Line{
int u,v,w;
inline void Init(int u_,int v_,int w_){
u=u_;v=v_;w=w_;
// printf("u=%d v=%d w=%d\n",u,v,w);
}
inline bool operator < (const Line &b)const{
return w>b.w;
}
}li[30];
int lt,fa[5];
inline int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}
int main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);rep(i,1,n) read(a[i].x),read(a[i].y);
mset(p,-1);ma[1]=-INF;ma[2]=INF;ma[3]=INF;ma[4]=-INF;
rep(i,1,n){
if(ma[1]<a[i].x+a[i].y) ma[1]=a[i].x+a[i].y,p[1]=i;
if(ma[2]>a[i].x-a[i].y) ma[2]=a[i].x-a[i].y,p[2]=i;
if(ma[3]>a[i].x+a[i].y) ma[3]=a[i].x+a[i].y,p[3]=i;
if(ma[4]<a[i].x-a[i].y) ma[4]=a[i].x-a[i].y,p[4]=i;
}
// rep(i,1,4) printf("p[%d]=%d\n",i,p[i]);
rep(i,1,n){
bool op=1;rep(j,1,4) if(p[j]==i) op=0;if(!op) continue;
int maxx=-INF,id=-1;
rep(j,1,4) if(maxx<abs(a[i].x-a[p[j]].x)+abs(a[i].y-a[p[j]].y)){
maxx=abs(a[i].x-a[p[j]].x)+abs(a[i].y-a[p[j]].y),id=j;
// printf("j=%d maxx=%d\n",j,maxx);
}
v[id].pb(i);Ans+=maxx;
// printf("maxx=%d\n",maxx);
}
rep(i,1,4) v[i].pb(p[i]);
// printf("Ans=%d\n",Ans);
rep(i,1,4)rep(j,i+1,4){
int maxx=-INF;
for(int now:v[j]) if(maxx<abs(a[now].x-a[p[i]].x)+abs(a[now].y-a[p[i]].y)) maxx=abs(a[now].x-a[p[i]].x)+abs(a[now].y-a[p[i]].y);
for(int now:v[i]) if(maxx<abs(a[now].x-a[p[j]].x)+abs(a[now].y-a[p[j]].y)) maxx=abs(a[now].x-a[p[j]].x)+abs(a[now].y-a[p[j]].y);
li[++lt].Init(i,j,maxx);
}
sort(li+1,li+lt+1);rep(i,1,4) fa[i]=i;
rep(i,1,lt){
int fau=Find(li[i].u),fav=Find(li[i].v);
if(fau==fav) continue;
Ans+=li[i].w;fa[fau]=fav;
}
printf("%lld\n",Ans);
return 0;
}
T2
首先考虑如果从 $i,j$ 建一条 $0$ 边，表示 $i<j$，建一条 $1$ 边表示 $i\le j$，我们可以得到一张 DAG，在 DAG 上 DP 显然不是很好做的，因为限制不够紧，考虑这张图是否可以缩进限制，使其变成一棵树？
有一个关键性质：区间之间只可能包含不可能相交，根据这个我们可以简单证明原 DAG 一定可以缩成一棵树。在树上 DP 用前缀和优化到 $O(nm)$ 即可。
struct edge{
int to,next,op;
inline void Init(int to_,int ne_,int op_){
to=to_;next=ne_;op=op_;
}
}li[N<<1];
int head[N],tail,n,m,b[N],d[N],id[N],tot,f[N][M],g[N][M];
vc<P> e[N];
queue<int> q;
vi v;
inline void Add(int from,int to,int op){
// printf("from=%d to=%d op=%d\n",from,to,op);
li[++tail].Init(to,head[from],op);head[from]=tail;
}
inline void dfs(int k,int fa){
Next(k){
int to=li[x].to;if(to==fa) continue;dfs(to,k);
}
rep(i,1,m){
f[k][i]=1;
Next(k){
int to=li[x].to,op=li[x].op;if(to==fa) continue;
if(op==0) f[k][i]=1ll*f[k][i]*g[to][i-1]%mod;
else f[k][i]=1ll*f[k][i]*g[to][i]%mod;
}
g[k][i]=(g[k][i-1]+f[k][i])%mod;
// printf("f[%d][%d]=%d\n",k,i,f[k][i]);
// printf("g[%d][%d]=%d\n",k,i,g[k][i]);
}
}
int main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);read(m);rep(i,1,n) read(b[i]);
rep(i,1,n){
if(b[i]==-1) continue;rep(j,b[i]+1,i-1) e[j].pb(mp(i,1)),d[i]++;
if(b[i]) e[i].pb(mp(b[i],0)),d[b[i]]++;
}
rep(i,1,n) if(!d[i]) q.push(i);
while(q.size()){
int top=q.front();q.pop();id[top]=++tot;
for(P now:e[top]){
d[now.fi]--;if(!d[now.fi]) q.push(now.fi);
}
}
assert(tot==n);id[0]=INF;
rep(i,1,n){
P maxx(0,0);
for(P now:e[i]) if(id[now.fi]<id[maxx.fi]) maxx=now;
if(maxx.fi==0) continue;Add(maxx.fi,i,maxx.se);d[i]++;
}
rep(i,1,n) if(!d[i]) v.pb(i);
int Ans=1;
for(int rt:v) dfs(rt,0);
for(int rt:v) Ans=1ll*Ans*g[rt][m]%mod;
printf("%d\n",Ans);
return 0;
}
T3
首先考虑后缀自动机，因为后缀自动机存储了所有子串的信息，那么对于一个状态，里面除了最长的那个字符串，其余字符串一定是不重要的，而如果一个状态有至少两个转移，那么这个状态里最长的那个串一定是重要的，因为在这个串前面加字符得到的字符串在别的状态里，$endpos$ 集合不一样，而往后加一个字符有不同加法，所以一定也不一样。
如果一个状态没有转移，即 $last$ 这个状态，里面最长的串一定也是重要的，而对于只有一个转移的状态，如果它是后缀，那么也是重要的，因为它往后加字符之后得到的串的 $endpos$ 一定不和原来一样。如果一个状态里面最长的字符串是重要的，那么我们称这个状态也是重要的，我们需要统计所有重要的状态，和在 $fail$ 树上，从根到 $last$ 这个路径上所有不重要的状态的个数之和。前一个好统计，后一个不好统计。因为树的形态会变化，所以一种思路是我们用 LCT 去维护 fail 树，操作就是在一个边上加上一个点，以及给一个点加一个叶子。
不过 LCT 常数太大了，只能做 $10^5$，切队长直接魔改了 LCT 过掉了这个题，我们考虑倒过来做，从后向前做，这样我们就可以近似认为树的状态没有变化，而我们需要维护每个点是否重要，以及一个点到根不重要点的数量，操作相当于树上单点改，链求和，树状数组树上差分做就可以。注意操作数是 $O(n)$ 的，因为改变次数和转移数和节点数是同一级别的。
代码：
int n,ans[N];
char s[N];
vi e[N];int L[N],R[N],itot;
struct BIT{
int p[N];
inline int lowbit(int x){return x&(-x);}
inline void Add(int w,int x){
// printf("Add w=%d x=%d\n",w,x);
for(int i=w;i<=itot;i+=lowbit(i)) p[i]+=x;
}
inline int Ask(int w){
// printf("Ask w=%d\n",w);
int res=0;for(int i=w;i;i-=lowbit(i)) res+=p[i];return res;
}
}bit;
struct Ques{
int op,k,x;
inline Ques(){}
inline Ques(int op,int k,int x) : op(op),k(k),x(x) {}
};
vc<Ques> qu[N];
struct SAM{
int Link[N<<1],tot,Len[N<<1],ch[N<<1][10],cnt[N<<1],last,Ans;
inline SAM(){tot=1;Link[1]=-1;Len[1]=0;last=1;Ans=0;}
inline void Insert(int c,int id){
// printf("first Ans=%d\n",Ans);
vc<P> v;v.clear();
int now=++tot;Len[now]=Len[last]+1;int p=last;
while(p!=-1&&!ch[p][c]){
ch[p][c]=now;cnt[p]++;
if(cnt[p]==1&&p!=1) Ans--,v.pb(mp(p,-1));
else if(cnt[p]==2&&p!=1) Ans++,v.pb(mp(p,1));
p=Link[p];
}
// printf("Ans=%d\n",Ans);
if(p==-1){Link[now]=1;}
else{
int q=ch[p][c];if(Len[q]==Len[p]+1){Link[now]=q;}
else{
int clone=++tot;Link[clone]=Link[q];rep(i,0,9) ch[clone][i]=ch[q][i];cnt[clone]=cnt[q];
if(cnt[clone]>=2) Ans++;else if(cnt[clone]==1) v.pb(mp(clone,-1));Len[clone]=Len[p]+1;
Link[q]=clone;Link[now]=clone;while(p!=-1&&ch[p][c]==q) ch[p][c]=clone,p=Link[p];
}
}
last=now;Ans++;v.pb(mp(now,-1));qu[id].pb(Ques(1,now,-1));
dec(i,0,(int)v.size()-1) qu[id].pb(Ques(2,v[i].fi,v[i].se));
}
inline void dfs(int k,int fa){
L[k]=++itot;if(cnt[k]==1) qu[n+1].pb(Ques(2,k,1));
for(int to:e[k])if(to!=fa){dfs(to,k);}
R[k]=itot;
}
inline void Build(){
rep(i,1,tot) if(Link[i]!=-1){
e[Link[i]].pb(i);
// printf("Add %d %d\n",Link[i],i);
}dfs(1,0);
}
}sam;
inline void Solve(){
// rep(i,1,n) printf("%d ",ans[i]);puts("");
dec(i,1,n+1){
for(Ques now:qu[i]) if(now.op==1) ans[i]+=bit.Ask(L[now.k]);
else{
if(now.k==1) continue;
// printf("Ope Add %d %d\n",now.k,now.x);
bit.Add(L[now.k],now.x);bit.Add(R[now.k]+1,now.x*(-1));
}
}
}
int main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);scanf("%s",s+1);
rep(i,1,n) sam.Insert(s[i]-'0',i),ans[i]=sam.Ans;sam.Build();
Solve();rep(i,1,n) printf("%d ",ans[i]);
return 0;
}