#P5880. 遊生夢死

    ID: 6425 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-坐标变换离散化普通线段树有序多重集合

遊生夢死

题目描述

维护两个初始为空的点可重集 U,VU,V。若任一集合为空,定义 F(U,V)=−1F(U,V)=-1。否则定义

$$F(U,V)=\min_{\substack{(u_x,u_y)\in U\\(v_x,v_y)\in V}} \max(u_x+v_x,\ u_y+v_y).$$

每次向其中一个集合插入一个点,或删除一个点的一次出现。每次操作后求 F(U,V)F(U,V)。

输入格式

第一行一个整数 qq,表示操作数。接下来 qq 行,每行四个整数 op,s,x,yop,s,x,y。

  • s=1s=1 表示操作集合 UU,s=2s=2 表示操作集合 VV。
  • op=1op=1 表示插入一个 (x,y)(x,y)。
  • op=2op=2 表示删除一个 (x,y)(x,y)。保证操作前该集合至少有一个此点,重复时只删除一个。

输出格式

输出 qq 行,第 ii 行一个整数,表示第 ii 次操作后的 F(U,V)F(U,V)。

样例

6
1 1 100 100
1 2 30 130
1 1 120 170
2 1 100 100
1 2 70 100
2 1 120 170
-1
230
230
300
270
-1

原题另在下发文件中提供样例 2–4。

数据范围

1≤q≤2.5×1051\le q\le2.5\times10^5,op,s∈{1,2}op,s\in\{1,2\},0≤x,y≤2.5×1050\le x,y\le2.5\times10^5。

子任务 分值 附加限制
1 所有操作 s=1s=1
2 10 q≤104q\le10^4
3 20 x,y≤100x,y\le100
4 30 q≤105q\le10^5
5 39 无

原题来源 Gym 103627 A。

原 PDF 题面