题解：P11340 [COI 2019] TENIS

· · 题解

\Large{\text{Solution}}

::::info[本题解中变量的含义]{open} 题解中变量和代码中相同。

神秘性质：一个 X 无法获胜，当且仅当存在 pos<minp_X，使得所有满足 1\le i \le 3,1 \le j \le pos 的 p_{i,j} 的集合大小为 pos。（也就等于 p_{1,j},p_{2,j},p_{3,j} 分别组成的集合）。

首先充分性是很明显的。前 pos 个没有其他人能战胜，他们内斗也一定会留下一人占据三个第一。至于必要性，如果不满足条件，肯定可以消掉前面的，并且不会出现消到中间消不掉的情况，所以可以。

如何判断？设置 N 个区间 [minp_i,maxp_i)，覆盖在线段树上，如果有一个点的值为 0，那么说明这个点前后没有关联，也就是这个点就是 pos。修改也很简单，把之前的删掉处理新的就行。

\Large{\text{Code}} 
#include <bits/stdc++.h>
//#define int long long
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <int, pii> piii;
const double PI = acos (-1);
const double eps = 1e-10;
const int N = 1e5 + 10, M = 2e5 + 10;
//const int mod = 1e9 + 7;
//const int mod = 998244353;

int p[4][N], maxp[N], minp[N];
struct node
{
    int l, r;
    int minn, tag;
} tr[N << 2];
void pushup(int u)
{
    tr[u].minn = min (tr[u << 1].minn, tr[u << 1 | 1].minn);
}
void pushdown(int u)
{
    int& tag = tr[u].tag;
    if (!tag) return;
    tr[u << 1].tag += tag;
    tr[u << 1 | 1].tag += tag;
    tr[u << 1].minn += tag;
    tr[u << 1 | 1].minn += tag;
    tag = 0;
}
void build(int u, int l, int r)
{
    tr[u].l = l, tr[u].r = r;
    if (l == r) return;
    int mid = l + r >> 1;
    build (u << 1, l, mid);
    build (u << 1 | 1, mid + 1, r);
}
void add(int u, int l, int r, int x)
{
    if (l > r) return;
    if (l <= tr[u].l && tr[u].r <= r)
    {
        tr[u].minn += x;
        tr[u].tag += x;
        return;
    }
    pushdown (u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) add (u << 1, l, r, x);
    if (r > mid) add (u << 1 | 1, l, r, x);
    pushup (u);
}
int find(int u, int l, int r)
{
    if (l > r) return 1;
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].minn;
    pushdown (u);
    int mid = tr[u].l + tr[u].r >> 1;
    int res = 2e9;
    if (l <= mid) res = min (res, find (u << 1, l, r));
    if (r > mid) res = min (res, find (u << 1 | 1, l, r));
    return res;
}

signed main()
{
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= n; j++)
        {
            int x;
            cin >> x;
            p[i][x] = j;
        }
    build (1, 1, n);
    for (int i = 1; i <= n; i++)
    {
        maxp[i] = max (p[1][i], max (p[2][i], p[3][i]));
        minp[i] = min (p[1][i], min (p[2][i], p[3][i]));
        add (1, minp[i], maxp[i] - 1, 1);
        // cout << p[1][i] << " " << p[2][i] << " " << p[3][i] << " " << minp[i] << " " << maxp[i] << "\n";
    }
    for (int i = 1; i <= q; i++)
    {
        // for (int j = 1; j <= n; j++)
        //     cout << find (1, j, j) << " ";
        // puts ("");
        int op;
        cin >> op;
        if (op == 1)
        {
            int x;
            cin >> x;
            int val = find (1, 1, minp[x] - 1);                                                                                                                         
            if (!val) puts ("NE");
            else puts ("DA");
        }
        else
        {
            int x, a, b;
            cin >> x >> a >> b;
            add (1, minp[a], maxp[a] - 1, -1);
            add (1, minp[b], maxp[b] - 1, -1);
            swap (p[x][a], p[x][b]);
            maxp[a] = max (p[1][a], max (p[2][a], p[3][a]));
            minp[a] = min (p[1][a], min (p[2][a], p[3][a]));
            maxp[b] = max (p[1][b], max (p[2][b], p[3][b]));
            minp[b] = min (p[1][b], min (p[2][b], p[3][b]));
            add (1, minp[a], maxp[a] - 1, 1);
            add (1, minp[b], maxp[b] - 1, 1);
        }
    }
    return 0;
}