POJ 3237树链剖分(二)
mid=(tree[i].l+tree[i].r)>>1; if(pos<=mid)update1(2*i,pos,val); else update1(2*i+1,pos,val); pushup(i); } void negval(int i,int l,int r) { if(tree[i].l>=l&&tree[i].r<=r) { tree[i].max=-tree[i].max; tree[i].min=-tree[i].min; swap(tree[i].max,tree[i].min); tree[i].neg^=1; return; } pushdown(i); int mid=(tree[i].l+tree[i].r)>>1; if(l<=mid)negval(2*i,l,r); if(r>mid)negval(2*i+1,l,r); pushup(i); } int query(int i,int l,int r) { if(tree[i].l>=l&&tree[i].r<=r)return tree[i].max; pushdown(i); int mid=(tree[i].l+tree[i].r)>>1; int ans=-inf; if(l<=mid)ans=max(ans,query(2*i,l,r)); if(r>mid)ans=max(ans,query(2*i+1,l,r)); pushup(i); return ans; } int findmax(int u,int v) { int f1=top[u],f2=top[v]; int tmp=-inf; while(f1!=f2) { if(deep[f1]
deep[v])swap(u,v); return max(tmp,query(1,p[son[u]],p[v])); } void neg(int u,int v) { int f1=top[u],f2=top[v]; while(f1!=f2) { if(deep[f1]
deep[v])swap(u,v); negval(1,p[son[u]],p[v]); } int e[maxn][3]; int main() { // freopen("tree.in","r",stdin); // freopen("data.out","w",stdout); int T,n; scanf("%d",&T); while(T--) { init(); scanf("%d",&n); for(int i=0;i
deep[e[i][1]]) swap(e[i][0],e[i][1]); update1(1,p[e[i][1]],e[i][2]); } char op[10]; int u,v; while(~scanf("%s",op)) { if(op[0]=='D')break; scanf("%d%d",&u,&v); if(op[0]=='Q') printf("%d\n",findmax(u,v)); else if(op[0]=='C') update1(1,p[e[u-1][1]],v); else neg(u,v); } } return 0; }