直接树状数组维护就好了
AC_code #include<bits/stdc++.h> using namespace std; #define re register int #define ll long long const int N=1e6+5; int n,q,fa[N]; ll val[N]; int to[N],nxt[N],head[N],rp; void add_edg(int x,int y){ to[++rp]=y; nxt[rp]=head[x]; head[x]=rp; } int dfn[N],dfm[N],cnt,idf[N]; int dep[N]; void dfs(int x){ dfn[x]=++cnt; idf[cnt]=x; for(re i=head[x];i;i=nxt[i]){ int y=to[i]; dep[y]=dep[x]+1; dfs(y); } dfm[x]=cnt; } ll tr[N]; int lb(int x){return x&(-x);} void ins(int x,ll v){ for(re i=x;i<=n;i+=lb(i)) tr[i]+=v; } ll query(int x){ ll ret=0; for(re i=x;i;i-=lb(i)) ret+=tr[i]; return ret; } signed main(){ scanf("%d%d",&n,&q); for(re i=2;i<=n;i++){ scanf("%d%lld",&fa[i],&val[i]); add_edg(fa[i],i); } dfs(1); for(re i=2;i<=n;i++){ int tmp; if(dep[i]%2)tmp=-1; else tmp=1; ins(dfn[i],val[i]*tmp); ins(dfm[i]+1,-val[i]*tmp); } while(q--){ int typ; scanf("%d",&typ); if(typ==1){ int u,v; ll s; scanf("%d%d%lld",&u,&v,&s); ll tmpu=query(dfn[u]); ll tmpv=query(dfn[v]); if(dep[u]%2)tmpu=-tmpu; if(dep[v]%2)tmpv=-tmpv; if(dep[u]%2==dep[v]%2){ ll tmp=tmpu+tmpv-s; if(tmp%2)printf("none\n"); else if(dep[u]%2)printf("%lld\n",tmp/2); else if(dep[v]%2==0)printf("%lld\n",-tmp/2); } else{ ll tmp=tmpu+tmpv; if(tmp==s)printf("inf\n"); else printf("none\n"); } } else{ int u,tmp; ll w; scanf("%d%lld",&u,&w); if(dep[u]%2)tmp=-1; else tmp=1; ins(dfn[u],-val[u]*tmp); ins(dfm[u]+1,val[u]*tmp); val[u]=w; ins(dfn[u],val[u]*tmp); ins(dfm[u]+1,-val[u]*tmp); } } } T3 Rectangle所以我因为这个题错过了A层？？？？
其实挺伤心的，自己改题总是特别慢，而且思路还总是有偏差
就这个题一开始我想偏了好多，
我用当前的树状数组去更新前面的，而题解是直接将前面的赋值过来
我也是吐了啊，真的很是无奈，最后迫不得已只能去看代码
总而言之就是代码能力过于弱了
这个就是一个用树状数组优化的枚举题；
你发现只有在边界上有点的时候这个正方形才是合法的，
那么我们假装每一列只有一个点，那么我们就可以固定这个点
从这个点向前枚举前面每一列的点，我们如果想用这两列作为矩形的边界
这两个点必须要选上，我们只需要找到那些y特别大特别小的就好了
直接把每个矩形都组合出来