【CCCC】L3-026 传送门 (30分)，splay（待复盘）

problem

7-14 传送门
平面上有 2n 个点，它们的坐标分别是 (1,0),(2,0),⋯(n,0) 和 (1,10
​9
​​ ),(2,10
​9
​​ ),⋯,(n,10
​9
​​ )。我们称这些点中所有 y 坐标为 0 的点为“起点”，所有 y 坐标为 10
​9
​​ 的点为终点。一个机器人将从坐标为 (x,0) 的起点出发向 y 轴正方向移动。显然，该机器人最后会到达某个终点，我们设该终点的 x 坐标为 f(x)。

在上述条件下，显然有 f(x)=x。不过这样的数学模型就太无趣了，因此我们对上述数学模型做一些小小的改变。我们将会对模型进行 q 次修改，每一次修改都是以下两种操作之一：

• x
  ​′
  ​​ x
  ​′′
  ​​ y: 在 (x
  ​′
  ​​ ,y) 与 (x
  ​′′
  ​​ ,y) 处增加一对传送门。当机器人碰到其中一个传送门时，它会立刻被传送到另一个传送门处。数据保证进行该操作时，(x
  ​′
  ​​ ,y) 与 (x
  ​′′
  ​​ ,y) 处当前不存在传送门。

• x
  ​′
  ​​ x
  ​′′
  ​​ y: 移除 (x
  ​′
  ​​ ,y) 与 (x
  ​′′
  ​​ ,y) 处的一对传送门。数据保证这对传送门存在。
  求每次修改后
  ​x=1
  ​∑
  ​n
  ​​ xf(x) 的值。

输入格式：
第一行输入两个整数 n 与 q (2≤n≤10
​5
​​ , 1≤q≤10
​5
​​ )，代表起点和终点的数量以及修改的次数。

接下来 q 行中，第 i 行输入一个字符 op
​i
​​ 以及三个整数 x
​i
​′
​​ , x
​i
​′′
​​ and y
​i
​​ (op
​i
​​ ∈{‘+’ (ascii: 43),‘-’ (ascii: 45)}, 1≤x
​i
​′
​​ <x
​i
​′′
​​ ≤n, 1≤y
​i
​​ <10
​9
​​ )，代表第 i 次修改的内容。修改顺序与输入顺序相同。

输出格式：
输出 q 行，其中第 i 行包含一个整数代表第 i 次修改后的答案。

输入样例：
5 4

• 1 3 1
• 1 4 3
• 2 5 2

• 1 4 3
  输出样例：
  51
  48
  39
  42
  样例解释：
  修改 | f(1) | f(2) | f(3) | f(4) | f(5) | 结果 — | — + 1 3 1 | 3 | 2 | 1 | 4 | 5 | 51 + 1 4 3 | 3 | 2 | 4 | 1 | 5 | 48 + 2 5 2 | 3 | 5 | 4 | 1 | 2 | 39 - 1 4 3 | 3 | 5 | 1 | 4 | 2 | 42

solution

/*
+ 一开始初始化成n条链，传送门对应链上的结点，将所有需要新增或者删除的传送门的y值离散化，存入链上。
+ 对于每个操作，实际上要做的是“分别查询两个结点各自所在链上的左右端点”和“将两个结点的后继结点交换”，用splay可以做到logq
*/
#include<bits/stdc++.h>
using namespace std;
typedef long  long LL;
const int maxn = 5e5+10, inf =1e9+10;

int n, m;
struct node{int x1,x2,y1,y2;}qr[maxn];
vector<int>rt[maxn];

#define l(u) ch[u][0]
#define r(u) ch[u][1]
int fa[maxn], ch[maxn][2], tot, X[maxn];
int sf(int u){return u== r(fa[u]);}
bool isrt(int u){return u!=l(fa[u])&&u!= r(fa[u]);}
void rot(int u){
	int v=fa[u],f= sf (u);
	if(!isrt(v))ch[fa[v]][sf(v)]= u;
	ch[v][f]=ch[u][f^1],fa[ch[v][f]]= v;
	fa[u]=fa[v],ch[u][f^1]=v,fa[v]= u;
}
int newnode(){int u=++tot; fa[u]=l(u)=r(u)= 0 ; return u;}
void splay(int u){ for(;!isrt(u); rot(u))if(!isrt(fa[u])&&sf(fa[u])==sf(u))rot(fa[u]);}
int fdl(int u){splay(u); for(;l(u); u=l(u)); splay(u); return u;}
int fdr(int u){splay(u); for(;r(u); u=r(u)); splay(u); return u;}

int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1; i <= m; i++){
		char ch;  cin>>ch;
		cin>>qr[i].x1>>qr[i].x2>>qr[i].y1;
	}
	for(int i=1; i <= n; i++){
		rt[i].push_back(0);  rt[i].push_back(inf);
	}
	for(int i=1; i <= m; i++){
		rt[qr[i].x1].push_back(qr[i].y1);
		rt[qr[i].x2].push_back(qr[i].y1);
	}
	for(int i=1; i <= n; i++){
		sort(rt[i].begin(),rt[i].end());
		rt[i].resize(unique(rt[i].begin(),rt[i].end()) - rt[i].begin());
	}
	for(int i=1; i <= m; i++){
		int y = qr[i].y1;
		qr[i].y1= lower_bound(rt[qr[i].x1].begin(),rt[qr[i].x1].end(),y)- rt[qr[i].x1].begin();
		qr[i].y2=lower_bound(rt[qr[i].x2].begin(),rt[qr[i].x2].end(),y)- rt[qr[i].x2].begin( );
	}
	for(int i=1; i <= n; i++){
		for(int j=0; j<rt[i].size(); j++){
			rt[i][j]=newnode(); X[rt[i][j]]= i;
		}
		for(int j=0; j<rt[i].size()-1; j++){
			r(rt[i][j])=rt[i][j+1],fa[rt[i][j+1]]= rt[i][j];
		}
	}
	LL ans=(LL)n*(n+1)*(2*n+1)/6;
	for(int i=1; i <= m; i++){
		int x1=qr[i].x1,x2=qr[i].x2,y1=qr[i].y1,y2=qr[i].y2;
		int u=rt[x1][y1],v= rt[x2][y2];
		int lu=X[fdl(u)],ru=X[fdr(u)],lv=X[fdl(v)],rv= X[fdr(v)];
		ans-=(LL)lu*ru+(LL)lv*rv;
		ans+=(LL)lu*rv+(LL) lv*ru;
		splay(u),splay(v);
		int u2=r(u),v2=r(v);
		r(u)=v2,r(v)=u2,fa[v2]=u,fa[u2]=v;
		cout<<ans<<"\n";
	}
	return 0;
}



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/115015964