Aragorn’s Story (树链剖分模板-点权区间修改)

熟练剖分:https://zhuanlan.zhihu.com/p/41082337

题目链接:https://cn.vjudge.net/contest/279350#problem/A

题目大意:一个树状图,要求实现点 x – y 的加减与求和操作。树链剖分模板题。

代码

 

#include <iostream>
#include <bits/stdc++.h>

#define lson o<<1
#define rson o<<1|1
#define Mid int m=(l+r)/2

using namespace std;

const int maxn=5e4+10;
const int inf=0x3f3f3f3f;

struct node
{
    int sum,lazy,cnt;
} tree[maxn<<2];

vector<int>edge[maxn];
int data[maxn],n,m,p;
char str[112];
int id_data[maxn],fa[maxn],son[maxn],siz[maxn],deep[maxn],top[maxn],tid[maxn];
int cnt,sum;

void init()
{
    for(int i=1; i<=n; i++)
    {
        cin>>data[i];
        edge[i].clear();
    }
    for(int i=1; i<n; i++)
    {
        int u,v;
        cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
}

/*
    第一遍dfs
    获得每个节点的重儿子,重量,父亲节点,深度
*/

void dfs(int u,int f,int d)//当前节点/父亲节点/深度
{
    siz[u]=1;
    deep[u]=d;
    fa[u]=f;
    son[u]=-1;
    for(int i=0; i<edge[u].size(); i++)
    {
        int v=edge[u][i];
        if(v!=f)
        {
            dfs(v,u,d+1);
            siz[u]+=siz[v];
            if(son[u]==-1||siz[son[u]]<siz[v])
            {
                son[u]=v;
            }
        }
    }
}

/*
    第二遍dfs
    对节点进行重新编号并将原有权值哈希到新的编号上
*/
void dfss(int u,int t)
{
    top[u]=t;
    tid[u]=cnt;
    id_data[cnt++]=data[u];
    if(son[u]!=-1)
        dfss(son[u],t);
    for(int i=0; i<edge[u].size(); i++)
    {
        int v=edge[u][i];
        if(son[u]!=v&&fa[u]!=v)
            dfss(v,v);
    }
}

void split()
{
    cnt=1;
    dfs(1,-1,0);
    dfss(1,1);
}

void push_down(int o)
{
    if(!tree[o].lazy)
        return;
    int lazy=tree[o].lazy;
    tree[lson].lazy+=lazy;
    tree[rson].lazy+=lazy;
    tree[lson].sum+=lazy*tree[lson].cnt;
    tree[rson].sum+=lazy*tree[rson].cnt;
    tree[o].lazy=0;
}

void build(int o,int l,int r)
{
    tree[o].lazy=0;
    if(l==r)
    {
        tree[o].sum=id_data[l];
        tree[o].cnt=1;
        return;
    }
    Mid;
    build(lson,l,m);
    build(rson,m+1,r);
    tree[o].sum=tree[lson].sum+tree[rson].sum;
}

void query(int o,int l,int r,int pos)
{
    if(l==r)
    {
        sum+=tree[o].sum;
        return;
    }
    push_down(o);
    Mid;
    if(pos<=m)query(lson,l,m,pos);
    else query(rson,m+1,r,pos);
}

void updata(int o,int l,int r,int ul,int ur,int d)
{
    if(r<ul||ur<l)
        return;
    if(ul<=l&&r<=ur)
    {
        tree[o].sum+=tree[o].cnt*d;
        tree[o].lazy+=d;
        return;
    }
    push_down(o);
    Mid;
    updata(lson,l,m,ul,ur,d);
    updata(rson,m+1,r,ul,ur,d);
    tree[o].sum=tree[lson].sum+tree[rson].sum;
}

void Updata(int x,int y,int d)
{
    int tx=top[x],ty=top[y];
    while(tx!=ty)
    {
        if(deep[tx]<deep[ty])
        {
            swap(x,y);
            swap(tx,ty);
        }
        updata(1,1,n,tid[tx],tid[x],d);
        x=fa[tx];
        tx=top[x];
    }
    if(deep[x]<deep[y])
        swap(x,y);
    updata(1,1,n,tid[y],tid[x],d);
}

void solve()
{
    split();
    build(1,1,n);
    while(p--)
    {
        int a,b,c;
        cin>>str;
        if(str[0]=='Q')
        {
            cin>>a;
            sum=0;
            query(1,1,n,tid[a]);
            cout<<sum<<endl;
        }
        else
        {
            cin>>a>>b>>c;
            if(str[0]=='I')
                Updata(a,b,c);
            else
                Updata(a,b,-c);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>m>>p)
    {
        init();
        solve();
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注