社区讨论

关于我遇到的玄学问题

学术版参与者 5已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@mi7eryie
此快照首次捕获于
2025/11/20 20:29
3 个月前
此快照最后确认于
2025/11/20 23:58
3 个月前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
long long read(){
	int f=1,c=getchar();
	while(!('0'<=c&&c<='9')){
		if(c=='-')f=-1;
		c=getchar();
	}
	long long ans=0;
	while('0'<=c&&c<='9'){
		ans=ans*10+c-'0';
		c=getchar();
	}
	return ans*f;
}
const int N=1e5+20,N4=4*N;
const long long V=1e18+20;
long long sum[N],mi[N],a[N];
struct NODE{
	pair<long long,int>mx;
	int ls,rs;
	NODE(long long b,int c,int l,int r){
		mx.first=b,mx.second=c;ls=l;rs=r;
	}
};

struct seg_tree{
	vector<NODE>t;
	seg_tree(){
		t.push_back(NODE(LONG_LONG_MIN,0,0,0));
		t.push_back(NODE(LONG_LONG_MIN,0,0,0));
	}
	int cnt=1;
	void clear(){
		cnt=1;
		t.clear();
		t.shrink_to_fit();
		t.push_back(NODE(LONG_LONG_MIN,0,0,0));
		t.push_back(NODE(LONG_LONG_MIN,0,0,0));
	}
	void newnode(int &p){
		if(p!=0)return;
		cnt++;
		t.push_back(NODE(LONG_LONG_MIN,0,0,0));
		p=cnt;
	}
	
	void pushup(int p){
		t[p].mx=max(t[t[p].ls].mx,t[t[p].rs].mx);
	}
	pair<long long,int> ask(int p,long long l,long long r,long long L,long long R){
//		cout<<p<<" "<<l<<" "<<r<<"-\n";
		if(p==0)return {LONG_LONG_MIN,0};
		if(L<=l&&r<=R)return t[p].mx;
		long long mid=(l+r)>>1;
		pair<long long,int>mx={LONG_LONG_MIN,0};
		if(L<=mid)mx=max(mx,ask(t[p].ls,l,mid,L,R));
		if(mid+1<=R)mx=max(mx,ask(t[p].rs,mid+1,r,L,R));
		return mx;
	}
	void add(int p,long long l,long long r,long long x,pair<long long,int> val){
//		cout<<p<<" "<<l<<" "<<r<<"\n";
		if(l==r){
			t[p].mx=val;
			return;
		}
		long long mid=(l+r)>>1;
		if(x<=mid){
			newnode(t[p].ls);
			add(t[p].ls,l,mid,x,val);
		}
		else{
			newnode(t[p].rs);
			add(t[p].rs,mid+1,r,x,val);
		}
		pushup(p);
	}
}T;

signed main(){
	
	T.add(1,0,V,0,{1,1});
	T.add(1,0,V,1,{2,2});
	
	cout<<T.ask(1,0,V,0,1).second;
	return 0;
}

这是一个动态开点线段树
新建节点时有可能什么都没干
具体表现可以将代码中的输出解注释
window 10:C++14 O2
求问大佬

回复

6 条回复,欢迎继续交流。

正在加载回复...