2021“MINIEYE杯”中国大学生算法设计超级联赛（4）

1008：Lawn of the Dead

题面

思路：

线段树 从上到下维护每一行可达的点有哪些。
在第 i 行 如果和不能走，那么在 i - 1 行 [ j + 1 , k - 1 ] 区间内最左边的能到达的点 x，那么第i行的 [ x , k - 1 ]就是可到达的

代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int N=1e6+5;
int n,m,k;
vector<int> vv[N];
int sum[3][N<<2];
int las[3][N<<2];

void pup(int id,int rt){
    sum[id][rt]=sum[id][rt<<1]+sum[id][rt<<1|1];
}

void pdown(int id,int rt,int l,int r){
    if(las[id][rt]==-1)
        return ;
    int mid=l+r>>1;
    sum[id][rt<<1]=(mid-l+1)*las[id][rt];
    sum[id][rt<<1|1]=(r-mid)*las[id][rt];
    las[id][rt<<1]=las[id][rt];
    las[id][rt<<1|1]=las[id][rt];
    las[id][rt]=-1;
}

void build(int id,int l,int r,int rt){
    las[id][rt]=-1;
    if(l==r){
        sum[id][rt]=0;
        return ;
    }
    int mid=l+r>>1;
    build(id,l,mid,rt<<1);
    build(id,mid+1,r,rt<<1|1);
    pup(id,rt);
}
void update(int id,int l,int r,int val,int ll,int rr,int rt){
    if(l<=ll&&r>=rr){
        sum[id][rt]=(rr-ll+1)*val;
        las[id][rt]=(rr-ll+1)*val;
        return ;
    }
    pdown(id,rt,ll,rr);
    int mid=ll+rr>>1;
    if(l<=mid)
        update(id,l,r,val,ll,mid,rt<<1);
    if(r>mid)
        update(id,l,r,val,mid+1,rr,rt<<1|1);
    pup(id,rt);
}
int query(int id,int l,int r,int ll,int rr,int rt){
    if(ll==rr){
        if(sum[rt])
            return ll;
        return -1;
    }
    pdown(id,rt,ll,rr);
    int mid=ll+rr>>1;
    int pos=-1;
    if(l<=mid&&sum[id][rt<<1])
        pos=query(id,l,r,ll,mid,rt<<1);
    if(pos!=-1)
        return pos;
    if(r>mid&&sum[id][rt<<1|1])
        return query(id,l,r,mid+1,rr,rt<<1|1);
    return -1;  
}
int main(){
    int T;
    cin>>T;
    while(T--){
        scanf("%d%d%d",&n,&m,&k);
        long long ans=0;
        for(int i=1;i<=n;i++)
            vv[i].clear();
        int x,y;
        for(int i=1;i<=k;i++){
            scanf("%d%d",&x,&y);
            vv[x].push_back(y);
        }
        for(int i=1;i<=n;i++){
            vv[i].push_back(0);
            vv[i].push_back(m+1);
            sort(vv[i].begin(),vv[i].end());
        }
        int now=1;
        build(0,1,m,1);
        build(1,1,m,1);
        
        if(vv[1].size()==2){
            update(0,1,m,1,1,m,1);
            ans+=m;
        }else{
            update(0,1,vv[1][1]-1,1,1,m,1);
            ans+=vv[1][1]-1;
        }
        
        for(int i=2;i<=n;i++){
            for(int j=0;j<vv[i].size()-1;j++){
                int l=vv[i][j]+1;
                int r=vv[i][j+1]-1;
                if(l>r)
                    continue;
                int pos=query(now^1,l,r,1,m,1);
                if(pos==-1)
                    continue;
                update(now,pos,r,1,1,m,1);
                ans+=r-pos+1;
            }
            now^=1;
            update(now,1,m,0,1,m,1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

// rt << 1 | 1