Codechef Graph on a Table

Graph on a Table

给定(N)行(M)列的棋盘。记第(r)行第(c)列的格子为((r, c))。给定(Q)个询问的矩形。

考虑一个有向无环图，图中每个节点对应棋盘上的一个格子（故共有(N imes M)个节点）。从格子((r_1, c_1))的节点到格子((r_2, c_2))的节点有边，当且仅当：

  • (r_1 < r_2, c_1 < c_2)；

  • 存在一个询问矩形同时包含((r_1, c_1))和((r_2, c_2))。

定义路径长度为路径包含的节点个数。求出图中的最长路径，以及长度最长的路径共有多少条。我们认为两条路径不同，当且仅当一条路径中存在一个不在另一条路径中出现的节点。由于满足条件的路径可能有很多，输出方案数对(10^9 + 7)取模得到的结果。

(1 leq N, M leq 2000)，(1 leq Q leq 5 imes 10^5)，(sum Ncdot Mleq 10^7)，(sum Qleq 5 imes 10^5)。

35分做法

先建出平面直角坐标系，然后按照(x)从大到小、(y)从大到小DP。

对于每一个点((x,y))，我们找出能覆盖它且满足(r_2>x)的矩形的上边界的最大值(max c)。那么直接统计((x+1,y+1)sim (x+1,max c))这条线段上每个点往(x)轴正方向延伸的DP值就行了。

这样做可能会统计到一些跟((x,y))不在一个矩形内部的点。但是我们发现它们一定不可能是最优解，所以没有关系。

时间复杂度(O(NMlog N+Qlog Qlog N))。

CO int N=2e3+10;
struct event {int l,r,u;};
vector<event> ins[N],era[N];

int hi[N];
namespace HI{
	multiset<int> tree[4*N];
	
	#define lc (x<<1)
	#define rc (x<<1|1)
	#define mid ((l+r)>>1)
	void build(int x,int l,int r){
		tree[x].clear();
		if(l==r) return;
		build(lc,l,mid),build(rc,mid+1,r);
	}
	void insert(int x,int l,int r,int ql,int qr,int v){
		if(ql<=l and r<=qr) {tree[x].insert(v); return;}
		if(ql<=mid) insert(lc,l,mid,ql,qr,v);
		if(qr>mid) insert(rc,mid+1,r,ql,qr,v);
	}
	void erase(int x,int l,int r,int ql,int qr,int v){
		if(ql<=l and r<=qr) {tree[x].erase(tree[x].find(v)); return;}
		if(ql<=mid) erase(lc,l,mid,ql,qr,v);
		if(qr>mid) erase(rc,mid+1,r,ql,qr,v);
	}
	void query(int x,int l,int r,int v){
		if(tree[x].size()) v=max(v,*tree[x].rbegin());
		if(l==r) {hi[l]=v; return;}
		query(lc,l,mid,v),query(rc,mid+1,r,v);
	}
	#undef lc
	#undef rc
	#undef mid
}

int ri[N];
namespace RI{
	multiset<int> tree[4*N];
	
	#define lc (x<<1)
	#define rc (x<<1|1)
	#define mid ((l+r)>>1)
	void build(int x,int l,int r){
		tree[x].clear();
		if(l==r) return;
		build(lc,l,mid),build(rc,mid+1,r);
	}
	void insert(int x,int l,int r,int ql,int qr,int v){
		if(ql<=l and r<=qr) {tree[x].insert(v); return;}
		if(ql<=mid) insert(lc,l,mid,ql,qr,v);
		if(qr>mid) insert(rc,mid+1,r,ql,qr,v);
	}
	void erase(int x,int l,int r,int ql,int qr,int v){
		if(ql<=l and r<=qr) {tree[x].erase(tree[x].find(v)); return;}
		if(ql<=mid) erase(lc,l,mid,ql,qr,v);
		if(qr>mid) erase(rc,mid+1,r,ql,qr,v);
	}
	void query(int x,int l,int r,int v){
		if(tree[x].size()) v=max(v,*tree[x].rbegin());
		if(l==r) {ri[l]=v; return;}
		query(lc,l,mid,v),query(rc,mid+1,r,v);
	}
	#undef lc
	#undef rc
	#undef mid
}

struct node {int v,w;} F[N][N];

