- 给定一棵定义在长度为(n)的序列上的广义线段树（即每次分割区间不一定取中点）。
- 有(k)次操作，每次随机选取一个区间进行一次(Modify)（详见原题）。
- 求最终有标记的节点数期望。
- (nle2 imes10^5,kle10^9)
毕竟是半年前考场上切掉的题目啊。。。
由于没有考场代码，这篇博客就一直坑着，直到今天下定决心重写一遍。
应该说实力还是没有太大退步，稍微想了一下便推出来了，接着轻松过样例，然后就一遍(A)掉了。
套路设立状态
真的想不到ZJOI会抄自己的题目，发现前一年的Day1T2（【洛谷5280】[ZJOI2019] 线段树）和今年的Day1T2完全就是一个套路，甚至今年这题可能还要更简单。
按照套路，对于一个点(x)（假设它对应区间为([l,r])，其父节点对应区间为([fl,fr])）我们设立三个状态：
- (f_{x,i,0})表示(i)次操作后(x)及其祖先都没有标记的方案数。
- (f_{x,i,1})表示(i)次操作后(x)没有标记，但(x)的祖先有标记的方案数。
- (f_{x,i,2})表示(i)次操作后(x)有标记的方案数。
方便起见，我们定义(S(x)=frac{x imes(x+1)}2)。
令(T=S(n))（一次操作的总方案数），(P=S(l-1)+S(n-r))（和当前区间无交的方案数），(A=l imes (n-r+1))（包含当前区间的方案数，也即当前点及其祖先中的某一个点作为终止节点的方案数）。
并类似地定义(Pf=S(fl-1)+S(n-fr),Af=fl imes(n-fr+1))。
然后考虑状态之间的转移：
- (U(0 ightarrow0))：那么这次操作要么和当前区间无交，要么走进了当前区间子树（和当前区间有交但是不包含）。总结一下就是(T-A)。
- (U(0 ightarrow 2))：那么这次操作要恰好停在当前点，也就是说要包含当前区间，但不能包含父节点对应的区间。总结一下就是(A-Af)。
- (U(0 ightarrow1))：自然就是除了(U(0 ightarrow0))和(U(0 ightarrow2))外的所有情况，即(T-U(0 ightarrow0)-U(0 ightarrow2)=Af)。
- (U(1 ightarrow0))：只有走进了当前区间子树的情况，和(U(0 ightarrow0))的区别就是少了和当前区间无交的方案数(P)。总结一下就是(T-P-A)。
- (U(1 ightarrow2))：当前点被打上标记既可能是因为父节点标记上传，也可能是因为直接被打上标记。无论如何首先我们必须要走到父节点，要减去与父节点区间无交的方案数(Pf)；其次，父节点及其祖先都不能作为终止节点，要减去包含父节点区间的方案数(Af)；再次，不能走进当前区间子树，要减去这一部分的方案数(U(1 ightarrow0))。总结一下就是(T-Pf-Af-U(1 ightarrow0)=P+A-Pf-Af)。
- (U(1 ightarrow1))：(T-U(1 ightarrow0)-U(1 ightarrow2)=Pf+Af)。
- (U(2 ightarrow0))：同(U(1 ightarrow0))，为(T-P-A)。
- (U(2 ightarrow2))：发现除了走进当前区间子树的情况，已有的标记是不可能消失的。总结一下就是(T-U(2 ightarrow0)=P+A)。
- (U(2 ightarrow1))：显然为(0)。
(k)这么大自然而然想到矩乘优化，于是这道题就做完了。
代码：(O(27nlogk))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 200000
#define X 998244353
using namespace std;
int n,k;I int QP(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
struct M
{
int a[3][3];I M() {memset(a,0,sizeof(a));}
I int* operator [] (CI x) {return a[x];}
I Con int* operator [] (CI x) Con {return a[x];}
I M operator * (Con M& o) Con//矩阵乘法
{
M t;RI i,j,k;for(i=0;i^3;++i) for(j=0;j^3;++j)
for(k=0;k^3;++k) t[i][j]=(1LL*a[i][k]*o[k][j]+t[i][j])%X;return t;
}
}U,t;
int ans;I void Solve(CI l,CI r,CI fl=0,CI fr=n+1)
{
#define S(x) (1LL*(x)*((x)+1)/2%X)
#define G(x,y) (1LL*(x)*(n-(y)+1)%X)
RI T=S(n),P=(S(l-1)+S(n-r))%X,A=G(l,r),Pf=(S(fl-1)+S(n-fr))%X,Af=G(fl,fr);
U[0][0]=(T-A+X)%X,U[0][2]=(A-Af+X)%X,U[0][1]=Af,//构造转移矩阵
U[1][0]=(T-P-A+X)%X,U[1][2]=((0LL+P+A-Pf-Af)%X+X)%X,U[1][1]=(Pf+Af)%X,
U[2][0]=(T-P-A+X)%X,U[2][2]=(P+A)%X,U[2][1]=0;
RI y=k;(t=M())[0][0]=1;W(y) y&1&&(t=t*U,0),U=U*U,y>>=1;ans=(ans+t[0][2])%X;//矩阵快速幂，ans统计答案
if(l==r) return;RI x;scanf("%d",&x),Solve(l,x,l,r),Solve(x+1,r,l,r);//递归
}
int main()
{
return scanf("%d%d",&n,&k),Solve(1,n),printf("%d
",1LL*ans*QP(QP(S(n),k),X-2)%X),0;//期望=总和/总方案数
}