Special topic of binary tree -- [deep base 16. Example 7] ordinary binary tree (simplified version) (multiset seeks the precursor and subsequent sentry Art)

【 Deep base 16. example 7】 Ordinary binary tree （ Simplified edition ）

Title Description

You need to write a data structure , To maintain some numbers （ All are $10^9$ Numbers within ） Set , At first, the collection is empty . The following operations need to be provided , Operating frequency $q$ No more than $10^4$：

1. Inquire about $x$ Number of rankings （ Ranking is defined as the number of numbers smaller than the current number $+1$. If there are more than one identical number , The smallest ranking should be output ）.
2. Query rank is $x$ Number of numbers .
3. seek $x$ The precursor of （ Precursor is defined as less than $x$, And the largest number ）. If not found, output $-2147483647$.
4. seek $x$ In the subsequent （ The following definition is greater than $x$, And the smallest number ）. If not found, output $2147483647$.
5. Insert a number $x$.

Input format

Output format

Examples #1

The sample input #1

7
5 1
5 3
5 5
1 3
2 2
3 3
4 3

Sample output #1

2
3
1
5

Learn a black Technology , When Use multiset Find a value Forerunner / The subsequent when , We can The first multiset Insert a positive infinity and a negative infinity two sentinels , after , look for Forerunner / The subsequent There is no need for special judgment .

Be careful , This question is for Forerunner / The subsequent Is defined as ： Less than x / Greater than x, And Maximum / Minimum Number of numbers .

Specific code snippet as follows ：

tr.insert(inf), tr.insert(-inf);		// Insert the sentry 

auto p1 = tr.lower_bound(x);
int down = *(--p1);		// Forerunner 

auto p2 = tr.upper_bound(x);
int up = *p2;		// The subsequent 

Code ：

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>

using namespace std;
//#define int long long
//#define map unordered_map
const int N = 1e4 + 10, inf = 2147483647;

signed main()
{
    
	int T = 1; //cin >> T;

	while (T--)
	{
    
		multiset<int> tr;
		tr.insert(inf), tr.insert(-inf);
		int n; cin >> n;
		while (n--)
		{
    
			int op, x;
			cin >> op >> x;
			if (op == 5)
			{
    
				tr.insert(x);
			}
			else if (op == 1)
			{
    
				int rk = 0;
				for (auto i = tr.begin(); i != tr.end(); i++)
				{
    
					if ((*i) < x)
					{
    
						rk++;
					}
				}
				cout << rk << '\n';
			}
			else if (op == 2)
			{
    
				int rk = 0;
				int tgt;
				for (auto i = tr.begin(); i != tr.end(); i++)
				{
    
					rk++;
					if (rk == x + 1)
					{
    
						tgt = (*i);
						break;
					}
				}
				cout << tgt << '\n';
			}
			else if (op == 3)
			{
    
				auto p = tr.lower_bound(x);
				int down = *(--p);
				
				cout << down << '\n';
			}
			else if (op == 4)
			{
    
				auto p = tr.upper_bound(x);
				int up = *p;
				cout << up << '\n';
			}
		}
	}

	return 0;
}