题解：P7220 [JOISC 2020] 掃除

· · 题解

P7220 [JOISC 2020] 掃除

题意

有四种操作：

  1. 询问点 x 的坐标
  2. 对所有 y\le l 的点进行 x=\max(x,n-l) 的操作
  3. 对所有 x\le l 的点进行 y=\max(y,n-l) 的操作
  4. 加入一个新的点 (x,y)

部分分 1（11 pts）

当只有前三种操作且满足 x_i\le x_{i+1},y_i\ge y_{i+1} 时，操作前后两点横纵坐标的关系不会因此而改变，因为每次受影响的点集是一个前缀或后缀。因此可以使用平衡树维护每个点的坐标，查询时直接询问第 x 个位置的值即可，时间复杂度 O(q\log m)。

部分分 2（64 pts）

当只有前三种操作时，因为没有了点之间特殊的位置关系，因此不能直接插入点。发现在一个点第一次被移动后插入可以满足 x_i\le x_{i+1},y_i\ge y_{i+1}。

证明：以操作二为例。当操作二移动点 i 时，对于已经被加入且满足 y_j\le y_i 的点 j 在操作之后一定会满足 x_j\ge x_i，因为 x_j\ge n-l=x_i；而对于已经被加入且满足 y_j>y_i 的点 j 在操作之后一定会满足 x_j\le x_i，因为若 x_j>x_i 就说明点 i 没被移动过而点 j 被移动过，但是由于 y_j>y_i，因此不可能出现该情况，即一定有 x_j\le x_i。操作三同理。

接下来就是计算每个点第一次被移动的时间点。考虑一个点被移动的条件。

  1. 操作二 l\ge y_i 或操作三 l\ge x_i。

  2. 操作二 n-l\le x_i 或操作三 n-l\le y_i。

条件二移位即可得到：操作二 n-x_i\ge l 或操作三 n-y_i\ge l。

也就是给 l 定了一个范围，那么用线段树维护单点修改，区间最小值（第一次的时刻即为满足条件的最小时刻）即可。时间复杂度 O(m\log n+q\log m)。

注意：因为不再是按原本的顺序插入，需要记录每个点对应平衡树上的点编号，并记录每个节点的父亲，查询时需要访问祖先节点下放标记。

正解

因为加入了操作四，直接维护较为困难。于是可以通过线段树分治拆分询问区间来实现。

具体的，若在时间 t 询问点 x，点 x 的加入时间为 s（前 m 个点在 0 时刻被加入），会影响该点坐标的就是操作区间 (s,t)。将其拆分成 \log q 个区间处理（将区间丢到线段树上，具体的可以去看【模板】线段树分治）。每个区间就是一个子问题，用上述部分分解法解决即可。

AC Code

