bzoj 4003: 城池攻占左偏树

题目大意

http://www.lydsy.com/JudgeOnline/problem.php?id=4003

题解

一开始看漏条件了

题目保证当占领城池可以使攻击力乘上\(v_i\)时,一定有\(v_i>0\)

上面这句话很重要(或者说去掉这句话就可以出成一道新题)

我们考虑在每个节点上都维护一个最小堆

每次移动时我们让在堆中的所有骑士一起移动

这样我们知道:如果堆顶的骑士可以占领成功

那么这个堆里剩下的所有骑士都一定能够占领成功

如果堆顶元素无法占领我们就删去这个堆顶的元素,这样我们最多删除n次

最坏情况是\(O(nlogn)\)的,可以承受

所以我们还需要这个堆支持快速合并,任意一个可并堆即可

于是我敲了一棵左偏树上去...打标记打到手软...第一次在堆上打标记

这个标记的正确性就由上面加粗的话保证了

这句话保证了:打标记后树的结构不会改变

调了1h才发现是merge没有return...

神奇的windows系统还让我过了样例和对拍,linux虚拟机下直接爆炸

Code

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

template<typename T>inline void read(T &x){

    x=0;char ch;bool flag = false;

    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

inline int cat_max(const int &a,const int &b){return a>b ? a:b;}

inline int cat_min(const int &a,const int &b){return a<b ? a:b;}

const int maxn = 300010;

struct Node{

    Node *ch[2];

    ll val,add,mul;

    int cnt,tag,deg,id;

}*null;

Node mem[maxn<<1],*li;

Node *root[maxn];

inline void init(){

    li = mem;null = li++;

    null->ch[0] = null->ch[1] = null;

    null->val = null->add = null->cnt

    = null->tag = null->mul = 0;

}

inline Node* newNode(int id,ll val){

    Node *p = li++;p->val = val;

    p->ch[0] = p->ch[1] = null;

    p->cnt = p->tag = p->deg = p->add = 0;

    p->mul = 1;p->id = id;return p;

}

inline void pushdown(Node *p){

    if(p == null) return;

    if(p->ch[0] != null){

        Node *x = p->ch[0];

        if(p->mul != 1){x->mul *= p->mul;x->add *= p->mul;x->val *= p->mul;}

        if(p->add != 0){x->add += p->add;x->val += p->add;}

        if(p->tag != 0){x->tag += p->tag;x->cnt += p->tag;}

    }

    if(p->ch[1] != null){

        Node *x = p->ch[1];

        if(p->mul != 1){x->mul *= p->mul;x->add *= p->mul;x->val *= p->mul;}

        if(p->add != 0){x->add += p->add;x->val += p->add;}

        if(p->tag != 0){x->tag += p->tag;x->cnt += p->tag;}

    }p->mul = 1;p->tag = p->add = 0;

}

Node *merge(Node *x,Node *y){

    //printf("%d %d\n",x,y);

    if(x == null) return y;

    if(y == null) return x;

    if(x->val > y->val) swap(x,y);

    pushdown(x);

    x->ch[1] = merge(x->ch[1],y);

    if(x->ch[0]->deg < x->ch[1]->deg)

        swap(x->ch[0],x->ch[1]);

    x->deg = x->ch[1]->deg + 1;

    return x;

}

int ans1[maxn],ans2[maxn];

inline void pop_less(int i,ll k,int p){

    while(1){

        if(root[i] == null) break;

        if(root[i]->val >= k) break;

        pushdown(root[i]);

        ans2[root[i]->id] = root[i]->cnt;

        //printf("%d died on %d with killed %d\n",root[i]->id,p,root[i]->cnt);

        //printf("%lld <-> %lld\n",root[i]->val,k);

        root[i] = merge(root[i]->ch[0],root[i]->ch[1]);

        ans1[p]++;

    }

}

ll h[maxn],v[maxn],s[maxn];

int c[maxn],fa[maxn],a[maxn];

inline void update(Node *p,int i){

    //printf("update");

    p->tag++;p->cnt++;

    if(a[i] == 0){

        p->add += v[i];

        p->val += v[i];

    }else{

        p->mul *= v[i];

        p->add *= v[i];

        p->val *= v[i];

    }

}

int main(){

    init();

    int n,m;read(n);read(m);

    for(int i=1;i<=n;++i) read(h[i]),root[i] = null;

    //printf("%d\n",root[2]);

    for(int i=2;i<=n;++i){

        read(fa[i]);read(a[i]);read(v[i]);

    }

    for(int i=1;i<=m;++i){

        read(s[i]);read(c[i]);

        if(s[i] < h[c[i]]){

            ans1[c[i]]++;

            ans2[i] = 0;

        }else{

            Node *p = newNode(i,s[i]);

            update(p,c[i]);

            root[c[i]] = merge(root[c[i]],p);

        }

    }

    for(int i=n;i>=2;--i){

        pop_less(i,h[fa[i]],fa[i]);

        update(root[i],fa[i]);

        root[fa[i]] = merge(root[i],root[fa[i]]);

    }

    while(root[1] != null){

        pushdown(root[1]);

        ans2[root[1]->id] = root[1]->cnt;

        //printf("%d win with killed %d\n",root[1]->id,root[1]->cnt);

        root[1] = merge(root[1]->ch[0],root[1]->ch[1]);

    }

    for(int i=1;i<=n;++i) printf("%d\n",ans1[i]);

    for(int i=1;i<=m;++i) printf("%d\n",ans2[i]);

    getchar();getchar();

    return 0;

}

巴特西

bzoj 4003: 城池攻占左偏树

题目大意

题解

Code

最新文章

热门文章

巴特西

bzoj 4003: 城池攻占 左偏树

题目大意

题解

Code

最新文章

热门文章

bzoj 4003: 城池攻占左偏树