块状链表求助(已经封装好,可读性高)
  • 板块学术版
  • 楼主LBYYSM_123
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/8/11 15:07
  • 上次更新2023/11/3 04:29:03
查看原帖
块状链表求助(已经封装好,可读性高)
707513
LBYYSM_123楼主2023/8/11 15:07
#include<bits/stdc++.h>
using namespace std;
const int sz=1000,th=2*sz;
typedef int var;
struct SK{
	vector<vector<var>> dt;
	int get(int lin){
		int wei=-2e9;
		if(dt.size()==0) return -1;
		for(int i=0;i<dt.size();i++){
			if(wei<lin&&lin<=dt[i].back())
				return i;
			wei=dt[i].back();
		} 
		return -1;
	}
	void insert(int p){
		int i=get(p);
		dt[i].emplace(lower_bound(dt[i].begin(),dt[i].end(),p),p);
		if(dt[i].size()>th){
			dt.emplace(dt.begin()+i+1,dt[i].end()-sz,dt[i].end());
			dt[i].erase(dt[i].end()-sz,dt[i].end());
		}
	}
	void erase(int p){
		int i=get(p);
		dt[i].erase(lower_bound(dt[i].begin(),dt[i].end(),p));
		if(dt[i].size()==0)dt.erase(dt.begin()+i);
	}
	int kth(int n){
		for(auto i:dt){
			if(i.size()<=n)
				n-=i.size();
			else
				return i[n];
		}
		return -1;
	}
	int clt(int n){
		int ans=0;
		for(auto i:dt){
			if(i.back()<n)
				ans+=i.size();
			else{
				for(auto j:i)
					if(j<n)
						ans++;
					else
						break;
			}
		}
		return ans;
	}
	int pre(int p){
        int i=get(p);
        auto ps=lower_bound(dt[i].begin(),dt[i].end(),p);
        if(ps==dt[i].begin())
			return dt[i-1].back();
        return *prev(ps);
    }
    int nex(int p){
        int i=get(p);
        auto ps=upper_bound(dt[i].begin(),dt[i].end(),p);
        if(ps==dt[i].end())
			return dt[i+1].front();
        return *ps;
    }
}tree;
vector<var> t;
signed main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int opt;
		cin>>opt;
		if(opt==1){
			int lin;
			cin>>lin;
			tree.insert(lin);
		}
		else if(opt==2){
			int lin;
			cin>>lin;
			tree.erase(lin);
		}
		else if(opt==3){
			int lin;
			cin>>lin;
			cout<<tree.clt(lin)<<endl;
		}
		else if(opt==4){
			int lin;
			cin>>lin;
			cout<<tree.kth(lin);
		}
		else if(opt==5){
			int lin;
			cin>>lin;
			cout<<tree.pre(lin);
		}
		else if(opt==6){
			int lin;
			cin>>lin;
			cout<<tree.nex(lin);
		}
	}
    return 0;
}

不知道为什么,插入时就会RE,帮一下忙吧。

2023/8/11 15:07
加载中...