熟练剖分

不想写树剖怎么办QwQ

维护每个点\(Ans\)

操作\(1\)就是子树加

操作\(2\)是操作\(1\)的叠加......

认真分析......

子树加\(dep\)!!!

写个树状数组节省一下码量

(节省了还是100+)

(我选择死亡)

#include 
    
     const int MAXN=100111;int N, M;int X;long long op;long long Ans;struct Vert{    int FE;    int Dps, Dpr;    int Dep;    long long Val, Sum;} V[MAXN];struct Edge{    int x, y, next;} E[MAXN<<1];int Ecnt;void addE(int a, int b){    ++Ecnt;    E[Ecnt].x=a;E[Ecnt].y=b;E[Ecnt].next=V[a].FE;V[a].FE=Ecnt;}int Dfn[MAXN], DFN;void DFS(int at, int f=0){    ++DFN;    Dfn[DFN]=at;    V[at].Dps=DFN;    for(int k=V[at].FE, to;k>0;k=E[k].next){        to=E[k].y;        if(to==f)   continue;        V[to].Dep=V[at].Dep+1;        V[to].Sum=V[at].Sum+V[to].Val;        DFS(to, at);    }    V[at].Dpr=DFN;}int lowbit(int a){    return a&(-a);}struct Trray{    int L;    long long n[MAXN];    void init(int l){        L=l;        for(int i=0;i
     
      0;i-=lowbit(i))            ret+=n[i];        return ret;    }    void Update(int l, int r, long long d){        for(int i=l;i<=L;i+=lowbit(i))      n[i]+=d;        for(int i=r+1;i<=L;i+=lowbit(i))    n[i]-=d;    }} Cv, Cd;int main(){        scanf("%d%d", &N, &M);        for(int i=1;i<=N;++i)   scanf("%lld", &V[i].Val);        for(int i=1, a, b;i