在pb_ds tree/set 中插入元素的方法？

我们如果要在pb_ds tree/set 中插入元素，还要保证一直有序（类似这题在数组中插入元素），那我们可以用这种神奇的方式维护。

用这道题为例，我们维护一个三元组，让第一个元素为原始下标的

10^6

倍，第二个值为时间轴/操作数，第三个值为要存的元素，那么我们插入的时候我们要插入第

i

个数前面，那我们就让这个数的第一关键字为

i

和

i-1

的第一关键字的一半（向下取整）。然后第二关键字为

tim

表示操做数，第三关键字为加入的值，这样很难卡，需要有

\log

个相同的

i

插入并插入

i+1

才会被卡。所以过掉了本题，有没有更好的方式让 pb_ds 插入元素呢？

我的代码：

CPP

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define fi first
#define se second
#define int long long
#define pii pair<int,int>
#define piii pair<pii,int>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace __gnu_pbds;
using namespace std;
int n,m;
tree<piii,null_type,less<piii>,rb_tree_tag,tree_order_statistics_node_update>tr;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
    cin>>n;tr.insert({{0,0},0});
    rep(i,1,n+1){
        int x;cin>>x;tr.insert({{i*(1<<20),0},x});
	}rep(i,1,n){
		int op;cin>>op;
		if(op==0){
			int l,r;cin>>l>>r;
			piii t1=*tr.find_by_order(l);
			piii t2=*tr.find_by_order(l-1);
			piii t3={{(t1.fi.fi+t2.fi.fi)/2,i},r};
			tr.insert(t3);
		}else{
			int c;cin>>c;
			cout<<(*tr.find_by_order(c)).se<<'\n';
		}
	}
	return 0;
}

在pb_ds tree/set 中插入元素的方法？

讨论操作

回复

相关推荐

在pb_ds tree/set 中插入元素的方法？