一个大大的疑问!!紧急求助!!!
查看原帖
一个大大的疑问!!紧急求助!!!
494699
卷王慢即快楼主2022/5/2 11:12

为什么我改一下+1-1的位置就MLE 和 WA了??

//AC代码,勿抄袭
#include<iostream>
using namespace std;
struct node {
	int left,right,size,value,num;
	node(int l,int r,int s,int v):
	left(l),right(r),size(s),value(v),num(1){}
	node(){}
}t[10001];
int cnt=0,root=0;
inline void update(int root)
{
	t[root].size=t[t[root].left].size+t[t[root].right].size+t[root].num;
}
inline int rk(int x,int root)
{
	if(root)
	{
		if(x<t[root].value) return rk(x,t[root].left);
		if(x>t[root].value)
		return rk(x,t[root].right)+t[root].num+t[t[root].left].size;
		return t[t[root].left].size+t[root].num;
	}
	return 1;
}
inline int kth(int x,int root)
{
	if(x<=t[t[root].left].size) return kth(x,t[root].left);
	if(x<=t[t[root].left].size+t[root].num) return t[root].value;
	return kth(x-t[t[root].left].size-t[root].num,t[root].right);
}
inline void insert(int x,int &root)
{
	if(x<t[root].value)
	{
		if(!t[root].left) t[t[root].left=++cnt]=node(0,0,1,x);
		else insert(x,t[root].left);
	}
	else if(x>t[root].value)
	{
		if(!t[root].right) t[t[root].right=++cnt]=node(0,0,1,x);
		else insert(x,t[root].right);
	}
	else t[root].num++;
	update(root);
}
int main()
{
	int n;
	cin>>n;
	t[root=++cnt]=node(0,0,1,2147483647);
	for(int i=1;i<=n;i++)
	{
		int x,y;
		cin>>y>>x;
		if(y==5) insert(x,root);
		if(y==1) cout<<rk(x,root)<<endl;
		if(y==2) cout<<kth(x,root)<<endl;
		if(y==3) cout<<kth(rk(x,root)-1,root)<<endl;
		if(y==4) cout<<kth(rk(x+1,root),root)<<endl;
	}
	return 0;
}
//WA、MLE代码,可抄袭QWQ
#include<iostream>
using namespace std;
struct node {
	int left,right,size,value,num;
	node(int l,int r,int s,int v):
	left(l),right(r),size(s),value(v),num(1){}
	node(){}
}t[10001];
int cnt=0,root=0;
inline void update(int root)
{
	t[root].size=t[t[root].left].size+t[t[root].right].size+t[root].num;
}
inline int rk(int x,int root)
{
	if(root)
	{
		if(x<t[root].value) return rk(x,t[root].left);
		if(x>t[root].value)
		return rk(x,t[root].right)+t[root].num+t[t[root].left].size;
		return t[t[root].left].size+t[root].num;
	}
	return 1;
}
inline int kth(int x,int root)
{
	if(x<=t[t[root].left].size) return kth(x,t[root].left);
	if(x<=t[t[root].left].size+t[root].num) return t[root].value;
	return kth(x-t[t[root].left].size-t[root].num,t[root].right);
}
inline void insert(int x,int &root)
{
	if(x<t[root].value)
	{
		if(!t[root].left) t[t[root].left=++cnt]=node(0,0,1,x);
		else insert(x,t[root].left);
	}
	else if(x>t[root].value)
	{
		if(!t[root].right) t[t[root].right=++cnt]=node(0,0,1,x);
		else insert(x,t[root].right);
	}
	else t[root].num++;
	update(root);
}
int main()
{
	int n;
	cin>>n;
	t[root=++cnt]=node(0,0,1,2147483647);
	for(int i=1;i<=n;i++)
	{
		int x,y;
		cin>>y>>x;
		if(y==5) insert(x,root);
		if(y==1) cout<<rk(x,root)<<endl;
		if(y==2) cout<<kth(x,root)<<endl;
		if(y==3) cout<<kth(rk(x-1,root),root)<<endl;
		if(y==4) cout<<kth(rk(x,root)+1,root)<<endl;
	}
	return 0;
}

谁能帮帮我?

2022/5/2 11:12
加载中...