codechef Graph on a Table

https://www.codechef.com/problems/TBGRAPH

题意 :

一个\(n\times m\)的网格图。\(q\) 个矩形，格子\((r1,c1)\)可以到达\((r2,c2)\)的条件是\(r2>r1,c2>c1\)且存在一个矩形同时包含这两个点。
初始点任意，求最多走几步以及方案数。
\(T\le 100000,S=\sum nm\le 10^7,\sum q\le 500000,\ n,m\le 2000\)

分析:

首先一个点\((r1,c1)\)只需要连\((r1+1,k)\)和\((k,c1+1)\)这些点，其他的点可以通过这些点到达。
那么我们求出每个点向右，向下扩展的最远点，这个可以用类似扫描线的东西扫两次，用\(set\)维护每个位置的最远点，复杂度\(O(q\log q+nm)\)。
然后可以\(dp\)，这个\(dp\)显然可以单调队列一下，开\(m+1\)个队列即可。
方案数的话在队列里进出的同时顺便用个数组维护一下就可以了。
没什么意思，单纯只是代码长。

代码:

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

#include <bitset>

#include <set>

#include <iostream>

using namespace std;

typedef long long ll;

#define mod 1000000007

//n,m<=2000,q<=500000

#define N 1000050

#define M 4000050

#define db(x) cerr<<#x<<" = "<<x<<endl

int n,m,q,id[2050][2050];

int la=0,f[M],g[M];

int now[N],rt[M],dw[M],r1[N],c1[N],r2[N],c2[N];

multiset<int>St[2050];

int Q[2050],Q2[2050][2050],L[2050],R[2050];

int nowans[2050],nowans2[2050][2050];

char buf[100000],*p1,*p2;

#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)

int rd() {

	int x=0; char s=nc();

	while(s<'0'||s>'9') s=nc();

	while(s>='0'&&s<='9') x=(((x<<2)+x)<<1)+s-'0',s=nc();

	return x;

}

struct A {

	int l,r,x,o;

	A() {}

	A(int l_,int r_,int x_,int o_) {l=l_,r=r_,x=x_,o=o_;}

	bool operator < (const A &u) const {

		return x<u.x;

	}

}a[N];

inline void upd(int x,int y) {

	if(f[y]<f[x]+1) f[y]=f[x]+1,g[y]=g[x];

	else if(f[y]==f[x]+1) g[y]=(g[y]+g[x])%mod;

}

inline void UPD(int &x,int y) {

	x+=y; if(x>=mod) x-=mod;

}

int NOW;

// int ss=0,sq=0;

