传送门

给定一个n*m的网格，有k个地雷，不能踩到地雷所在格子，从（1，1）出发，只能往左或者往下走，问最多可以到达多少个格子。

由于n，m都是1e5级别，所以我们不能模拟。

我们先观察一个结论，

• 对于第i行，假设有y1,y2两个雷，[y1+1,y2-1]这个区间格子如何能被到达呢？

• 只能从上面下来，所以我们在第i-1行中找打[y1+1,y2-1]这个区间内最左端的可到达的位置idx,那么第i行的[idx,y2-1]这个区间都是可到达的了。

• 如果我们用1代表可到达，0代表不可到达，上面的操作实质就是区间查询，区间覆盖，最后每行的答案就是查询区间和，每行答案累加起来就是最终答案。（除了维护区间和之外，还需要额外维护区间内最左端1的位置。）

• 我们考虑对每行都建一个线段树，但是空间不够，我们可以只建两棵，用滚动数组的思想。每次滚动都把区间更新成全是0的情况。

• 枚举到第i行时，每次先假设第i行都是0，然后枚举地雷进行区间更新

• 细节：1、第一行需要特判。2、我们可以假设第0列，第m+1列都是雷，这样可以省略很多特殊情况的判断

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define ull unsigned long long
#define ll long long
#define pii pair<int, int>
const int maxn = 1e5 + 10;
const ll mod = 998244353;
const ll inf = (ll)4e16+5;
const int INF = 1e9 + 7;
const double pi = acos(-1.0);
ll inv(ll b){if(b==1)return 1;return(mod-mod/b)*inv(mod%b)%mod;}
inline ll read()
{ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
struct node 
{#define lc rt<<1#define rc rt<<1|1int l,r;int idx;//最小的 1所在的列 没有1则记为m+1 1表示可以走int sum;//区间和  表示可以走的格子数 每结束一行 求一次区间和 累加答案 
}tree[2][maxn<<2];
int tag[2][maxn<<2];//区间覆盖的lazy 1表示覆盖成1  2表示覆盖成0
int n,m,q;
inline void pushup(int rt,int k) 
{tree[k][rt].sum=tree[k][lc].sum + tree[k][rc].sum;tree[k][rt].idx=min(tree[k][lc].idx , tree[k][rc].idx);
}
void build(int rt,int l,int r,int k)//刚开始假设全部不能走
{tree[k][rt].l=l,tree[k][rt].r=r;tag[k][rt]=0;if(l==r){tree[k][rt].idx=m+1;tree[k][rt].sum=0;return ;}int mid=l+r>>1;build(lc,l,mid,k);build(rc,mid+1,r,k);pushup(rt,k);
}
inline void change(int rt,int v,int k)
{tree[k][rt].sum=(tree[k][rt].r-tree[k][rt].l+1)*(v%2);if(!tree[k][rt].sum) {tree[k][rt].idx=m+1;}else tree[k][rt].idx=tree[k][rt].l;tag[k][rt]=v;
}
inline void pushdown(int rt,int k)
{if(tag[k][rt]) {change(lc,tag[k][rt],k);change(rc,tag[k][rt],k);tag[k][rt]=0;}
}
void upd(int rt,int vl,int vr,int v,int k)
{int l=tree[k][rt].l,r=tree[k][rt].r;if(vr<l || vl>r || vr<vl) return ;if(vl<=l && r<=vr) {change(rt,v,k);return ;}pushdown(rt,k);upd(lc,vl,vr,v,k);upd(rc,vl,vr,v,k);pushup(rt,k);
}
int qry(int rt,int vl,int vr,int k)
{int l=tree[k][rt].l,r=tree[k][rt].r;if(vr<l || vl>r || vr<vl) return m+1;if(vl<=l && r<=vr) {return tree[k][rt].idx;}pushdown(rt,k);return min(qry(lc,vl,vr,k) , qry(rc,vl,vr,k));
}
int qry1(int rt,int vl,int vr,int k)
{int l=tree[k][rt].l,r=tree[k][rt].r;if(vr<l || vl>r || vr<vl) return 0;if(vl<=l && r<=vr) {return tree[k][rt].sum;}pushdown(rt,k);return qry(lc,vl,vr,k) + qry(rc,vl,vr,k);
}
vector<int> dead[maxn];
int main()
{int t;cin>>t;while(t--){scanf("%d %d %d",&n,&m,&q);for(int i=0;i<=n+1;i++) dead[i].clear();for(int i=1,x,y;i<=q;i++){scanf("%d %d",&x,&y);dead[x].push_back(y);}//不妨假设第0列 m+1列 全是雷for(int i=1;i<=n;i++) {dead[i].push_back(0);dead[i].push_back(m+1);sort(dead[i].begin(),dead[i].end());}build(1,1,m,1);//建树build(1,1,m,0);ll ans=0;//特判第一行if((int)dead[1].size() == 2) //除0 m+1列外没有雷{upd(1,1,m,1,1);}else upd(1,1,dead[1][1]-1,1,1);//1到第一个雷前一格的这段区间 可以走ans+=qry1(1,1,m,1);for(int i=2;i<=n;i++){upd(1,1,m,2,i%2);//滚动数组 先假设这一行全不能走for(int j=0;j<(int)dead[i].size()-1;j++){int y1=dead[i][j],y2=dead[i][j+1];//第i-1行的线段树中 查询[y1+1,y2-1]区间内 最左端的1int left=qry(1,y1+1,y2-1,(i-1)%2);if(left == m+1) continue;//都是0upd(1,left,y2-1,1,i%2);}ans+=qry1(1,1,m,i%2);}printf("%lld\n",ans);}return 0;
}