7.11考试-解题报告
i207M
2019-07-11 14:33:06
为啥最后一场考**题啊。
## T1
线段树预处理up和left，然后单调队列优化DP。
这个预处理挺值得思考的。
我们如果离线正着扫描，那么就要处理“区间取max”，区间撤销一次取max，这没啥一个log做法。
但是我们倒着扫，我们扫描到改撤销的时候并不用撤销，因为这种情况下即使我们不修改，这个max比当前位置还要靠后，所以会自动被忽略掉。我们没扫描完就dfs这棵线段树，这样复杂度就是$O(q\log q+nm)$~~，但是题解有q不带log的做法，感觉很神仙。~~ 假的，std写的是qn的
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
#define ri register int
#define il inline
#define fi first
#define se second
#define solid const auto &
typedef long long LL;
typedef pair<int,int> pii;
template<class T>il void in(T &x)
{
x=0; char c=getchar(); bool f=0;
while(!isdigit(c)) f|=(c=='-'),c=getchar();
while(isdigit(c)) x=x*10+(c^'0'),c=getchar();
f?x=-x:0;
}
template<class T>il void out(T x,const char c='\n')
{
static short st[30]; short tp=0;
if(x<0) putchar('-'),x=-x;
do st[++tp]=x%10,x/=10; while(x);
while(tp) putchar('0'|st[tp--]);
putchar(c);
}
template<class T>il void err(const T &x,const char c='\n') {cerr<<x<<c;}
template<class T,class ...Args>il void err(const T &x,const Args &...args) {err(x,' '),err(args...);}
const int md=1e9+7;
il int qpow(int a,int b) {int r=1; for(;b;b>>=1,a=(LL)a*a%md) if(b&1) r=(LL)r*a%md; return r;}
il int fit(const int x) {return x>=md?x-md:x;}
il void inc(int &x,const int v) {(x+=v)>=md?x-=md:0;}
namespace i207M
{
const int N=2005; // WARN N, M
struct Data
{
int mx,cnt;
il void operator+=(const Data &v)
{
if(v.mx>mx) *this=v;
else if(v.mx==mx) inc(cnt,v.cnt);
}
il void err() {::err(mx,cnt);}
};
const int inf=0x3f3f3f3f;
int n,m,cq;
int lm[N][N],um[N][N];
Data s[N][N];
Data ans;
namespace S
{
struct Queue
{
int q[N],hd,tl;
int sm;
Data qd[N];
int sc[N];
il void clear()
{
hd=sm=1,tl=0;
}
il void getsm()
{
while(sm<tl&&qd[sm+1].mx==qd[hd].mx) ++sm;
}
il void push(int id,const Data &d)
{
while(hd<=tl&&qd[tl].mx<d.mx) --tl;
sm=min(sm,tl);
q[++tl]=id,qd[tl]=d;
sc[tl]=fit(sc[tl-1]+d.cnt);
getsm();
}
il void pop2(int l)
{
while(hd<=tl&&q[hd]<l) ++hd;
sm=max(sm,hd);
getsm();
}
il Data ask()
{
if(hd>tl) return (Data){0,0};
return (Data){qd[hd].mx,fit(sc[sm]-sc[hd-1]+md)};
}
} lq[N],hq;
void solve()
{
ans.mx=ans.cnt=0;
for(ri j=0;j<=m;++j) lq[j].clear();
for(ri i=1;i<=n;++i)
{
hq.clear();
for(ri j=1;j<=m;++j)
{
s[i][j]=(Data){0,1};
hq.pop2(lm[i][j]);
lq[j-1].pop2(um[i][j]);
s[i][j]+=hq.ask();
s[i][j]+=lq[j-1].ask();
++s[i][j].mx;
ans+=s[i][j];
hq.push(j,s[i-1][j]);
lq[j-1].push(i-1,s[i-1][j-1]);
}
}
}
}
namespace T
{
const int M=N*4;
const int rt=1;
#define gm int mid((l+r)>>1)
#define ls (x<<1)
#define rs (x<<1|1)
int mn[M];
il void build(int x,int l,int r)
{
mn[x]=inf;
if(l==r) return;
gm; build(ls,l,mid),build(rs,mid+1,r);
}
void upd(int x,int l,int r,int ql,int qr,int v)
{
if(ql<=l&&r<=qr)
{
mn[x]=min(mn[x],v);
return;
}
gm;
if(ql<=mid) upd(ls,l,mid,ql,qr,v);
if(qr>mid) upd(rs,mid+1,r,ql,qr,v);
}
void dfsl(int x,int l,int r,int lie,int v)
{
v=min(v,mn[x]);
if(l==r)
{
lm[l][lie]=v;
return;
}
gm;
dfsl(ls,l,mid,lie,v),dfsl(rs,mid+1,r,lie,v);
}
void dfsu(int x,int l,int r,int han,int v)
{
v=min(v,mn[x]);
if(l==r)
{
um[han][l]=v;
return;
}
gm;
dfsu(ls,l,mid,han,v),dfsu(rs,mid+1,r,han,v);
}
struct Tan
{
int x1,y1,x2,y2;
il void init()
{
in(x1),in(y1),in(x2),in(y2);
}
il void err() {::err(x1,y1,x2,y2);}
};
const int S=500005;
Tan tn[S];
int id[S];
void prework()
{
for(ri i=1;i<=cq;++i) id[i]=i;
sort(id+1,id+1+cq,[](const int a,const int b) {return tn[a].y2>tn[b].y2;});
build(rt,1,n);
for(ri j=m,p=1;j>=1;--j)
{
while(p<=cq&&tn[id[p]].y2==j)
{
solid it=tn[id[p]];
if(it.x1<it.x2) upd(rt,1,n,it.x1+1,it.x2,it.y1);
++p;
}
dfsl(rt,1,n,j,inf);
}
sort(id+1,id+1+cq,[](const int a,const int b) {return tn[a].x2>tn[b].x2;});
build(rt,1,m);
for(ri i=n,p=1;i>=1;--i)
{
while(p<=cq&&tn[id[p]].x2==i)
{
solid it=tn[id[p]];
if(it.y1<it.y2) upd(rt,1,m,it.y1+1,it.y2,it.x1);
++p;
}
dfsu(rt,1,m,i,inf);
}
}
}
il void clear()
{
for(ri i=1;i<=n;++i)
for(ri j=1;j<=m;++j)
{
s[i][j].mx=s[i][j].cnt=0;
}
}
signed main()
{
#ifdef M207
freopen("in.in","r",stdin);
//freopen("ot.out","w",stdout);
#else
freopen("roche.in","r",stdin);
freopen("roche.out","w",stdout);
#endif
int T; in(T);
for(ri o=1;o<=T;++o)
{
clear();
in(n),in(m),in(cq);
for(ri i=1;i<=cq;++i)
{
T::tn[i].init();
}
T::prework();
S::solve();
out(ans.mx,' '),out(ans.cnt);
}
return 0;
}
}
signed main()
{
i207M::main();
return 0;
}
```
## T2
感觉可做，但是看不懂题解。
## T3
摸了。