HDU 6992 Lawn of the Dead (线段树）

题目链接
题目描述：

题目大意：
一个僵尸在一个N*M的矩阵里面初始位置为（1，1），它只能向有或向下走，且矩阵中有些点有土豆雷它无法走到这个点，求僵尸能够走到的所有点的个数。

思路分析：
通过题目意思分析我们可以知道，知道一个将能走到一个点，当且仅当它的上面的点或左边的点至少有一个能走到，那么僵尸才能走到这个点（矩阵外的点看作是不能走的点）。第一行是一个特殊情况，因为题目保证（1，1）点是可以达到的，所以我们设边界（0，1）也是可以到达的。所以我们可以根据上一层的状态来确定下一层，能够到达的点。在每一层中我们找到连续无土豆雷点区间，在上一层中我们找到相同区间中第一个可以到达点的下标（对应当前层），从这个下标到当前层区间结束，就是这一层这段连续区间能够走到的长度。

因为数据是1e5*1e5所以直接暴力开一个二维数组是不可行，其实我们发现只需要保存上一层信息就可以得出当前层能够走到的点的个数，于是自然而然就想到可以用滚动数组来存。但是每一层暴力查询区间信息和修改区间信息，总的时间复杂度依然是O（n^2)的，所以我们可以用线段来优化区间查询和区间修改操作，将时间复杂度降到nlogn级别就可以AC了。

代码：

#include<bits/stdc++.h>
using namespace std;
/*线段树中某端区间更新为1，表示这段区间可走
某段区间更新为0，表示这段区间不可走，默认为不可走
线段树每个节点记录当前表示的区间能走的点数，累加每一层能走的点数就是最终答案*/
typedef long long ll;
const int INF=0x3f3f3f3f; 
int t;
int n,m,k;
int x,y;
ll ans;
struct ty{
    int l,r;
    int d;//d记录的数每一段区间能到达的点的数量 
    int lazy;
    //laze表示初始化为-1，0表示这个区间不可被到达，1表示这个可以被到达 
};
vector<int > g[100005];
ty tr[2][100005*4];
//建立线段树 
inline void build(int f,int u,int l,int r){
    tr[f][u].l=l;tr[f][u].r=r;
    if(l==r){
        tr[f][u].d=0;tr[f][u].lazy=-1;
        return ;
    }
    int mind=(l+r)>>1;
    build(f,u<<1,l,mind);
    build(f,u<<1|1,mind+1,r);
    tr[f][u].d=0;tr[f][u].lazy=-1;
    return ;
} 
//懒标记操作 
inline void pushdown(int f,int u){
    if(tr[f][u].lazy==-1) return ;
    tr[f][u<<1].d=(tr[f][u<<1].r-tr[f][u<<1].l+1)*tr[f][u].lazy;
    tr[f][u<<1].lazy=tr[f][u].lazy;
    tr[f][u<<1|1].d=(tr[f][u<<1|1].r-tr[f][u<<1|1].l+1)*tr[f][u].lazy;
    tr[f][u<<1|1].lazy=tr[f][u].lazy;
    tr[f][u].lazy=-1;
    return ;
}
//线段树更新 
inline void modify(int f,int u,int l,int r,int d){
    if(tr[f][u].l>=l&&tr[f][u].r<=r){
        tr[f][u].d=(tr[f][u].r-tr[f][u].l+1)*d;
        tr[f][u].lazy=d;
        return ;
    }
    pushdown(f,u);
    int mind=(tr[f][u].l+tr[f][u].r)>>1;
    if(l<=mind) modify(f,u<<1,l,r,d);
    if(r>mind) modify(f,u<<1|1,l,r,d);
    tr[f][u].d=tr[f][u<<1].d+tr[f][u<<1|1].d;
    return ;
}
//线段树查询 
inline int query(int f,int u,int l,int r){
    if(!tr[f][u].d) return INF;
    if(tr[f][u].l==tr[f][u].r) return tr[f][u].l;//**这里是返回tr[f][u].l**
    pushdown(f,u);
    int mind=(tr[f][u].l+tr[f][u].r)>>1;
    if(tr[f][u].l>=l&&tr[f][u].r<=r){//记得写不然会超时
        if(tr[f][u<<1].d>0) return query(f,u<<1,l,r);
        else return query(f,u<<1|1,l,r);
    }
    int t1=INF,t2=INF;
    if(l<=mind) t1=query(f,u<<1,l,r);
    if(r>mind) t2=query(f,u<<1|1,l,r);
    return min(t1,t2);
}
int main(){
    scanf(" %d",&t);
    while(t--){
        ans=0;
        scanf(" %d %d %d",&n,&m,&k);
        for(int i=1;i<=n;i++) g[i].clear();
        for(int i=1;i<=k;i++){
            scanf(" %d %d",&x,&y);
            g[x].push_back(y);//记录每一行不能走的点
        }
        build(0,1,1,m);//建立第一颗线段树 
        build(1,1,1,m);//建立第二个线段树 
        modify(0,1,1,1,1);//初始化第一个线段树 
        for(int i=1;i<=n;i++){
            sort(g[i].begin(),g[i].end());//**记得排序**
            int len=g[i].size();
            int l=0,r;//r表示不能这一排不能到达的点的左边界 
            for(int j=0;j<len;j++){
                r=g[i][j];
                if(l+1<=r-1) {//表示存在一段没土豆雷的一段连续区间 
                    int pos=query((i&1)^1,1,l+1,r-1);//如果pos=INF表示这一段区间都不能走 
                    if(pos!=INF) modify(i&1,1,pos,r-1,1);//修改给当前区间，给当前区间每个点加一，表示这个点可以到达
                }
                l=r; 
            }
            if(l+1<=m){
                int pos=query((i&1)^1,1,l+1,m);
                if(pos!=INF) modify(i&1,1,pos,m,1);
            }
            ans+=tr[i&1][1].d;
            modify((i&1)^1,1,1,m,0);//将之前的线段树清空，用作下一次线段树 
        }
        printf("%lld\n",ans); 
    }    
    return 0;
}