题目：
定义一个矩阵的贡献为：其互不相同的行的种类数。
给出一个矩阵，求其所有子矩阵的贡献和。
分析：
可以把每一行拿出来，弄成一个字符串，建一颗Trie树出来。
此时，就可以算出以最左端为左边界的所有子矩阵的贡献。
算完后，把第一层节点合并，相当于去除了第一列的所有数。
此时就可以看做把每一行从第二列开始，建的Trie树。
然后可以算出从第一列到第二列所有矩形贡献的变化量。（变化量只和合并的位置有关，所以计算一次变化量后，就会删去等量的点）
然后就可以算出以第二列为左边界的所有子矩阵的贡献。
……
就可以算出所有贡献了。
整个复杂度
O(nm(logn)(logm))O(nm(logn)(logm))O(nm(logn)(logm))
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#define SF scanf
#define PF printf
#define MAXN 500010
using namespace std;
typedef long long ll;
int n,m;
ll now;
void Read(int &x){
x=0;char c;while(c=getchar(),c!=EOF&&(c<'0'||c>'9'));x=c-'0';while(c=getchar(),c!=EOF&&c>='0'&&c<='9')x=x*10+c-'0';
}
struct node{
ll val;set<int>s;map<int,node*> ch; void ins(int x){
int l=x+1,r=n-x; set<int>::iterator p=s.insert(x).first;if(p!=s.begin())l=x-*prev(p);if(next(p)!=s.end())r=*next(p)-x;val+=1ll*l*r;now+=1ll*l*r;}
}Trie[MAXN];
node *rt=Trie,*ncnt=Trie;
node *merge(node *x,node *y){
if(x==NULL) return y;if(y==NULL) return x;if(x->ch.size() < y->ch.size())swap(x,y);for(map<int,node*>::iterator it=y->ch.begin();it!=y->ch.end();it++)x->ch[it->first]=merge(x->ch[it->first],it->second);if(x->s.size() < y->s.size()){
swap(x->s,y->s);swap(x->val,y->val);}for(set<int>::iterator it=y->s.begin();it!=y->s.end();it++)x->ins(*it);now-=y->val;return x;
}
int main(){
ll ans=0;int x;
// SF("%d%d",&n,&m);Read(n),Read(m);for(int i=0;i<n;i++){
node *pos=rt;for(int j=0;j<m;j++){
Read(x);
// SF("%d",&x);if(!pos->ch.count(x))pos->ch[x]=++ncnt;pos=pos->ch[x];pos->ins(i);}}ans+=now;for(int i=1;i<m;i++){
node* newrt=NULL;for(map<int,node*>::iterator it=rt->ch.begin();it!=rt->ch.end();it++){
if(newrt==NULL)newrt=it->second;elsenewrt=merge(newrt,it->second); }rt=newrt;now-=rt->val;ans+=now;}PF("%lld",ans);
}