关于pb_ds库中的平衡树的一个疑惑
查看原帖
关于pb_ds库中的平衡树的一个疑惑
482856
TigerNick楼主2024/8/11 21:01

为什么上面的代码WA,下面的代码AC,仅修改了数字的偏移量。

#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;
tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> bbt;  
int n,c,num;
map<int,int> mp;
signed main(){
    scanf("%lld",&n);  
    while(n--)
    {
        scanf("%lld%lld",&c,&num);
        switch(c)
		{ 
	        case 1:  
	        {
	            bbt.insert((num<<20)+mp[num]);
	            mp[num]++;
	            break;
	        }
	        case 2:
	        {
	            bbt.erase(bbt.lower_bound(num<<20));
	            mp[num]--;
	            break;
	        }
	        case 3:  
	            printf("%lld\n",bbt.order_of_key(num<<20)+1);  
	            break;  
	        case 4:  
	            printf("%lld\n",*bbt.find_by_order(num-1)>>20);
	            break; 
	        case 5:
	        	printf("%lld\n",*--bbt.lower_bound(num<<20)>>20);
	        	break;
	        case 6:
				printf("%lld\n",*bbt.lower_bound((num+1)<<20)>>20);
	        	break;
        }
    }
    return 0;
}
#include<bits/stdc++.h> 
#include<ext/pb_ds/assoc_container.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;  
tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> bbt;  
int n,num;  
int c,cnt;  
//map<int,int> mp;
signed main(){
    scanf("%lld",&n);  
    while(n--)
    {
        scanf("%lld%lld",&c,&num);++cnt;
        switch(c)
		{ 
	        case 1:  
	        {
	            bbt.insert((num<<20)+cnt-1);
	            //mp[num]++;
	            break;
	        }
	        case 2:
	        {
	            bbt.erase(bbt.lower_bound(num<<20));
	            //mp[num]--;
	            break;
	        }
	        case 3:  
	            printf("%lld\n",bbt.order_of_key(num<<20)+1);  
	            break;  
	        case 4:  
	            printf("%lld\n",*bbt.find_by_order(num-1)>>20);
	            break; 
	        case 5:
	        	printf("%lld\n",*--bbt.lower_bound(num<<20)>>20);
	        	break;
	        case 6:
				printf("%lld\n",*bbt.lower_bound((num+1)<<20)>>20);
	        	break;
        }
    }
    return 0;
}
2024/8/11 21:01
加载中...