JLOI2015 城池攻占

题目

可以发现：由于只有加乘两种变化，并且乘的数是正的，那么占领同一城池的骑士，占领前和占领后战斗力相对大小是不变的 。

那么可以用左偏树维护战斗力从小到大的顺序，占领到同一城池的骑士。

显然每次考虑占领到这个城池的骑士时，要先考虑它管辖的城池的的骑士（DFS）。

之后得到了这些骑士战斗力构成的左偏树，每次找到战斗力最小值（直接找），如果战斗力不够就删除，表示它们失败了。

然后其它点就占领了这个城池。

打上修改战斗力的标记以后，把这棵左偏树合并到管辖它的城池上去，表示它们到达了管辖它们的城池。

合并次数$O(n)$，加入，删除次数$O(m)$，单次复杂度$O(\log n)$，总复杂度$O((n+m)\log n)$

当然由于这题管辖i的城池j一定满足j<i，那么可以直接从n到1考虑。

/*
Author: CNYALI_LK
LANG: C++
PROG: 3261.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
    ll s=0,base=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')base=-base;
    while(isdigit(c)){s=s*10+(c^48);c=getchar();}
    return s*base;
}
ll w[333333],l[333333],r[333333],add_tag[333333],mul_tag[333333],rlink[333333],fa[333333],a[333333],v[333333],in[333333];
ll h[333333],die[333333],dis[333333],root[333333],dsum[333333];
void put_add(ll x,ll y){add_tag[x]+=y;w[x]+=y;}
void put_mul(ll x,ll y){add_tag[x]*=y;w[x]*=y;mul_tag[x]*=y;}
void push_tag(ll x){
    put_mul(l[x],mul_tag[x]);
    put_mul(r[x],mul_tag[x]);
    put_add(l[x],add_tag[x]);
    put_add(r[x],add_tag[x]);
    add_tag[x]=0;
    mul_tag[x]=1;
}
ll merge(ll x,ll y){
    if(!x)return y;
    if(!y)return x;
    push_tag(x);
    push_tag(y);
    if(w[x]>w[y])swap(x,y);
    r[x]=merge(r[x],y);
    if(rlink[r[x]]>rlink[l[x]])swap(l[x],r[x]);
    rlink[x]=rlink[r[x]]+1;
    return x;
}
void remove(ll &x){
    push_tag(x);
    x=merge(l[x],r[x]);
}

int main(){
#ifdef cnyali_lk
    freopen("3261.in","r",stdin);
    freopen("3261.out","w",stdout);
#endif
    ll n,m;
    n=read();
    m=read();
    for(ll i=1;i<=n;++i)h[i]=read();
    dis[0]=-1;
    for(ll i=2;i<=n;++i){fa[i]=read(),a[i]=read(),v[i]=read();dis[i]=dis[fa[i]]+1;}
    for(ll i=1;i<=m;++i){mul_tag[i]=1;w[i]=read();in[i]=read();root[in[i]]=merge(root[in[i]],i);}
    for(ll i=n;i;--i){
        while(root[i]&&w[root[i]]<h[i]){
            die[root[i]]=i;
            remove(root[i]);
            ++dsum[i];
        }   
        if(a[i])put_mul(root[i],v[i]);
        else put_add(root[i],v[i]);
        root[fa[i]]=merge(root[fa[i]],root[i]);
    }
    for(ll i=1;i<=n;++i)printf("%lld\n",dsum[i]);   
    for(ll i=1;i<=m;++i)printf("%lld\n",dis[in[i]]-dis[die[i]]);
    return 0;
}