void solve() {

	NOW++;

	n=rd(),m=rd(),q=rd();

	// ss+=n*m,sq+=q;

	int i,j,k,ln=n*m;

	int gg=0;

	for(i=0;i<=ln+1;i++) f[i]=g[i]=0;

	for(i=1;i<=n;i++)for(j=1;j<=m;j++)id[i][j]=++gg;

	for(i=1;i<=n;i++)for(j=1;j<=m;j++)rt[id[i][j]]=j,dw[id[i][j]]=i;

	for(i=1;i<=q;i++)r1[i]=rd(),c1[i]=rd(),r2[i]=rd(),c2[i]=rd();

	// if(NOW==17)for(i=1;i<=q;i++) printf("%d %d %d %d\n",r1[i],c1[i],r2[i],c2[i]);

	// return ;

	la=0;

	for(i=1;i<=q;i++) if(r1[i]!=r2[i]) {

		a[++la]=A(c1[i],c2[i],r1[i],1);

		a[++la]=A(c1[i],c2[i],r2[i],-1);

	}

	sort(a+1,a+la+1);

	for(i=1;i<=m;i++) now[i]=i,St[i].clear();

	j=1;

	for(i=1;i<=n;i++) {

		for(;j<=la&&a[j].x==i;j++) {

			int x=a[j].l;

			if(a[j].o==1) St[x].insert(a[j].r);

			else St[x].erase(St[x].find(a[j].r));

			if(!St[x].empty()) now[x]=*St[x].rbegin();

			else now[x]=x;

		}

		for(k=1;k<=m;k++) {

			rt[id[i][k]]=max(rt[id[i][k-1]],now[k]);

		}

	}

	la=0;

	for(i=1;i<=q;i++) if(c1[i]!=c2[i]) {

		a[++la]=A(r1[i],r2[i],c1[i],1);

		a[++la]=A(r1[i],r2[i],c2[i],-1);

	}

	sort(a+1,a+la+1);

	for(i=1;i<=n;i++) now[i]=i,St[i].clear();

	j=1;

	for(i=1;i<=m;i++) {

		for(;j<=la&&a[j].x==i;j++) {

			int x=a[j].l;

			if(a[j].o==1) St[x].insert(a[j].r);

			else St[x].erase(St[x].find(a[j].r));

			if(!St[x].empty()) now[x]=*St[x].rbegin();

			else now[x]=x;

		}

		for(k=1;k<=n;k++) {

			dw[id[k][i]]=max(dw[id[k-1][i]],now[k]);

		}

	}

	for(i=1;i<=m;i++) for(j=0;j<=n;j++) nowans2[i][j]=0;

	for(i=1;i<=m;i++) L[i]=R[i]=0;

	for(i=1;i<=n;i++) {

		int l=0,r=0;

		for(j=0;j<=m;j++) nowans[j]=0;

		for(j=1;j<=m;j++) {

			f[id[i][j]]=1; g[id[i][j]]=1;

			if(j>1) {

				while(l<r&&rt[Q[l]]<j) {

					UPD(nowans[f[Q[l]]],mod-g[Q[l]]);

					l++;

				}

				if(l<r) {

					f[ln+1]=f[Q[l]];

					g[ln+1]=nowans[f[Q[l]]];

					upd(ln+1,id[i][j]);

				}

				if(i>2) {

					while(L[j-1]<R[j-1]&&dw[Q2[j-1][L[j-1]]]<i) {

						UPD(nowans2[j-1][f[Q2[j-1][L[j-1]]]],mod-g[Q2[j-1][L[j-1]]]);

						L[j-1]++;

					}

					if(L[j-1]<R[j-1]) {

						f[ln+1]=f[ Q2[j-1][ L[j-1] ] ];

						g[ln+1]=nowans2[j-1][f[ln+1]];

						upd(ln+1,id[i][j]);

					}

				}

			}

			if(i>1) {

				while(l<r&&f[Q[r-1]]<f[id[i-1][j]]) {

					UPD(nowans[f[Q[r-1]]],mod-g[Q[r-1]]);

					r--;

				}

				Q[r++]=id[i-1][j];

				UPD(nowans[f[id[i-1][j]]],g[id[i-1][j]]);

			}

			upd(id[i][j],0);

		}

		if(i>1) {

			for(j=1;j<=m;j++) {

				while(L[j]<R[j]&&f[Q2[j][R[j]-1]]<f[id[i-1][j]]) {

					UPD(nowans2[j][f[Q2[j][R[j]-1]]],mod-g[Q2[j][R[j]-1]]);

					R[j]--;

				}

				Q2[j][R[j]++]=id[i-1][j];

				UPD(nowans2[j][f[id[i-1][j]]],g[id[i-1][j]]);

			}

		}

	}

	printf("%d %d\n",f[0]-1,g[0]);

}

// #include <ctime>

// double tt;

int main() {

	// freopen("roche.in","r",stdin);

	// freopen("roche.out","w",stdout);

	// tt=clock();

	int T;

	scanf("%d",&T);

	while(T--) solve();

	// printf("%.2f\n",(clock()-tt)/1000.0);

	// printf("%d %d\n",sq,ss);

}

/*

2

3 4 2

1 1 2 2

2 2 3 4

3 3 2

1 1 3 3

1 1 3 3

*/

巴特西

codechef Graph on a Table

codechef Graph on a Table

最新文章

热门文章