【学习笔记】[PA2019] Osady i warownie 2

出题人脑洞好大，拜谢出题人。

这题好抽象😱

EI 说这题可以转化为对偶图，但是我完全没看懂😅

考虑维护最向右和向下的两条路径，那么不能放的位置就是两条路径的交（感性理解一下）

考虑抽象的描述这条路径，$r_i$表示第$i$行能到达的最大的列，那么$\{r_i\}$是单调不降的，等价于我们要维护字典序最大/最小的路径

考虑向下的怎么维护。首先，这个点一定要在路径上，即$r_{x-1}\le y\le r_x$（假设插入的点是$(x,y)$）；其次，我们希望以最小的代价调整（尽量保持前缀不变），但是又必须绕过$(x,y)$，这等价于$\forall i\ge x-1,r_i=\max(r_i,y+1)$。注意到每次调整时至少有一个障碍以后不会被考虑到，因此总调整数目不会超过$O(k)$。

因此递归下去即可。

复杂度$O(k\log k)$。

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int n,m,K,v;
struct node{
    set<int>sx[100005],sy[100005];
    int bit[100005];
    int n,m;
    int get(int x,int y){
        return sx[x].count(y);
    }
    void add(int x,int y){
        for(x++;x<=n;x+=x&-x)bit[x]=max(bit[x],y);
    }
    int qmax(int x){
        int y(0);
        for(x++;x;x-=x&-x)y=max(y,bit[x]);
        return y;
    }
    int query(int x,int y){
        if(x==0)return qmax(x)>=y;
        return qmax(x-1)<=y&&y<=qmax(x);
    }
    void upd(int x,int y){
        if(!query(x,y))return;
        add(x-1,y+1),x--,y++;
        if(sx[x].size()&&sx[x].upper_bound(y)!=sx[x].begin()){
            auto it=--sx[x].upper_bound(y);
            upd(x,*it);
        }
        if(sy[y].size()&&sy[y].lower_bound(x)!=sy[y].end()){
            auto it=sy[y].lower_bound(x);
            upd(*it,y);
        }
    }
    void ins(int x,int y){
        sx[x].insert(y),sy[y].insert(x);
        upd(x,y);
    }
}R,D;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>K;
    D.n=n,D.m=m;
    R.n=m,R.m=n;
    D.add(n-1,m-1);
    R.add(m-1,n-1);
    for(int i=1;i<=K;i++){
        int r,c,z;
        cin>>r>>c>>z;
        r=(r^v)%n,c=(c^v)%m;
        if(D.get(r,c)){
            cout<<"NIE"<<"\n";
        }
        else if(D.query(r,c)&&R.query(c,r)){
            cout<<"TAK"<<"\n";
            v^=z;
        }   
        else{
            cout<<"NIE"<<"\n";
            D.ins(r,c),R.ins(c,r);
        }
    }
}