一个月前的事情捏，因为今天刚好在摸鱼就想起来写写。
Day 1
开题，先总的过一遍，好像比较传统。
T1 基本上是一眼题了，简单容斥一下就可以解决。很快开始写，写好过了小样例。但是这个时候还没有大样例。而我对这份代码并不太自信，感觉一车细节，所以开拍。
果然 WA 了。然后开始艰难地调试，毕竟代码确实是有点长。调了不知道多久终于过拍了，一看时间已经过去将近两小时了。感觉不太妙。
开 T2，感觉有点神秘，估计要放弃正解。先写个暴力过 1,2，再手推了 3~7 测试点，感觉不能做了。想着能过 \(k=0\) 就行，但是不会。先过。
T3 稍微分析一下看出一个性质，然后发现前 9 个点都是暴力，先写过去。再看看特殊性质，链不难，转化一下成为线段树优化 DP。写写写，拿小样例测了一下是过了，不知道写对没有。
再回去看看 T2，对 \(n=1\) 打表发现是双阶乘，这么神奇。
剩下的时间什么都不会。估分 100+50+52=202，但是没地方测。
Day 2
开题，居然有字符串。
T1 看 \(n\) 很小感觉是乱搞题。先写了一个暴力，然后开始想一些奇妙的东西，比如 \(n\) 次 dijk 之类的。然后突然发现这个 dijk 的结果可以继承，那好像就成了？复杂度上界是 \(O(2^nn^3)\)，但应该多算了不少，能过的样子。写之，测一下极限数据，还比较稳，写个拍丢了。大概一个多小时的样子。
T2 字符串题，只好往我会的方向想。试试能不能用 SA，然后发现真的可以，用 SA 之后配一个 Manacher，加三次二维数点就解决了。但是 SA 我也不太会写啊，怎么办呢，硬写。凭着模糊的记忆，光写 SA 可能就写了四五十分钟，但还是写过去了。接下来就没什么好说的了，正常写数点，很快调过去了。
大概三个半小时了，看 T3，题目都没理解，但看数据范围肯定有 10 分暴力，说不定还能多搞点。但是不想写了。
这时又发现洛谷上有题和大样例了，把两天的代码都测一下，居然一点没挂。这样总分 100+50+52+100+100+(>=10)=(>=412)，算上笔试过了队线。
这场 VP 有点码力爆发的意思，总代码量接近 15K（其中 Day 1 接近 10K），感觉状态还不错。
但过了有什么用呢，又去不了。NOIP 挂成什么都不知道，去了 NOI 估计也是挂分。以前还是练的太少太少了。只能说赶紧练，希望 24 年能够去见见世面。
下面是题解部分。
D1T1
给定方格平面上若干条线段，有水平线，竖直线和斜率为 \(1\) 的线，其中斜线不超过 \(5\) 条。求这些线经过的格子数目。
题解：答案可以表示成 水平线和竖直线的并 加上 斜线的并 减去 斜线与水平线，竖直线的交点数目。第一个值离散化后扫描线求，第二个值直接暴力，第三个值用 set 记一下就行。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int test,n,m,q,x[N<<2],y[N<<2],X,Y,cnt1,cnt2,cnt3;ll ans,cnt;
struct node{int x1,y1,x2,y2;};
bool operator <(const node&a,const node&b){return a.x1<b.x1;}
bool cmp(node a,node b){return a.x1-a.y1==b.x1-b.y1?a.x1<b.x1:a.x1-a.y1<b.x1-b.y1;}
vector<node> q1,q2,q3,q4,Q;
set<pair<int,int> > S;
ll sum[N<<4],tag[N<<4];
void modify(int p,int l,int r,int L,int R,int v){
if(l>=L&&r<=R){
if(v==1){++tag[p];sum[p]=y[r+1]-y[l];}
else{--tag[p];if(!tag[p])sum[p]=(l==r?0:sum[p<<1]+sum[p<<1|1]);}
return;
}
int mid=l+r>>1;
if(L<=mid)modify(p<<1,l,mid,L,R,v);
if(R>mid)modify(p<<1|1,mid+1,r,L,R,v);
if(!tag[p])sum[p]=sum[p<<1]+sum[p<<1|1];
}
int main(){
// freopen("color.in","r",stdin);
// freopen("color.out","w",stdout);
scanf("%d",&test);
scanf("%d%d%d",&n,&m,&q);
for(int i=1,op;i<=q;i++){
node tmp;
scanf("%d%d%d%d%d",&op,&tmp.x1,&tmp.y1,&tmp.x2,&tmp.y2);
if(op!=3)ans+=max(abs(tmp.x1-tmp.x2)+1,abs(tmp.y1-tmp.y2)+1);
x[4*i-3]=tmp.x1;x[4*i-2]=tmp.x2;x[4*i-1]=tmp.x1+1;x[4*i]=tmp.x2+1;
y[4*i-3]=tmp.y1;y[4*i-2]=tmp.y2;y[4*i-1]=tmp.y1+1;y[4*i]=tmp.y2+1;
if(op==1){if(tmp.x1>tmp.x2)swap(tmp.x1,tmp.x2);q1.push_back(tmp);}
if(op==2){if(tmp.y1>tmp.y2)swap(tmp.y1,tmp.y2);q2.push_back(tmp);}
if(op==3)q4.push_back(tmp);
}cnt=ans;
sort(x+1,x+4*q+1);sort(y+1,y+4*q+1);
X=unique(x+1,x+4*q+1)-x-1;Y=unique(y+1,y+4*q+1)-y-1;
sort(q4.begin(),q4.end(),cmp);
node xx;
for(int i=0;i<q4.size();i++){
if(i==0)xx=q4[i];
if(i!=0&&q4[i].x1-q4[i].y1!=q4[i-1].x1-q4[i-1].y1)
q3.push_back(xx),xx=q4[i];
if(i!=0&&q4[i].x1-q4[i].y1==q4[i-1].x1-q4[i-1].y1){
if(xx.x2<q4[i].x1)q3.push_back(xx),xx=q4[i];
else xx.x2=max(q4[i].x2,xx.x2),xx.y2=max(q4[i].y2,xx.y2);
}
if(i==q4.size()-1)q3.push_back(xx);
}
for(node a:q3)ans+=a.x2-a.x1+1;
for(node a:q3)for(node b:q1)
if(a.y1<=b.y1&&a.y2>=b.y2&&
b.y1-a.y1+a.x1>=b.x1&&b.y1-a.y1+a.x1<=b.x2)
S.insert({b.y1-a.y1+a.x1,b.y1});
for(node a:q3)for(node b:q2)
if(a.x1<=b.x1&&a.x2>=b.x2&&
b.x1-a.x1+a.y1>=b.y1&&b.x1-a.x1+a.y1<=b.y2)
S.insert({b.x1,b.x1-a.x1+a.y1});
for(node a:q1){
a.x1=lower_bound(x+1,x+X+1,a.x1)-x;
a.x2=lower_bound(x+1,x+X+1,a.x2+1)-x;
a.y1=lower_bound(y+1,y+Y+1,a.y1)-y;
a.y2=lower_bound(y+1,y+Y+1,a.y2)-y;
Q.push_back({a.x1,a.y1,1,a.y2});
Q.push_back({a.x2,a.y1,-1,a.y2});
}
for(node a:q2){
a.x1=lower_bound(x+1,x+X+1,a.x1)-x;
a.x2=lower_bound(x+1,x+X+1,a.x2+1)-x;
a.y1=lower_bound(y+1,y+Y+1,a.y1)-y;
a.y2=lower_bound(y+1,y+Y+1,a.y2)-y;
Q.push_back({a.x1,a.y1,1,a.y2});
Q.push_back({a.x2,a.y1,-1,a.y2});
}
sort(Q.begin(),Q.end());
for(int i=1,p=0;i<=X;i++){
while(p<Q.size()&&Q[p].x1==i)
modify(1,1,Y,Q[p].y1,Q[p].y2,Q[p].x2),++p;
cnt-=sum[1]*(x[i+1]-x[i]);
}
printf("%lld\n",ans-cnt-S.size());
return 0;
}
D2T1
在一棵 \(n\) 层的满二叉树上加入若干条祖先指向后代的边，边有边权。树边由儿子指向父亲。对所有满足 \(u\) 能到达 \(v\) 的有序点对 \((u,v)\)，求 \(u\) 到 \(v\) 的最短路径长度和。
题解：注意到一个事实：如果 \(u\) 能到达不在 \(u\) 子树内的点 \(v\)，那 \(u\) 到 \(v\) 的最短路径就等于 \(u\) 沿着树边走到 \(LCA(u,v)\) 的路径长加上 \(LCA(u,v)\) 到 \(v\) 的最短路径长。所以只要求出每个点到它子树内点的最短路径，再乘一些容易求的系数即可。
要求 \(u\) 到它所有后代的距离，可以从它的两个儿子继承而来。也就是说，儿子到其子树内点的最短距离加上连接它们的边的长度，可以作为初始值加入优先队列。然后跑 Dijkstra。
时间有点久了，真的忘了。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5,P=998244353;
int n,m,a[N],rt,vis[N],dep[N];
ll dis[N],sum0,sum1,sum2,sum3,ans;
int head[N],nxt[N<<1],ver[N<<1],val[N<<1],tot;
void add(int u,int v,int w){
ver[++tot]=v;val[tot]=w;
nxt[tot]=head[u];head[u]=tot;
}
map<pair<int,int>,int> M;
priority_queue<pair<ll,int> > Q;
void init(int u){
dis[u]+=a[rt];vis[u]=0;
if(dis[u]<1e17)Q.push({-dis[u],u});
if(u*2<(1<<n))init(2*u),init(2*u+1);
}
void dfs(int u){
++sum0;sum2=(sum2+(dep[u]-dep[rt]+P)%P)%P;
if(dis[u]<1e17)sum1=(sum1+dis[u]%P)%P,++sum3;
if(u*2<(1<<n))dfs(2*u),dfs(2*u+1);
}
void solve(int s){
rt=s;init(s);dis[s]=0;Q.push({0,s});
while(!Q.empty()){
int u=Q.top().second;Q.pop();
if(vis[u])continue;vis[u]=1;
for(int i=head[u],v;i;i=nxt[i])
if(dis[v=ver[i]]>dis[u]+val[i]&&v>rt){
dis[v]=dis[u]+val[i];
Q.push({-dis[v],v});
}
}
sum0=sum3=1;sum2=sum1=0;dfs(2*s);
ll sum4=sum0,sum5=sum1,sum6=sum2,sum7=sum3;
sum0=sum3=1;sum2=sum1=0;dfs(2*s+1);
ans=(ans+sum4*sum1%P+sum2*sum7%P
+sum0*sum5%P+sum6*sum3%P)%P;
if(s*2<(1<<n-1))solve(2*s),solve(2*s+1);
}
int main(){
// freopen("trade.in","r",stdin);
// freopen("trade.out","w",stdout);
memset(dis,0x3f,sizeof(dis));
scanf("%d%d",&n,&m);
for(int i=2;i<(1<<n);i++){
scanf("%d",a+i);
add(i,i/2,a[i]);dep[i]=(dep[i/2]+a[i])%P;
}
for(int i=1,u,v,w;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
if(M.find({u,v})==M.end())M[{u,v}]=w;
else M[{u,v}]=min(M[{u,v}],w);
}
for(auto x:M)add(x.first.first,x.first.second,x.second);
solve(1);
printf("%lld\n",ans);
return 0;
}
D2T2
给定字符串 \(s[1,n]\)，\(q\) 次询问，每次给定 \(i,r\)，求满足 \(1\le l \le r\)，且 \(s[i,i+l-1]\) 的字典序小于 \(s[i+l,i+2l-1]\) 的翻转的字典序。
题解：如何用 SA 刻画这个条件？不妨扩展一下，如果满足条件，则 \(s[i,n]\) 的字典序也小于 \(s[1,i+2l-1]\) 的翻转的字典序。那么就可以把原字符串翻转一遍接在后面，然后跑 SA，只要对应的字符串在后缀数组中排在前面就行。
但是有一点问题，就是可能 \(s[i,i+l-1]\) 等于 \(s[i+l,i+2l-1]\) 的翻转，但仍然排在前面。这时会发现构成了一个回文串，所以跑 Manacher。
列一下式子。\(rk[i]\) 表示后缀 \(s[i,n]+s[n,1]\) 的排名，\(rk[2n+1-i]\) 表示后缀 \(s[i,1]\) 的排名。\(a[i]\) 表示以 \(i\) 和 \(i+1\) 的中心为缝隙的回文串的最大长度。则 \(l\) 满足条件，当且仅当 \(rk[i]\lt rk[2n+2-2l-i]\) 且 \(a[i+l-1]\lt l\)。
对第二个条件考虑反面。容易转成二维数点，剩下的推导是容易的。对第一个式子，我选择分奇偶各进行一次。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int test,T,n,q,a[N],ans[N];char s[N],t[N];
int c[N],x[N],y[N],sa[N],rk[N];
void SA(){
int m=300;n*=2;
for(int i=1;i<=n;i++)x[i]=t[i],c[x[i]]++;
for(int i=1;i<=m;i++)c[i]+=c[i-1];
for(int i=n;i>=1;i--)sa[c[x[i]]--]=i;
for(int k=1;k<=n;k*=2){
int num=0;
for(int i=n-k+1;i<=n;i++)y[++num]=i;
for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
for(int i=1;i<=m;i++)c[i]=0;
for(int i=1;i<=n;i++)c[x[i]]++;
for(int i=1;i<=m;i++)c[i]+=c[i-1];
for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y);x[sa[1]]=num=1;
for(int i=2;i<=n;i++){
if(sa[i]<=n-k&&sa[i-1]<=n-k&&
y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])
x[sa[i]]=num;
else x[sa[i]]=++num;
}
if(num==n)break;m=num;
}
for(int i=1;i<=n;i++)rk[sa[i]]=i;
n/=2;
}
//sa[i]表示排名为i的后缀是s[sa[i]:n]
void Manacher(){
int l=0,r=0;
for(int i=1;i<n;i++){
if(i>=r){
int j=0;
while(i-j>=1&&i+j+1<=n&&s[i-j]==s[i+j+1])++j;
if(j>0){l=i-j+1;r=i+j;}a[i]=j;
}
else{
int p=l+r-i-1;
if(a[p]<r-i)a[i]=a[p];
else{
int j=r-i;
while(i-j>=1&&i+j+1<=n&&s[i-j]==s[i+j+1])++j;
r=i+j;l=i-j+1;a[i]=j;
}
}
}
}
//a[i]表示以i和i+1间的缝隙为中心的最长回文串的长度的一半
struct BIT{
int c[N];
void init(){for(int i=1;i<=2*n;i++)c[i]=0;}
void add(int x,int v){for(;x<=2*n;x+=x&-x)c[x]+=v;}
int ask(int x){int res=0;for(;x;x-=x&-x)res+=c[x];return res;}
}B;
struct query{int l,r,id;}f[N];
int id[N],cnt;
bool cmp1(int i,int j){return i-a[i]<j-a[j];}
bool cst1(query a,query b){return a.l<b.l;}
bool cst2(query a,query b){return rk[a.l]>rk[b.l];}
void init(){
memset(a,0,sizeof(a));
memset(sa,0,sizeof(sa));
memset(ans,0,sizeof(ans));
memset(c,0,sizeof(c));
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
}
int main(){
// freopen("string.in","r",stdin);
// freopen("string.out","w",stdout);
scanf("%d%d",&test,&T);
while(T--){
init();
scanf("%d%d",&n,&q);
scanf("%s",s+1);
for(int i=1;i<=n;i++)t[i]=t[2*n+1-i]=s[i];
Manacher();SA();
for(int i=1;i<=q;i++)
scanf("%d%d",&f[i].l,&f[i].r),f[i].id=i;
B.init();cnt=0;
for(int i=1;i<n;i++)
if(a[i]&&rk[i+1-a[i]]<rk[2*n+1-i-a[i]])id[++cnt]=i;
sort(id+1,id+cnt+1,cmp1);sort(f+1,f+q+1,cst1);
for(int i=1,p=1;i<=q;i++){
while(p<=cnt&&id[p]-a[id[p]]+1<=f[i].l)
{B.add(id[p],1);++p;}
ans[f[i].id]-=B.ask(f[i].l+f[i].r-1)-B.ask(f[i].l-1);
}
B.init();cnt=0;
for(int i=2*n;i>=1;i--)
if(sa[i]&1)id[++cnt]=i;
sort(f+1,f+q+1,cst2);
for(int i=1,p=1;i<=q;i++)if(f[i].l&1){
while(p<=cnt&&id[p]>rk[f[i].l]){B.add(sa[id[p]],1);++p;}
ans[f[i].id]+=B.ask(2*n-f[i].l)-B.ask(2*n+1-2*f[i].r-f[i].l);
}
B.init();cnt=0;
for(int i=2*n;i>=1;i--)
if(!(sa[i]&1))id[++cnt]=i;
for(int i=1,p=1;i<=q;i++)if(!(f[i].l&1)){
while(p<=cnt&&id[p]>rk[f[i].l]){B.add(sa[id[p]],1);++p;}
ans[f[i].id]+=B.ask(2*n-f[i].l)-B.ask(2*n+1-2*f[i].r-f[i].l);
}
for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
}
return 0;
}