社区讨论
求助 92pts T了两个点
P3919【模板】可持久化线段树 1(可持久化数组)参与者 2已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @lobgfh66
- 此快照首次捕获于
- 2023/10/29 20:35 2 年前
- 此快照最后确认于
- 2023/11/04 02:00 2 年前
JAVASCRIPT
"use strict";
const inpStr=new Int8Array(require('fs').readFileSync('/dev/stdin'));
const inpLen=inpStr.length;
let inpPtr=0;
function getNum(){
let x=0,f=1;
while(inpPtr<inpLen&&(inpStr[inpPtr]<48||inpStr[inpPtr]>57)){
if(inpStr[inpPtr]==45)f=-1;
inpPtr++;
}
if(inpPtr>=inpLen)return NaN;
while(inpPtr<inpLen&&inpStr[inpPtr]>=48&&inpStr[inpPtr]<=57){
x=x*10+inpStr[inpPtr]-48;
inpPtr++;
}
return x*f;
}
const MAXM=1000000;
let n=0,m=0,vr=0,op=0,loc=0,vl=0;
const SIZ=(1<<21|9)+MAXM*21;
let lch=new Int32Array(SIZ+10);
let rch=new Int32Array(SIZ+10);
let num=new Int32Array(SIZ+10);
let totSeg=0;
function newSeg(idx){
totSeg++;
if(idx!==undefined){
lch[totSeg]=lch[idx];
rch[totSeg]=rch[idx];
num[totSeg]=num[idx];
}
return totSeg;
}
let verRt=new Int32Array(MAXM+10);
let totVer=0;
function newVer(old,cop){
totVer++;
if(!cop)verRt[totVer]=verRt[old];
else verRt[totVer]=newSeg(verRt[old]);
}
function _build_(rt,l,r){
if(l==r){
num[rt]=getNum();
return;
}
let mid=(l+r)>>1;
lch[rt]=newSeg();
_build_(lch[rt],l,mid);
rch[rt]=newSeg();
_build_(rch[rt],mid+1,r);
}
function build(){
verRt[0]=newSeg();
_build_(verRt[0],1,n);
}
function _posChn_(rt,l,r,pos,val){
if(l==r){
num[rt]=val;
return;
}
let mid=(l+r)>>1;
if(pos<=mid){
lch[rt]=newSeg(lch[rt]);
_posChn_(lch[rt],l,mid,pos,val);
}
else{
rch[rt]=newSeg(rch[rt]);
_posChn_(rch[rt],mid+1,r,pos,val);
}
}
function posChn(ver,pos,val){
newVer(ver,true);
_posChn_(verRt[totVer],1,n,pos,val);
}
function _posVal_(rt,l,r,pos){
if(l==r)return num[rt];
let mid=(l+r)>>1;
if(pos<=mid)return _posVal_(lch[rt],l,mid,pos);
else return _posVal_(rch[rt],mid+1,r,pos);
}
function posVal(ver,pos){
newVer(ver,false);
return _posVal_(verRt[totVer],1,n,pos);
}
function main(){
n=getNum(),m=getNum();
build();
while(m--){
vr=getNum(),op=getNum(),loc=getNum();
if(op==1){
vl=getNum();
posChn(vr,loc,vl);
}
else console.log(posVal(vr,loc));
}
}
main();
回复
共 4 条回复,欢迎继续交流。
正在加载回复...