IN node operator*(CO node&a,CO node&b){
	if(!b.v) return a;
	return {a.v+b.v,mul(a.w,b.w)};
}
IN node operator+(CO node&a,CO node&b){
	node ans={max(a.v,b.v)};
	if(ans.v==a.v) ans.w=add(ans.w,a.w);
	if(ans.v==b.v) ans.w=add(ans.w,b.w);
	return ans;
}

struct Seg{
	node tree[4*N];
	
	#define lc (x<<1)
	#define rc (x<<1|1)
	#define mid ((l+r)>>1)
	void build(int x,int l,int r){
		tree[x]={0,0};
		if(l==r) return;
		build(lc,l,mid),build(rc,mid+1,r);
	}
	void insert(int x,int l,int r,int p,CO node&v){
		tree[x]=tree[x]+v;
		if(l==r) return;
		if(p<=mid) insert(lc,l,mid,p,v);
		else insert(rc,mid+1,r,p,v);
	}
	node query(int x,int l,int r,int ql,int qr){
		if(ql>qr) return {0,0};
		if(ql<=l and r<=qr) return tree[x];
		if(qr<=mid) return query(lc,l,mid,ql,qr);
		if(ql>mid) return query(rc,mid+1,r,ql,qr);
		return query(lc,l,mid,ql,qr)+query(rc,mid+1,r,ql,qr);
	}
	#undef lc
	#undef rc
	#undef mid
}S[N];

node G[N];

namespace Val{
	node tree[4*N];
	
	#define lc (x<<1)
	#define rc (x<<1|1)
	#define mid ((l+r)>>1)
	void build(int x,int l,int r){
		if(l==r) {tree[x]=G[l]; return;}
		build(lc,l,mid),build(rc,mid+1,r);
		tree[x]=tree[lc]+tree[rc];
	}
	node query(int x,int l,int r,int ql,int qr){
		if(ql>qr) return {0,0};
		if(ql<=l and r<=qr) return tree[x];
		if(qr<=mid) return query(lc,l,mid,ql,qr);
		if(ql>mid) return query(rc,mid+1,r,ql,qr);
		return query(lc,l,mid,ql,qr)+query(rc,mid+1,r,ql,qr);
	}
	#undef lc
	#undef rc
	#undef mid
}

