sequence

matrix

n∗m≤5e5,1≤ai,j≤1e9n*m≤5e5,1≤a_{i,j}≤1e9n∗m≤5e5,1≤ai,j​≤1e9

一道很妙的题。

首先大家应该都会无脑的O(nm2)dpO(nm^2)dpO(nm2)dp，即我们固定左右端点和之间的字符串$S$，从上往下扫计算每一行的贡献，对于第$i$行的串SiS_iSi​，我们设上一个出现的满足Sj=SiS_j=S_iSj​=Si​的位置为$j$，那么SiS_iSi​对答案的贡献就是$(i-j)\ast (n-i+1)$

于是对于每一种串我们可以维护其出现位置的集合setS={a0,a1,a2,..,at}set_S=\{a_0,a_1,a_2,..,a_t\}setS​={

a0​,a1​,a2​,..,at​}，其中a0=0a_0=0a0​=0是方便计算的，那么这个串的贡献就是∑i=1t(ai−ai−1)(n−ai+1)\sum_{i=1}^t(a_i-a_i-1)(n-a_i+1)∑i=1t​(ai​−ai​−1)(n−ai​+1)

现在的问题变成了如何快速维护这个东西。

考虑先将$l$强制为$1$，然后按行建立$trie$树，对于每个节点维护上面谈到的位置集合，然后可以统计出$l=1$时候的答案。

然后当$l\to l+1$的时候，我们把当前根节点的所有儿子删掉，把所有儿子的儿子启发式合并起来即可。

代码：

#include
    
     #define ri register int#define fi first#define se secondusing namespace std;const int rlen=1<<18|1;inline char gc(){
    	static char buf[rlen],*ib,*ob;	(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));	return ib==ob?-1:*ib++;}inline int read(){
    	int ans=0;	char ch=gc();	while(!isdigit(ch))ch=gc();	while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();	return ans;}typedef long long ll;const int N=5e5+5;int n,m,a[N],rt=1,tot=1;map
     
      son[N];set
      
       pos[N];typedef map
       
        ::iterator It;ll ans=0,sum=0,val[N];inline void build(int id,int l,int r){
    	for(ri p=rt,v,i=l;i<=r;++i){
    		if(!son[p][a[i]])son[p][a[i]]=++tot,pos[son[p][a[i]]].insert(0),pos[son[p][a[i]]].insert(n+1);		pos[v=son[p][a[i]]].insert(id);		set
        
         ::iterator it=pos[v].lower_bound(id);		--it,val[v]+=(ll)(id-*it)*(n-id+1);		p=v;	}}inline int merge(int x,int y){
    	if(!x||!y)return x+y;	if(pos[x].size()