Submission #642652

#	Time	Username	Problem	Language	Result	Execution time	Memory
642652		Tenis0206	Arboras (RMI20_arboras)	C++11	100 / 100	275 ms	36988 KiB

arboras

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int Mod = 1e9 + 7;

struct aint
{
    int ai[500005],lazy[500005];
    void propag(int nod, int a, int b)
    {
        if(lazy[nod]==0)
        {
            return;
        }
        int mij = (a + b) >> 1;
        ai[nod*2] += lazy[nod] * (mij - a + 1);
        ai[nod*2+1] += lazy[nod] * (b - mij);
        lazy[nod*2] += lazy[nod];
        lazy[nod*2+1] += lazy[nod];
        lazy[nod] = 0;
    }
    void update(int ua, int ub, int val, int nod, int a, int b)
    {
        if(ua<=a && ub>=b)
        {
            ai[nod] += val * (b - a + 1);
            lazy[nod] += val;
            return;
        }
        propag(nod,a,b);
        int mij = (a + b) >> 1;
        if(ua<=mij)
        {
            update(ua,ub,val,nod*2,a,mij);
        }
        if(ub>mij)
        {
            update(ua,ub,val,nod*2+1,mij+1,b);
        }
        ai[nod] = ai[nod*2] + ai[nod*2+1];
    }
    int query(int poz, int nod, int a, int b)
    {
        if(a==b)
        {
            return ai[nod];
        }
        propag(nod,a,b);
        int mij = (a + b) >> 1;
        if(poz<=mij)
        {
            return query(poz,nod*2,a,mij);
        }
        return query(poz,nod*2+1,mij+1,b);
    }
};

aint ai,ai2;

int n,q;

int w[100005],Mx[100005];
int l[100005],t[100005],c[100005],poz[100005],lvl[100005];

int cnt = 0, paths = 1;

int d[100005];

pair<int,int> Max[100005],Max2[100005];

vector<int> G[100005];

set<pair<int,int>,greater<pair<int,int>>>s[100005];

vector<int> se;

void get_w(int nod, int dad = 0)
{
    w[nod] = 1;
    for(auto it : G[nod])
    {
        if(it==dad)
        {
            continue;
        }
        get_w(it,nod);
        w[nod] += w[it];
        if(w[it] > w[Mx[nod]])
        {
            Mx[nod] = it;
        }
    }
}

void get_paths(int nod, int dad = 0, int level = 1)
{
    poz[nod] = (++cnt);
    l[nod] = paths;
    lvl[nod] = level;
    t[nod] = dad;
    if(G[nod].size()==1 && nod!=1)
    {
        return;
    }
    get_paths(Mx[nod],nod,level+1);
    for(auto it : G[nod])
    {
        if(it==dad || it==Mx[nod])
        {
            continue;
        }
        ++paths;
        c[paths] = it;
        get_paths(it,nod,level+1);
    }
}

void dfs(int nod, int dad = 0)
{
    for(auto it : G[nod])
    {
        if(it==dad)
        {
            continue;
        }
        dfs(it,nod);
        if(Max[it].first + d[it] > Max[nod].first)
        {
            Max2[nod] = Max[nod];
            Max[nod].first = Max[it].first + d[it];
            Max[nod].second = it;
        }
        else if(Max[it].first + d[it] > Max2[nod].first)
        {
            Max2[nod].first = Max[it].first + d[it];
            Max2[nod].second = it;
        }
    }
    for(auto it : G[nod])
    {
        if(it==dad || it==Max[nod].second)
        {
            continue;
        }
        se.push_back(it);
    }
}

void add_se(int nod)
{
    s[l[nod]].insert({lvl[nod],nod});
}

void remove_se(int nod)
{
    auto it = s[l[nod]].lower_bound({lvl[nod],nod});
    s[l[nod]].erase(it);
}

int find_next_se(int nod)
{
    while(nod)
    {
        auto it = s[l[nod]].lower_bound({lvl[nod],nod});
        if(it!=s[l[nod]].end())
        {
            return it->second;
        }
        nod = t[c[l[nod]]];
    }
    return 1;
}

void update_arb(int x, int y, int val)
{
    if(lvl[x] > lvl[y])
    {
        return;
    }
    while(l[x]!=l[y])
    {
        ai.update(poz[c[l[y]]],poz[y],+val,1,1,n);
        y = t[c[l[y]]];
    }
    ai.update(poz[x],poz[y],+val,1,1,n);
}

void update(int nod, int val)
{
    while(nod!=1)
    {
        int anc = find_next_se(nod);
        update_arb(anc,t[nod],+val);
        nod = anc;
        if(nod==1)
        {
            break;
        }
        int cnd = ai.query(poz[nod],1,1,n) + d[nod];
        int dad = t[nod];
        int Maxdad = ai.query(poz[dad],1,1,n);
        int Max2dad = ai2.query(poz[dad],1,1,n);
        if(cnd <= Max2dad)
        {
            break;
        }
        if(cnd > Maxdad)
        {
            remove_se(nod);
            add_se(Max[dad].second);
            ai2.update(poz[dad],poz[dad],Maxdad-Max2dad,1,1,n);
            Max2[dad].second = Max[dad].second;
            ai.update(poz[dad],poz[dad],cnd-Maxdad,1,1,n);
            Max[dad].second = nod;
            val = cnd - Maxdad;
            nod = dad;
        }
        else if(cnd > Max2dad)
        {
            Max2[dad].second = nod;
            ai2.update(poz[dad],poz[dad],cnd-Max2dad,1,1,n);
            break;
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
  //  freopen("nr.in","r",stdin);
  //  freopen("nr.out","w",stdout);
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        int t;
        cin>>t;
        ++t;
        G[i].push_back(t);
        G[t].push_back(i);
    }
    for(int i=2;i<=n;i++)
    {
        cin>>d[i];
    }
    dfs(1);
    get_w(1);
    c[1] = 1;
    get_paths(1);
    for(auto it : se)
    {
        add_se(it);
    }
    for(int i=1;i<=n;i++)
    {
        ai.update(poz[i],poz[i],Max[i].first,1,1,n);
        ai2.update(poz[i],poz[i],Max2[i].first,1,1,n);
    }
    cout<<(ai.ai[1] + ai2.ai[1]) % Mod<<'\n';
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        int nod,val;
        cin>>nod>>val;
        ++nod;
        d[nod] += val;
        update(nod,val);
        cout<<(ai.ai[1] + ai2.ai[1]) % Mod<<'\n';
    }
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 31 / 31
• Subtask 4: 45 / 45