【CodeChef April Challenge 2014】Final Battle of Chef / 题解

【CodeChef  April Challenge 2014】Final Battle of Chef / 题解

题目描述

Chef declared war on Byteland. Chefs best scientist Pramod has designed a new Fighter Plane which can fly with Speed of Light!! So none of the defence forces of Byteland can defeat or defend it.

Byteland has a structure of a tree with $N$ cities connected by $N-1$ bidirectional roads. Each city has index between $[1,n]$ (inclusive) and no two cities have same index. The capital city of Byteland has index $1$. The distance between two cities is the number of roads in the path from one to other.

If the plane drops a bomb on a city $A$, with damage value $X$ then the damage done to a city $B$ will be $\lfloor \frac{X}{2^d}\rfloor$ where $d$ is the distance between $A$ and $B$, note that as the distance of $A$ from itself is $0$, the damage done to $A$ will be $\lfloor \frac{X}{2^0}\rfloor = X$.

Each city has a certain wealth $W_i$ in it, if it is damaged by a value of $X$ then its wealth is reduced by $X$. On a day if the wealth of a city becomes less than or equal to zero then it is considered Economically Dead.

Your task is to write a program that keeps track of the bombings done by the plane and answer the queries asked by the chef. The chef has a total of $Q$ queries for you. There are two types of queries.

  1. Chef gives you two integers $A$ and $X$, which means that the plane drops a bomb on the city with index $A$ with damage value $X$. A bomb can also be dropped on economically dead city.
  2. Chef gives you an integer $A$ and you need to print the number of cities that are economically dead which have $A$ in the path from the capital to them.
    (See explanation for better understanding)

Constraints

$1 \leq N \leq 10^5$

$1 \leq Q \leq 10^5$

$1 \leq X \leq 10^5$

$1 \leq W_i \leq 10^9$

思路

观察数据范围,发现每次修改的影响范围 $\log X$ 最大不超过 $15$,我们可以猜想算法复杂度和 $\log X$ 相关。

对于更新,考虑到一个子树内深度相同的点在 BFS 序上是连续的一段,我们可以在 BFS 序上建线段树,维护区间的权值最小值。对于每个受影响的深度,直接修改。

因为仍有 $\log X$ 个祖先是受影响的,在更新时应当注意把重复计算的权值消除。

对于查询,考虑一个子树内所有点在 DFS 序上是连续的一段,在 DFS 序上建树状数组,每次更新时遇到权值小于等于 $0$ 的新点就加入树状数组。

那么这道题就非常符合直觉地做完了。

代码

#include <bits/stdc++.h>
#define ll long long
#define inf 1e12 
using namespace std;
const int maxn=1e5+1;

int read(){
    int x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x;
}

vector<int>to[maxn];

int n,cnt;
int w[maxn],id[maxn],fa[maxn];
int t[maxn],L[maxn],R[maxn];

struct Fen_Tree{
    void add(int x){while(x<=n) t[x]++,x+=(x&-x);}
    int sum(int x){int r=0;while(x)r+=t[x],x-=(x&-x);return r;} 
}FT;

void pre(int u,int f){
    fa[u]=f;L[u]=++cnt;
    for (int i=0;i<to[u].size();++i){
        int v=to[u][i];
        if (v!=f) pre(v,u);
    }
    R[u]=cnt;
}

//---------------------------------------------------

struct Seg_Tree{
    #define ls (p<<1)
    #define rs (p<<1|1)
    #define mid ((l+r)>>1)
    ll t[maxn<<2],lazy[maxn<<2];

    void pushup(int p){
        t[p]=min(t[ls],t[rs]);
    }
    void pushdown(int p){
        t[ls]+=lazy[p],lazy[ls]+=lazy[p];
        t[rs]+=lazy[p],lazy[rs]+=lazy[p];
        lazy[p]=0;
    }
    void build(int l,int r,int p){
        if (l==r) return t[p]=w[id[l]],void();
        build(l,mid,ls),build(mid+1,r,rs);
        pushup(p);
    }
    void update(int l,int r,int L,int R,int v,int p){
        if (L<=l&&r<=R){t[p]+=v,lazy[p]+=v;return;}
        if (lazy[p]) pushdown(p);
        if (mid>=R) update(l,mid,L,R,v,ls);
        else if (mid<L) update(mid+1,r,L,R,v,rs);
        else update(l,mid,L,R,v,ls),update(mid+1,r,L,R,v,rs);
        pushup(p);
    }
    void putout(int l,int r,int p){
        if (l==r){FT.add(L[id[l]]),t[p]=inf;return;}
        if (lazy[p]) pushdown(p);
        if (t[ls]<=0) putout(l,mid,ls);
        if (t[rs]<=0) putout(mid+1,r,rs);
        pushup(p);
    }
}ST;

//---------------------------------------------------

int tim,tag[maxn],lb[maxn][16],rb[maxn][16];

void bfs(){
    queue<int>q;
    q.push(1);id[tag[1]=++tim]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        for (int i=0;i<to[u].size();++i){
            int v=to[u][i];
            if (tag[v]) continue;
            id[tag[v]=++tim]=v;
            q.push(v);
        }
    }
    for (int i=1;i<=n;++i)
        for (int j=0;j<=15;++j)
            lb[i][j]=1e7;
    for(int i=1;i<=n;i++){
        int t=i;
        for(int j=0;j<=15;j++){
            lb[t][j]=lb[t][j]>tag[i]?tag[i]:lb[t][j];
            rb[t][j]=rb[t][j]<tag[i]?tag[i]:rb[t][j];
            t=fa[t];
        }
    }
}

void apply(int u,int v){
    int pos=0;
    while(v&&rb[u][pos]){
        ST.update(1,n,lb[u][pos],rb[u][pos],v,1);
        v/=2,pos++;
    }
}

void change(int u,int v,int f){
    if (f) apply(f,v/2);
    apply(u,-v);
    if (fa[u]&&(v/2)) change(fa[u],v/2,u);
}

//---------------------------------------------------

int query(int u){
    ST.putout(1,n,1);
    return FT.sum(R[u])-FT.sum(L[u]-1);
}

int main(){
    freopen("pang.in","r",stdin);
    freopen("pang.out","w",stdout);
    n=read();
    for (int i=1;i<=n;++i)
    w[i]=read();
    for (int i=2;i<=n;++i){
        int u=read(),v=read();
        to[u].push_back(v);
        to[v].push_back(u);
    }
    pre(1,0);bfs();ST.build(1,n,1);
    for (int i=read();i;--i){
        int op=read(),u=read();
        if (op==1) change(u,read(),0);
        else printf("%d\n",query(u));
    }
}
Show Comments