当前位置: 代码迷 >> 综合 >> 【Trie树】【启发式合并】2019雅礼集训 matrix
  详细解决方案

【Trie树】【启发式合并】2019雅礼集训 matrix

热度:61   发布时间:2023-09-27 04:16:09.0

题目:

定义一个矩阵的贡献为:其互不相同的行的种类数。
给出一个矩阵,求其所有子矩阵的贡献和。


分析:

可以把每一行拿出来,弄成一个字符串,建一颗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);
}