社区讨论
关于我遇到的玄学问题
学术版参与者 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 条回复,欢迎继续交流。
正在加载回复...