Rinne Loves Data Structure

NC22596. Rinne Loves Data Structure

描述

Rinne 喜欢 OI。在 9102 年的 PION 中，她在初赛遇到了这样一道题目：

阅读下列代码，然后回答问题。

补充：建树过程中会更新lc和rc，这实质上是一个二叉查找树的插入过程。

定义一个玄学节点叫做 R，每次操作读入 val ，执行 Insert(R,val)。

问题：每次 Insert 操作结束之后，输出当前节点的深度和。
这里我们定义 R 节点的深度为 0。

输入描述

第一行一个整数 N，表示操作次数。

接下来 N 行，第 i 行有一个值 ，表示第 i 次操作的 。

输出描述

N 行，每行输出该次操作完后的答案。

示例1

输入:

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 958ms, 内存消耗: 37552K, 提交时间: 2023-07-14 17:58:00

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6;
const int mod = 3e5 + 5;
int n;
int x;
set<int>s;
map<int,int>mp;
int ans;
signed main(){
	cin >> n;
	s.insert(-mod);
	s.insert(mod);
	mp[-mod] = -1;
	mp[mod] = -1;
	while(n--){
		cin >> x;
		auto p = s.lower_bound(x);
		auto t = p--;
		mp[x] = max(mp[*p],mp[*t]) + 1;
		ans += mp[x];
		s.insert(x);
		cout << ans << endl;
	}
}
/*
2
5
2 1
4 3
5 3
3 2



*/