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

这题好抽象😱

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

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

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

考虑向下的怎么维护。首先，这个点一定要在路径上，即$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);}}
}