2016年4月18日 星期一

Codechef April Challenge 2016 Mario and Luigi

// https://www.codechef.com/problems/FURGRAPH
/*
    雖然說原題是邊的兩端點
    都要佔領才能得分
    但把它當成佔領一個就能得分也是可以的
    因為兩人各佔一個的話 分數就會抵消
    只是要注意 這樣的兩人的分數差會變兩倍

    把問題轉化成這樣後 可以發現顯然
    兩個人都會想優先選 周圍邊權和比較大的點
    設數列 F[i] 為 點i周圍的邊權和
    那原題等價於 求F 大到小排序後 
    奇數項的和扣掉偶數項的和
    這可以使用 treap 來維護
    複雜度 O((N+M)logN)
*/

#include <algorithm>
#include <iostream>
#include <cstdio>
 
using namespace std;
 
typedef long long ll;
ll num[200000];
 
struct Node
{
    Node *l, *r;
    ll sum, num;
    int pri, sz;
 
    Node(ll x = 0):l(NULL),r(NULL),sum(x),num(x),pri(rand() ),sz(1){}
};
 
inline int Size(Node *O)
{
    return O ? O->sz : 0;
}
 
inline ll Sum(Node *O)
{
    return O ? O->sum : 0;
}
 
inline void pull(Node *O)
{
    ll p = O->num - Sum(O->r);
    O->sz = Size(O->l)+1+Size(O->r);
 
    if( Size(O->l) & 1 ) O->sum = Sum(O->l)-p;
    else O->sum = Sum(O->l)+p;
}
 
Node *merge(Node *a, Node *b)
{
    if( !a || !b ) return a ? a : b;
    else if( a->pri >= b->pri )
    {
        a->r = merge(a->r, b);
        pull(a);
        return a;
    }
    else
    {
        b->l = merge(a, b->l);
        pull(b);
        return b;
    }
}
 
void split(Node *O, Node *&a, Node *&b, ll k)
{
    if( !O ) a = b = NULL;
    else if( O->num >= k )
    {
        a = O;
        split(O->r, a->r, b, k);
        pull(a);
    }
    else
    {
        b = O;
        split(O->l, a, b->l, k);
        pull(b);
    }
}
 
void add(Node *&O, ll x)
{
    Node *l, *r;
    split(O, l, r, x);
    O = merge(merge(l, new Node(x)), r);
}
 
void del(Node *&O, ll x)
{
    if( x == O->num ) O = merge(O->l, O->r);
    else if( x > O->num )
    {
        del(O->l, x);
        pull(O);
    }
    else
    {
        del(O->r, x);
        pull(O);
    }
}
 
 
 
int main()
{
    srand(408);
 
    int T;
    scanf("%d", &T);
 
    while( T-- )
    {
        int N, M;
        scanf("%d %d", &N, &M);
 
        Node *root = NULL;
 
        for(int Ni = 1; Ni <= N; Ni++)
        {
            num[Ni] = 0;
            root = merge(root, new Node(0));
        }
 
        for(int Mi = 0; Mi < M; Mi++)
        {
            int u, v, c;
            scanf("%d %d %d", &u, &v, &c);
 
 
            del(root, num[u]);
            if( u != v ) del(root, num[v]);
 
            num[u] += c;
            num[v] += c;
 
            add(root, num[u]);
            if( u != v ) add(root, num[v]);
 
            printf("%lld\n", root->sum/2);
        }
    }
}

沒有留言:

張貼留言