包含不小于$\sqrt n$列的只有不大于$\sqrt n$行，修改时这些行打标记，否则暴力更新，操作一列的时候暴力更新这些行。合并没啥影响直接搞就是了。更新需要访问位置，感觉必须用哈希表，并不是特别靠谱。平均复杂度$O(n\sqrt n)$。

#include
#include
#include
using namespace std;
using namespace __gnu_pbds;
int n2;
inline void upd2(int&a,int b){
aw;
vec(){s=d=0;}
void ins(int i,int e){
auto j=w.find(i);
if(w.end()==j)w[i]=e-d;
else
upd2(j->second,e-d);
upd2(s,e);
}
};
gp_hash_tablef[2];
gp_hash_tableg[2];
gp_hash_tableh[2];
void dev(int k,int x){
auto&a=f[k][x];
for(int y:h[k^1]){
auto&b=f[k^1][y];
auto i=b.w.find(x);
if(b.w.end()!=i)
a.ins(y,i->second+b.d);
}
}
int sol5(int k,int x){
if(h[k].end()==h[k].find(x))
dev(k,x);
return f[k][x].s;
}
int ask(int k,int x){
return g[k].end()!=g[k].find(x)?sol5(k,g[k][x]):0;
}
void inc(int k,int x,int d){
auto&a=f[k][x];
if(h[k].end()==h[k].find(x)){
dev(k,x);
for(auto&e:a.w){
e.second+=d;
f[k^1][e.first].ins(x,e.second);
}
}else{
a.d+=d;
for(int y:h[k^1]){
auto&b=f[k^1][y];
auto i=b.w.find(x);
if(b.w.end()!=i){
i->second+=d;
upd2(b.s,i->second+b.d);
}
}
}
a.s+=d;
}
void sol4(int k,int x,int nx){
g[k][nx]=g[k][x];
g[k].erase(x);
}
void sol3(int k,int x,int nx){
auto&a=f[k][x],&b=f[k][nx];
if(h[k].end()==h[k].find(x))
dev(k,x);
for(auto e:a.w){
auto&c=f[k^1][e.first];
upd2(c.w[nx],e.second+a.d-c.d);
c.w.erase(x);
b.ins(e.first,e.second+a.d);
}
if(h[k].erase(x)||b.w.size()>n2){
h[k].insert(nx);
dev(k,nx);
}
}
void sol2(int k,int x,int nx){
sol3(k,g[k][x],g[k][nx]);
g[k].erase(x);
}
void sol1(int k,int x,int nx){
if(f[k][g[k][x]].w.size()<=f[k][g[k][nx]].w.size()) sol2(k,x,nx); else{ sol2(k,nx,x); sol4(k,x,nx); } } void mov(int k,int x,int nx){ if(x!=nx) (g[k].end()!=g[k].find(nx)?sol1:sol4)(k,x,nx); } int main(){ int n,m,x,y,d; char o[8]; scanf("%d",&n); n2=sqrt(n+.5); while(n--){ scanf("%d%d%d",&x,&y,&d); f[0][x].ins(y,d); f[1][y].ins(x,d); g[0][x]=x; g[1][y]=y; } for(int k=0;k<2;++k) for(auto&e:f[k]) if(e.second.w.size()>n2)
h[k].insert(e.first);
scanf("%d",&m);
while(m--){
scanf("%s%d",o,&x);
int k=*o=='Y';
if(o[1]=='Q')
printf("%d\n",ask(k,x));
else{
scanf("%d",&d);
if(g[k].end()!=g[k].find(x))
o[1]=='M'?mov(k,x,x+d):inc(k,g[k][x],d);
}
}
}