题目链接

P3120 [USACO15FEB]Cow Hopscotch G

solve

读完题目我们很容易写出一个 \(O(n^4)\) 的方程

\[F[i][j]=\sum F[i'][j'] \]

这个柿子可以通过三维偏序来优化，但是我往另外一个方向走了

如果颜色数很少的话，就可以用一个数组 \(sum[i][j][k]\) 表示第 \(k\) 个颜色在 \(i,j\) 左上角的方案书之和，\(sum[i][j][0]\)表示总的，所以方程就变成了

\[F[i][j]=sum[i-1][j-1][0]-sum[i-1][j-1][a[i][j]] \]

但是这里的颜色数达到了 \(n\times m\) 的级别，但要改的点数不多，就可以考虑用线段树的动态开点来维护前缀和

我们每行每行处理，先求后改，开 \(k\) (颜色数) 颗线段树，于是方案就变成了

\[sum[j-1]-\text{第a[i][j]的1到{j-1}的前缀和} \]

每次求完回去再同意修改即可

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=755;
const LL TT=1e9+7;
int N,M,cnt;
int a[maxn][maxn];
LL F[maxn][maxn],S[maxn];
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
struct Tree{
	LL sum;
	int ls,rs;
}tr[maxn*maxn*16];
inline void update(int x){
	tr[x].sum=(tr[tr[x].ls].sum+tr[tr[x].rs].sum)%TT;
}
void modify(int &x,int l,int r,int pos,int data){
	if(!x)x=++cnt;
	if(!(l^r)){tr[x].sum=(tr[x].sum+data)%TT;return ;}
	int mid=(r-l>>1)+l;
	(pos<=mid)&&(modify(tr[x].ls,l,mid,pos,data),0);(pos>mid)&&(modify(tr[x].rs,mid+1,r,pos,data),0);
	update(x);
	return ;
}
LL query(int x,int l,int r,int L,int R){
	if(!x)return 0;
	if(L<=l&&r<=R)return tr[x].sum;
	int mid=(r-l>>1)+l;
	LL ret=0;
	(L<=mid)&&(ret=(ret+query(tr[x].ls,l,mid,L,R))%TT,0);(R>mid)&&(ret=(ret+query(tr[x].rs,mid+1,r,L,R))%TT,0);
	return ret;
}
int main(){
	freopen("P3120.in","r",stdin);
	freopen("P3120.out","w",stdout);
	N=read();M=read();cnt=read();
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++)
			a[i][j]=read();
	for(int i=1;i<=M;i++) S[i]=1;F[1][1]=1;modify(a[1][1],1,M,1,1);
	for(int i=2;i<=N;i++){
		for(int j=2;j<=M;j++)F[i][j]=(S[j-1]-query(a[i][j],1,M,1,j-1)+TT)%TT;
		LL res=0;
		for(int j=2;j<=M;j++){
			res=(res+F[i][j]);
			S[j]=(S[j]+res)%TT;
			modify(a[i][j],1,M,j,F[i][j]);
		}
	}
	printf("%lld\n",F[N][M]);
	return 0;
}