#include <bits/stdc++.h>
#define fre(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);
#define lc (p << 1)
#define rc (p << 1 | 1)
using namespace std;
const int N = 1e6 + 5 , inf = 1e9 + 7;
mt19937 rd (time (0));
struct Treap
{
    int n = 0;
    struct Point
    {
        int x , y;
        bool operator < (Point A) const
        {
            if (x != A.x) return x < A.x;
            return y > A.y;
        }
        bool operator <= (Point A) const
        {
            if (x != A.x) return x < A.x;
            return y >= A.y;
        }
        bool operator == (Point A) const
        {
            return x == A.x && y == A.y;
        }
    };
    struct Node
    {
        int l , r;
        Point v;
        int w , sz;
        Point tag;
        int fa;
    } tr[N];
    int get_new (Point x)
    {
        tr[++ n] = {0 , 0 , x , rd () , 1 , {-1 , -1} , 0};
        return n;
    }
    void push_up (int p)
    {
        if (tr[p].l) tr[tr[p].l].fa = p;
        if (tr[p].r) tr[tr[p].r].fa = p;
    }
    void push_downx (int p)
    {
        if (~tr[p].tag.x)
        {
            int ls = tr[p].l , rs = tr[p].r;
            tr[ls].v.x = max (tr[ls].v.x , tr[p].tag.x);
            tr[rs].v.x = max (tr[rs].v.x , tr[p].tag.x);
            tr[ls].tag.x = max (tr[ls].tag.x , tr[p].tag.x);
            tr[rs].tag.x = max (tr[rs].tag.x , tr[p].tag.x);
            tr[p].tag.x = -1;
        }
    }
    void push_downy (int p)
    {
        if (~tr[p].tag.y)
        {
            int ls = tr[p].l , rs = tr[p].r;
            tr[ls].v.y = max (tr[ls].v.y , tr[p].tag.y);
            tr[rs].v.y = max (tr[rs].v.y , tr[p].tag.y);
            tr[ls].tag.y = max (tr[ls].tag.y , tr[p].tag.y);
            tr[rs].tag.y = max (tr[rs].tag.y , tr[p].tag.y);
            tr[p].tag.y = -1;
        }
    }
    void push_down (int p)
    {
        push_downx (p);
        push_downy (p);
    }
    void updx (int p , int x)
    {
        tr[p].v.x = max (tr[p].v.x , x);
        tr[p].tag.x = max (tr[p].tag.x , x);
    }
    void updy (int p , int x)
    {
        tr[p].v.y = max (tr[p].v.y , x);
        tr[p].tag.y = max (tr[p].tag.y , x);
    }
    void spl (int p , Point x , int &l , int &r)
    {
        if (!p)
        {
            l = r = 0;
            return ;
        }
        push_down (p);
        if (tr[p].v <= x)
        {
            l = p;
            spl (tr[p].r , x , tr[p].r , r);
            push_up (l);
        }
        else
        {
            r = p;
            spl (tr[p].l , x , l , tr[p].l);
            push_up (r);
        }
        tr[p].sz = tr[tr[p].l].sz + tr[tr[p].r].sz + 1;
    }
    void splx (int p , int x , int &l , int &r)
    {
        if (!p)
        {
            l = r = 0;
            return ;
        }
        push_down (p);
        if (tr[p].v.x <= x)
        {
            l = p;
            splx (tr[p].r , x , tr[p].r , r);
            push_up (l);
        }
        else
        {
            r = p;
            splx (tr[p].l , x , l , tr[p].l);
            push_up (r);
        }
        tr[p].sz = tr[tr[p].l].sz + tr[tr[p].r].sz + 1;
    }
    void sply (int p , int x , int &l , int &r)
    {
        if (!p)
        {
            l = r = 0;
            return ;
        }
        push_down (p);
        if (tr[p].v.y > x)
        {
            l = p;
            sply (tr[p].r , x , tr[p].r , r);
            push_up (l);
        }
        else
        {
            r = p;
            sply (tr[p].l , x , l , tr[p].l);
            push_up (r);
        }
        tr[p].sz = tr[tr[p].l].sz + tr[tr[p].r].sz + 1;
    }
    int mrg (int l , int r)
    {
        if (!l || !r)
            return l | r;
        if (tr[l].w <= tr[r].w)
        {
            push_down (l);
            tr[l].r = mrg (tr[l].r , r);
            tr[l].sz = tr[tr[l].l].sz + tr[tr[l].r].sz + 1;
            push_up (l);
            return l;
        }
        else
        {
            push_down (r);
            tr[r].l = mrg (l , tr[r].l);
            tr[r].sz = tr[tr[r].l].sz + tr[tr[r].r].sz + 1;
            push_up (r);
            return r;
        }
    }
    int size (int rt) {return tr[rt].sz;}
    int ins (int &rt , Point x)
    {
        int rl , rr;
        spl (rt , x , rl , rr);
        rt = mrg (mrg (rl , get_new (x)) , rr);
        return n;
    }
    void up (int rt , int p)
    {
        if (p ^ rt) up (rt , tr[p].fa);
        push_down (p);
    }
    Point get (int rt , int p)
    {
        up (rt , p);
        return tr[p].v;
    }
} T;
int rt;
int n , m , q , M , up1[N] , up2[N] , tim[N] , pos[N];
vector <int> add[N];
struct node
{int x , y , id;} a[N] , ans[N];
struct ST_MIN
{
    int Tr[N * 50] , ls[N * 50] , rs[N * 50] , idx = 0;
    void push_up (int p)
    {
        Tr[p] = inf;
        if (ls[p]) Tr[p] = min (Tr[p] , Tr[ls[p]]);
        if (rs[p]) Tr[p] = min (Tr[p] , Tr[rs[p]]);
    }
    void ins (int ps , int x , int &p , int s = 0 , int t = 1e9)
    {
        if (ps < 0) return ;
        if (!p) p = ++ idx , Tr[p] = inf , ls[p] = rs[p] = 0;
        if (s == t)
        {
            Tr[p] = min (Tr[p] , x);
            return ;
        }
        int mid = s + t >> 1;
        if (mid >= ps) ins (ps , x , ls[p] , s , mid);
        else ins (ps , x , rs[p] , mid + 1 , t);
        push_up (p);
    }
    int qry (int l , int r , int p , int s = 0 , int t = 1e9)
    {
        if (l > r) return inf;
        if (!p) return inf;
        if (l <= s && t <= r) return Tr[p];
        int mid = s + t >> 1;
        if (mid >= r) return qry (l , r , ls[p] , s , mid);
        else if (mid < l) return qry (l , r , rs[p] , mid + 1 , t);
        else return min (qry (l , r , ls[p] , s , mid) , qry (l , r , rs[p] , mid + 1 , t));
    }
} Tr1 , Tr2;
int rt1 , rt2;
bool vis[N];
int pt[N];
vector <int> que[N << 2];
void Add (int l , int r , int x , int p = 1 , int s = 1 , int t = q)
{
    if (l <= s && t <= r)
    {
        que[p].push_back (x);
        return ;
    }
    int mid = s + t >> 1;
    if (mid >= l) Add (l , r , x , lc , s , mid);
    if (mid < r) Add (l , r , x , rc , mid + 1 , t);
}
void clean ()
{
    rt1 = rt2 = rt = 0;
    Tr1.idx = Tr2.idx = T.n = 0;
}
void solve (int p = 1 , int l = 1 , int r = q)
{
    for (int j = l;j <= r;j ++)
    Tr1.ins (up1[j] - 1 , j , rt1) ,
    Tr2.ins (up2[j] - 1 , j , rt2) ;

    for (int i : que[p])
        vis[i] = 0 , tim[i] = min (Tr1.qry (ans[i].y , n - ans[i].x , rt1) , Tr2.qry (ans[i].x , n - ans[i].y , rt2));
    for (int i : que[p])
    {
        if (tim[i] == inf) continue;
        add[tim[i]].push_back (i);
    }

    for (int i = l;i <= r;i ++)
    {
        if (up1[i])
        {
            int L , R;
            T.sply (rt , up1[i] - 1 , R , L);
            T.updx (L , n - up1[i] + 1);
            rt = T.mrg (R , L);
        }
        else if (up2[i])
        {
            int L , R;
            T.splx (rt , up2[i] - 1 , L , R);
            T.updy (L , n - up2[i] + 1);
            rt = T.mrg (L , R);
        }
        for (int id : add[i])
        {
            vis[id] = 1;
            if (up1[i]) ans[id].x = n - up1[i] + 1;
            else ans[id].y = n - up2[i] + 1;
            pos[id] = T.ins (rt , {ans[id].x , ans[id].y});
        }
    }
    for (int i : que[p]) if (tim[i] ^ inf)
    {
        ans[i] = {T.get (rt , pos[i]).x , T.get (rt , pos[i]).y};
        add[tim[i]].clear ();
    }
    clean ();
    if (l == r) return ;
    int mid = l + r >> 1;
    solve (lc , l , mid);
    solve (rc , mid + 1 , r);
}
signed main ()
{
    ios::sync_with_stdio (0) , cin.tie (0) , cout.tie (0);
    cin >> n >> m >> q;
    for (int i = 1;i <= m;i ++) a[i].id = i , tim[i] = inf , cin >> a[i].x >> a[i].y , pt[i] = 1;
    for (int i = 1;i <= q;i ++)
    {
        int op , x , y;
        cin >> op >> x;
        if (op == 1) ans[++ M] = a[x] , Add (pt[x] , i , M);
        else if (op == 2) up1[i] = x + 1;
        else if (op == 3) up2[i] = x + 1;
        else cin >> y , ++ m , a[m] = {x , y , m} , pt[m] = i;
    }
    solve ();
    for (int i = 1;i <= M;i ++) cout << ans[i].x << ' ' << ans[i].y << '\n';
    return 0;
}