MnZn刚学权值线段树求助
查看原帖
MnZn刚学权值线段树求助
171513
Polariserist楼主2020/12/16 16:58

RT,倒数第二个点WA(负数)

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int ml=1,mr=1e7,maxn=1001010,it=0x3f3f3f3f;
int cnt=1,tree[maxn*4],tls[maxn*4],trs[maxn*4];
void spread(int p){
	if(!tls[p]){
		tls[p]=++cnt;
	}
	if(!trs[p]){
		trs[p]=++cnt;
	}
}
void add(int x,int d,int p=1,int cl=ml,int cr=mr){
	if(cl==cr){
		tree[p]+=d;
		return;
	}
	int mid=(cr+cl-1)/2;
	spread(p);
	if(x<=mid){
		add(x,d,tls[p],cl,mid);
	}
	else{
		add(x,d,trs[p],mid+1,cr);
	}
    tree[p]=tree[tls[p]]+tree[trs[p]];
}
int ask(int l,int r,int p=1,int cl=ml,int cr=mr){
	if(cl>r||cr<l)return 0;
	if(cl>=l&&cr<=r){
		return tree[p];
	}
	int mid=(cl+cr-1)/2;
	spread(p);
	return ask(l,r,tls[p],cl,mid)+ask(l,r,trs[p],mid+1,cr);
}
void insert(int v){
	add(v,1);
}
void remov(int v){
	add(v,-1);
}
int countl(int v){
	return ask(ml,v-1);
}
int countg(int v){
	return ask(v+1,mr);
}
int rnk(int v){
	return countl(v)+1;
}
int kth(int k,int p=1,int cl=ml,int cr=mr){
	if(cl==cr)return cl;
	int mid=(cl+cr-1)/2;
	if(tree[tls[p]]>=k)return kth(k,tls[p],cl,mid);
	else return kth(k-tree[tls[p]],trs[p],mid+1,cr);
}
int pre(int v){
	int r=countl(v);
	return kth(r);
}
int suc(int v){
	int r=tree[1]-countg(v)+1;
	return kth(r);
}
signed main(){
    ios::sync_with_stdio(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int opt,v;
		cin>>opt>>v;
		switch(opt){
			case 1:
				insert(v);
				break;
			case 2:
				remov(v);
				break;
			case 3:
				cout<<rnk(v)<<'\n';
				break;
			case 4:
				cout<<kth(v)<<'\n';
				break;
			case 5:
				cout<<pre(v)<<'\n';
				break;
			case 6:
				cout<<suc(v)<<'\n';
				break;
		}
	}
}
2020/12/16 16:58
加载中...