权值线段树求调,样例都没过!
查看原帖
权值线段树求调,样例都没过!
363006
wangyibo201026楼主2022/5/3 10:51

代码:

#include<bits/stdc++.h>

#define int long long
#define endl '\n'

using namespace std;

const int N = 1e5 + 5;
const int M = 1e7;

int m;

struct Val_Segment_Tree{
	int tree[N] = {0}, top = 1;
	int lch[N] = {0}, rch[N] = {0};
	void pushup(int node){
		tree[node] = tree[lch[node]] + tree[rch[node]];
	}
	void insert(int node, int lt, int rt, int x, int val){
		if(!node){
			node = ++top;
		}
		if(x < lt || x > rt){
			return ;
		}
		if(lt == rt && lt == x){
			tree[node] += val;
			return ;
		}
		int mid = lt + rt >> 1;
		insert(lch[node], lt, mid, x, val);
		insert(rch[node], mid + 1, rt, x, val);
		pushup(node);
	}
	int rank(int node, int lt, int rt, int x){
		if(lt == rt){
			return lt - M;
		}
		int mid = lt + rt >> 1;
		if(x <= tree[lch[node]]){
			return rank(lch[node], lt, mid, x);
		}
		else{
			return rank(rch[node], mid + 1, rt, x - tree[lch[node]]);
		}
	}
	int query1(int node, int lt, int rt, int x){
		if(lt == rt){
			return tree[node];
		}
		int mid = lt + rt >> 1;
		if(x <= mid){
			return query1(lch[node], lt, mid, x);
		}
		else{
			return tree[lch[node]] + query1(rch[node], mid + 1, rt, x);
		}
	}
	int query2(int node, int lt, int rt, int x){
		if(lt == rt){
			return 1;
		}
		int mid = lt + rt >> 1;
		if(x <= mid){
			return query2(lch[node], lt, mid, x);
		}
		else{
			return tree[lch[node]] + query2(rch[node], mid + 1, rt, x);
		}
	}
}t;

signed main(){
	cin >> m;
	while(m--){
		int op;
		cin >> op;
		if(op == 1){
			int x;
			cin >> x;
			t.insert(1, 1, 2 * M, x + M, 1);
		}
		else if(op == 2){
			int x;
			cin >> x;
			t.insert(1, 1, 2 * M, x + M, -1);
		}
		else if(op == 3){
			int x;
			cin >> x;
			cout << t.query2(1, 1, 2 * M, x + M) << endl;
		}
		else if(op == 4){
			int x;
			cin >> x;
			cout << x << endl; 
			cout << t.rank(1, 1, 2 * M, x) << endl;
		}
		else if(op == 5){
			int x;
			cin >> x;
			cout << t.rank(1, 1, 2 * M, t.query2(1, 1, 2 * M, x + M) - 1) << endl;
		}
		else{
			int x;
			cin >> x;
			cout << t.rank(1, 1, 2 * M, t.query1(1, 1, 2 * M, x + M) + 1) << endl;
		}
	}
	return 0;
}
2022/5/3 10:51
加载中...