void real_main(){
	int n=read<int>(),m=read<int>();
	for(int x=1;x<=n+1;++x) ins[x].clear(),era[x].clear();
	for(int q=read<int>();q--;){
		int r1=read<int>(),c1=read<int>(),r2=read<int>(),c2=read<int>();
		if(r2-r1+1<=1 or c2-c1+1<=1) continue;
		ins[r2].push_back({c1,c2,r2});
		era[r1].push_back({c1,c2,r2});
	}
	HI::build(1,1,m);
	for(int y=1;y<=m;++y) S[y].build(1,1,n);
	RI::build(1,1,m);
	node ans={0,0};
	for(int x=n;x>=1;--x){
//		cerr<<"x="<<x<<endl;
		for(CO event&e:ins[x+1]) HI::insert(1,1,m,e.l+1,e.r,e.u);
		for(CO event&e:era[x+1]) HI::erase(1,1,m,e.l+1,e.r,e.u);
		HI::query(1,1,m,0);
//		cerr<<"hi=";
//		for(int y=1;y<=m;++y) cerr<<" "<<hi[y];
//		cerr<<endl;
		for(int y=m;y>=1;--y) G[y]=S[y].query(1,1,n,x+1,hi[y]);
		Val::build(1,1,m);
		for(CO event&e:ins[x+1]) RI::insert(1,1,m,e.l,e.r-1,e.r);
		for(CO event&e:era[x+1]) RI::erase(1,1,m,e.l,e.r-1,e.r);
		RI::query(1,1,m,0);
//		cerr<<"ri=";
//		for(int y=1;y<=m;++y) cerr<<" "<<ri[y];
//		cerr<<endl;
		for(int y=m;y>=1;--y){
			F[x][y]={1,1};
			F[x][y]=F[x][y]*Val::query(1,1,m,y+1,ri[y]);
			ans=ans+F[x][y];
			S[y].insert(1,1,n,x,F[x][y]);
		}
	}
//	cerr<<"F="<<endl;
//	for(int y=m;y>=1;--y){
//		for(int x=1;x<=n;++x) cerr<<" ("<<F[x][y].v<<","<<F[x][y].w<<")";
//		cerr<<endl;
//	}
	printf("%d %d
",ans.v,ans.w);
}
int main(){
//	freopen("roche.in","r",stdin),freopen("roche.out","w",stdout);
	for(int T=read<int>();T--;) real_main();
	return 0;
}

100分做法

https://www.cnblogs.com/daniel14311531/p/10507150.html

由于要求的是最长路经，所以对于路径相邻的两个位置((x_i, y_i))和((x_{i + 1}, y_{i + 1}))满足(x_i + 1 = x_{i + 1})或(y_i + 1 = y_{i + 1})。

考虑DP，预处理出每个点可以从那些地方转移（( ext{left}[i][j])和( ext{up}[i][j])分别维护这个点可以转移的最左和最上方的位置）。

然后单调队列+桶优化DP即可。

CO int N=2e3+10,M=5e5+10,inf=1e9;
struct rectangle {int xl,yl,xr,yr;} a[M];
int up[N][N],lt[N][N];

struct node {int v,w;} F[N][N];

IN node operator+(CO node&a,CO node&b){
	node ans={max(a.v,b.v)};
	if(ans.v==a.v) ans.w=add(ans.w,a.w);
	if(ans.v==b.v) ans.w=add(ans.w,b.w);
	return ans;
}

struct Queue{
	node que[N];
	int idx[N],L,R,sum[N];
	
	IN void init(int n){
		L=1,R=0,fill(sum+1,sum+n+1,0);
	}
	void insert(int x,CO node&a){
		for(;L<=R and que[R].v<a.v;--R)
			sum[que[R].v]=add(sum[que[R].v],mod-que[R].w);
		que[++R]=a,idx[R]=x;
		sum[a.v]=add(sum[a.v],a.w);
	}
	node query(int x){
		for(;L<=R and idx[L]<x;++L)
			sum[que[L].v]=add(sum[que[L].v],mod-que[L].w);
		return {que[L].v+1,sum[que[L].v]};
	}
}UP[N],LT[N];

void real_main(){
	int n=read<int>(),m=read<int>(),q=read<int>();
	for(int i=1;i<=q;++i)
		read(a[i].xl),read(a[i].yl),read(a[i].xr),read(a[i].yr);
	
	for(int x=1;x<=n;++x)for(int y=1;y<=m;++y)
		up[x][y]=lt[x][y]=inf;
	for(int i=1;i<=q;++i){
		for(int x=a[i].xl+1;x<=a[i].xr;++x)
			lt[x][a[i].yr]=min(lt[x][a[i].yr],a[i].yl);
		for(int y=a[i].yl+1;y<=a[i].yr;++y)
			up[a[i].xr][y]=min(up[a[i].xr][y],a[i].xl);
	}
	for(int x=n;x>=1;--x)for(int y=m;y>=1;--y){
		if(y<m) lt[x][y]=min(lt[x][y],lt[x][y+1]);
		if(x<n) up[x][y]=min(up[x][y],up[x+1][y]);
		if(lt[x][y]>=y) lt[x][y]=inf;
		if(up[x][y]>=x) up[x][y]=inf;
	}
	
	for(int x=1;x<=n;++x) LT[x].init(m);
	for(int y=1;y<=m;++y) UP[y].init(n);
	for(int x=1;x<=n;++x)for(int y=1;y<=m;++y) F[x][y]={1,1};
	for(int x=1;x<=n;++x)for(int y=1;y<=m;++y){
		LT[x].insert(y,F[x][y]);
		UP[y].insert(x,F[x][y]);
		if(lt[x+1][y+1]!=inf)
			F[x+1][y+1]=F[x+1][y+1]+LT[x].query(lt[x+1][y+1]);
		if(up[x+1][y+1]!=inf)
			F[x+1][y+1]=F[x+1][y+1]+UP[y].query(up[x+1][y+1]);
		if(lt[x+1][y+1]!=inf and up[x+1][y+1]!=inf and F[x+1][y+1].v==F[x][y].v+1)
			F[x+1][y+1].w=add(F[x+1][y+1].w,mod-F[x][y].w);
	}
	node ans={0,0};
	for(int x=1;x<=n;++x)for(int y=1;y<=m;++y) ans=ans+F[x][y];
	printf("%d %d
",ans.v,ans.w);
}
int main(){
//	freopen("roche.in","r",stdin),freopen("roche.out","w",stdout);
	for(int T=read<int>();T--;) real_main();
	return 0;
}

显然这份代码的(O(QN))能被扫描线优化到(O(Qlog Q))。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/autoint/p/12889381.html