专栏文章

题解：P7220 [JOISC 2020] 掃除

llovely_nst
P7220题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minmgtix
此快照首次捕获于
2025/12/02 04:49
3 个月前
此快照最后确认于
2025/12/02 04:49
3 个月前
查看原文

P7220 [JOISC 2020] 掃除

题意

有四种操作：
  1. 询问点 xx 的坐标
  2. 对所有 y≤ly\le l 的点进行 x=max⁡(x,n−l)x=\max(x,n-l) 的操作
  3. 对所有 x≤lx\le l 的点进行 y=max⁡(y,n−l)y=\max(y,n-l) 的操作
  4. 加入一个新的点 (x,y)(x,y)

部分分 1（11 pts）

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

部分分 2（64 pts）

当只有前三种操作时，因为没有了点之间特殊的位置关系，因此不能直接插入点。发现在一个点第一次被移动后插入可以满足 xi≤xi+1,yi≥yi+1x_i\le x_{i+1},y_i\ge y_{i+1}。
证明：以操作二为例。当操作二移动点 ii 时，对于已经被加入且满足 yj≤yiy_j\le y_i 的点 jj 在操作之后一定会满足 xj≥xix_j\ge x_i，因为 xj≥n−l=xix_j\ge n-l=x_i；而对于已经被加入且满足 yj>yiy_j>y_i 的点 jj 在操作之后一定会满足 xj≤xix_j\le x_i，因为若 xj>xix_j>x_i 就说明点 ii 没被移动过而点 jj 被移动过，但是由于 yj>yiy_j>y_i，因此不可能出现该情况，即一定有 xj≤xix_j\le x_i。操作三同理。
接下来就是计算每个点第一次被移动的时间点。考虑一个点被移动的条件。
  1. 操作二 l≥yil\ge y_i 或操作三 l≥xil\ge x_i。
  2. 操作二 n−l≤xin-l\le x_i 或操作三 n−l≤yin-l\le y_i。
条件二移位即可得到：操作二 n−xi≥ln-x_i\ge l 或操作三 n−yi≥ln-y_i\ge l。
也就是给 ll 定了一个范围，那么用线段树维护单点修改，区间最小值（第一次的时刻即为满足条件的最小时刻）即可。时间复杂度 O(mlog⁡n+qlog⁡m)O(m\log n+q\log m)。
注意：因为不再是按原本的顺序插入，需要记录每个点对应平衡树上的点编号，并记录每个节点的父亲，查询时需要访问祖先节点下放标记。

正解

因为加入了操作四，直接维护较为困难。于是可以通过线段树分治拆分询问区间来实现。
具体的，若在时间 tt 询问点 xx，点 xx 的加入时间为 ss（前 mm 个点在 00 时刻被加入），会影响该点坐标的就是操作区间 (s,t)(s,t)。将其拆分成 log⁡q\log q 个区间处理（将区间丢到线段树上，具体的可以去看【模板】线段树分治）。每个区间就是一个子问题，用上述部分分解法解决即可。

AC Code

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...