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
*/
