33分线段树,MLE
查看原帖
33分线段树,MLE
754444
tamamocross楼主2024/1/28 17:06
#include<iostream>
using namespace std;
const int Max=1e6+1;
struct node{
	int l,r;
	int sum;
	node(){
		sum=0;
	}
};
int tot;
node tree[4*Max];
void Build(int p,int l,int r){
	tree[p].sum=r-l+1;tree[p].l=l,tree[p].r=r;
	if(l==r){
		return;
	}
	int mid=(l+r)/2;
	Build(2*p,l,mid);
	Build(2*p+1,mid+1,r);
}
node& query(int p,int l,int r){
	//cout<<l<<" "<<tree[p].l<<" "<<tree[p].r<<" "<<r<<endl;
	if(l<=tree[p].l&&tree[p].r<=r){
		return tree[p];
	}
	int mid=(tree[p].l+tree[p].r)/2;
	node* tmp=new node;
	if(l<=mid){
		tmp->sum+=query(2*p,l,r).sum;
	}
	if(r>=mid+1){
		tmp->sum+=query(2*p+1,l,r).sum;
	}
	return *tmp;
}
void change(int p,int num){
	if(tree[p].l==tree[p].r){
		tree[p].sum=0;
		return;
	}
	int mid=(tree[p].l+tree[p].r)/2;
	if(num<=mid){
		change(2*p,num);
	}else{
		change(2*p+1,num);
	}
	tree[p].sum=tree[2*p].sum+tree[2*p+1].sum;
}

int main(){
	int n,m;
	cin>>n>>m;
	Build(1,0,n);change(1,0);
	int len=n;
	int p=0;
	while(len!=1){
	//	cout<<len<<endl;
		int cnt=m;
		int lef=query(1,p+1,n).sum;
	//	cout<<1;
		if(cnt<=lef){
			int l=p,r=n;
			while(l!=r){
		//		cout<<l<<" "<<r<<endl;
				int mid=(l+r+1)/2;
				if(query(1,p+1,mid).sum>=cnt){
					r=mid-1;
				}else{
					l=mid;
				}
				
			}
			p=l+1;
			change(1,p);
		}else{
			cnt-=lef;
			cnt%=len;
			if(cnt==0){
				cnt=len;
			}
			int l=0,r=n;
			while(l!=r){
				int mid=(l+r+1)/2;
				if(query(1,0,mid).sum>=cnt){
					r=mid-1;
				}else{
					l=mid;
				}
			}
			p=l+1;
			change(1,p);
		}
	//	cout<<p<<endl;
		len--;
	}
	for(int i=1;i<=n;i++){
		if(query(1,i,i).sum==1){
			cout<<i;
			return 0;
		}
	}
} 
//999999 999999
2024/1/28 17:06
加载中...