在长宽1e5级的时候,类似于本题的操作就必须在y方向动态开点了...
然而本蒟蒻动态开点在如何单点修改后递归更新信息的地方出现了问题qwq
我想到的方法是开个map记录编号为i的树纵坐标为y的叶子结点的编号
大概就是:
void change(int line,int &k,int l,int r,int p,int v,int flag=0){
if(!k){
k=New();
if(l==r) mp[line][p]=k;
}
这样做只在叶子用一次map,似乎并不会影响渐进复杂度的正确性
在本题也以520ms的时间顺利通过了
但是我在别的地方交类似题目时却T掉了qwq
删掉更新那句就可以跑完,所以应该可以确定是这个更新的问题
但我不理解啊qwq
希望大佬指点迷津awa
如果在这个地方有更加优美的实现方法,也请赐教!OvO
修改部分的代码:
void change(int line,int &k,int l,int r,int p,int v,int flag=0){
if(!k){
k=New();
if(l==r) mp[line][p]=k;
}
if(l==r){
if(flag==0) tr[k].mx=tr[k].mn=v;
else{//从x方向的左右儿子更新答案
int L=mp[line<<1][p],R=mp[line<<1|1][p];
tr[k].mx=max(tr[L].mx,tr[R].mx);
tr[k].mn=min(tr[L].mn,tr[R].mn);
}
return;
}
if(p<=mid) change(line,tr[k].ls,l,mid,p,v,flag);
else change(line,tr[k].rs,mid+1,r,p,v,flag);
pushup(k);
return;
}
void Add(int k,int l,int r,int x,int y,int v){
if(l==r){
change(k,rt[k],1,n,y,v,0);
return;
}
if(x<=mid) Add(k<<1,l,mid,x,y,v);
else Add(k<<1|1,mid+1,r,x,y,v);
change(k,rt[k],1,n,y,v,1);//把这句删掉就不T了
return;
}