题解：P5983 [PA 2019] Osady i warownie 2

· · 题解

桑格莉娅不止一次地启发我做网格行走相关题目：

贴模型走路是一个很实用的技巧，可以在这类网格路径题中有效地去除一些重复冗余状态。

比如这道题，定义首末两行、两列为边缘部分，其他为非边缘部分，我们可以发现无论怎么在非边缘部分添加障碍，都存在至少两条合法路径，如下图：

OOOOO
O.X.O
OXX.O
OX.XO
OOOOO

X 代表障碍，O 代表边缘部分，. 是普通的空地。我们发现只要存在边缘部分，我们就不用管普通的空地。

但是边缘部分可能会改变。比如在一个空的 5 \times 5 网格中添加一个障碍：

OOOX.
O.OOO
O...O
O...O
OOOOO

不难发现障碍的作用是“如果处在原来的边缘部分，就把这个边缘部分挪个地方到左下角/右上角”，或者说“如果处在原来的边缘部分，则令自己左下角/右上角不可能再为边缘部分”。到底哪个角就要看自己原先处在左下角的边缘还是右上角的边缘。如果同时处在两类边缘，那说明没有路径可以走了，此时输出 TAK，我们也顺便获得了是否有路径的充要条件。

边缘的修改是可以均摊的，因为每个点最多被一类边缘用一次，于是写一个事件驱动模拟。其中需要找最大最小值，set 常数大，换成堆就可以了。

 /* NE_Cat 4.1 */
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;

const int N = 100010;
typedef pair < int, int > PII;
struct Point {int x, y, val, id;} p[N * 10];
int n, m, k, lim[4][N]; map < PII, int > mp;
priority_queue < PII, vector < PII >, greater < PII > > conS[4][N];
priority_queue < PII > conL[4][N];

inline bool check(int opt, Point pos)
{
    if(opt == 0 && pos.y <= lim[0][pos.x]) return true;
    if(opt == 1 && pos.x >= lim[1][pos.y]) return true;
    if(opt == 2 && pos.y >= lim[2][pos.x]) return true;
    if(opt == 3 && pos.x <= lim[3][pos.y]) return true;
    return false;
}
inline void search_A(Point pos);
inline void search_B(Point pos);
inline void get(int opt, int id);
inline void get(int opt, int id)
{
    if(opt == 0)
    {
        while(!conS[0][id].empty() && conS[0][id].top().first <= lim[0][id])
        {
            PII cur = conS[0][id].top();
            conS[0][id].pop();
            search_A(p[cur.second]);
        }
    }
    else if(opt == 1)
    {
        while(!conL[1][id].empty() && conL[1][id].top().first >= lim[1][id])
        {
            PII cur = conL[1][id].top();
            conL[1][id].pop();
            search_A(p[cur.second]);
        }
    }
    else if(opt == 2)
    {
        while(!conL[2][id].empty() && conL[2][id].top().first >= lim[2][id])
        {
            PII cur = conL[2][id].top();
            conL[2][id].pop();
            search_B(p[cur.second]);
        }
    }
    else
    {
        while(!conS[3][id].empty() && conS[3][id].top().first <= lim[3][id])
        {
            PII cur = conS[3][id].top();
            conS[3][id].pop();
            search_B(p[cur.second]);
        }
    }
}
inline void search_A(Point pos)
{
//  cerr << "A " << pos.x << " " << pos.y << '\n';
    if(pos.x - 1 >= 1)
    {
        lim[0][pos.x - 1] = max(lim[0][pos.x - 1], pos.y + 1);
        get(0, pos.x - 1);
    }
    if(pos.y + 1 <= m)
    {
        lim[1][pos.y + 1] = min(lim[1][pos.y + 1], pos.x - 1);
        get(1, pos.y + 1);
    }
}
inline void search_B(Point pos)
{
//  cerr << "B " << pos.x << " " << pos.y << '\n';
    if(pos.x + 1 <= n)
    {
        lim[2][pos.x + 1] = min(lim[2][pos.x + 1], pos.y - 1);
        get(2, pos.x + 1);
    }
    if(pos.y - 1 >= 1)
    {
        lim[3][pos.y - 1] = max(lim[3][pos.y - 1], pos.x + 1);
        get(3, pos.y - 1);
    }
}

int main()
{
//  freopen("text.in", "r", stdin);
//  freopen("prog.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 1; i <= k; ++i) cin >> p[i].x >> p[i].y >> p[i].val, p[i].id = i;
    memset(lim[1], 0x3f, sizeof(lim[1]));
    memset(lim[2], 0x3f, sizeof(lim[2]));
    lim[0][n] = m; lim[1][1] = 1;
    lim[2][1] = 1; lim[3][m] = n;
    for(int i = 1, v = 0; i <= k; ++i)
    {
        p[i].x ^= v, p[i].y ^= v;
        p[i].x %= n, p[i].y %= m;
        ++p[i].x, ++p[i].y;
//      cerr << p[i].x << " " << p[i].y << " +++++++++++++++++++++++++++++\n";
        if(mp[{p[i].x, p[i].y}]) {cout << "NIE" << '\n'; continue;}
        mp[{p[i].x, p[i].y}] = true;
        if(!check(0, p[i]) && !check(1, p[i]) && !check(2, p[i]) && !check(3, p[i]))
        {
            cout << "NIE" << '\n';
            conS[0][p[i].x].push({p[i].y, i});
            conL[1][p[i].y].push({p[i].x, i});
            conL[2][p[i].x].push({p[i].y, i});
            conS[3][p[i].y].push({p[i].x, i});
        }
        else if((check(0, p[i]) || check(1, p[i])) && (check(2, p[i]) || check(3, p[i])))
        {
            cout << "TAK" << '\n';
            v ^= p[i].val; mp[{p[i].x, p[i].y}] = false;
        }
        else if(check(0, p[i]) || check(1, p[i])) cout << "NIE" << '\n', search_A(p[i]);
        else cout << "NIE" << '\n', search_B(p[i]);
    }
    return 0;
}
/*

*/