1647 字
8 分钟
BZOJ 2827 千山鸟飞绝 Treap
2017-09-24
题解
Treap

题目描述#

话说有一天doyouloveme和vfleaking到山里玩。谁知doyouloveme刚刚进山，所有的鸟儿竟被他的神犇气场给惊得全部飞走了。vfleaking顿时膜拜不已。
这时鸟王用鸟语说道：“!@#$%……?”安抚了一下众鸟的情绪。鸟王生性好斗，作出了一个决定——要排鸟布阵把刚才吓到它们的人类赶出山去。

每只鸟都有一个编号，都有一个威武值。每秒钟鸟王都会发一个命令，编号为v的鸟飞到(x,y)去（坐标系原点是山顶，坐标单位为鸟爪）。鸟飞得很快，一秒之内就飞到了，可以看作是瞬间移动。如果编号为v的鸟和编号为u的鸟某一时刻处在同一位置，它们就会互相鼓励，增加各自的士气值和团结值。一只鸟的士气值等于此刻与它处在同一位置的鸟中的威武值的最大值，团结值等于此刻与它处在同一位置的鸟的只数。如果每一时刻都没有鸟与它处在同一位置，则士气值和团结值都为0。要注意自己不能鼓励自己，计算士气值和团结值时不能算上自己。 t秒钟后，doyouloveme目测出了现在每只鸟的战斗力，于是感叹了一句：“不妙，我们得走了。”
正所谓团结的鸟儿一个顶俩，所以doyouloveme这样描述战斗力：一只鸟战斗力值等于它在0到t秒中士气值的最大值与团结值的最大值的乘积。注意不是乘积的最大值，而是最大值的乘积。
vfleaking很想知道现在每只鸟的战斗力，但是他当然不会啦，于是他把这个任务交给了你来完成。

输入#

第一行一个数n，代表鸟的只数。（鸟王那家伙你可以完全忽视掉）
接下来n行，每行三个整数w,x,y描述每只鸟的威武值和初始坐标。第i+1行描述编号为i的鸟。
接下来一行有一个数t，代表经过时间ts。
接下来t行，每行三个整数v,x,y描述鸟王每秒的命令。

输出#

一共n行，每行一个数，代表每只鸟的战斗力。

样例输入#

5
1 1 1
3 1 2
4 4 4
2 0 1
2 2 3
5
1 1 2
2 4 4
2 4 3
3 0 1
5 0 1

样例输出#

3
4
6
8
8

提示#

对于样例的解释： 首先5只鸟的位置为(1,1),(1,2),(4,4),(0,1),(2,3)，士气和团结值都是0。
鸟1飞到了(1,2)，于是鸟1和鸟2互相鼓励，鸟1士气变为3，鸟2士气变为1。鸟1鸟2的团结值变为1。
然后鸟2飞到(4,4)，与鸟3互相鼓励，鸟2士气变为4，鸟3士气变为3。鸟2与鸟3的团结值变为1。
鸟2然后飞到了(4,3)，一个没有鸟的地方。于是士气和团结值都变为了0。
接下来鸟3和鸟5都飞到了鸟4的位置，于是三只鸟互相鼓励，鸟4、鸟5士气变为4，鸟3士气仍为3。鸟3、鸟4、鸟5的团结值都变为2。
于是大家的战斗力：
鸟1：3 * 1 = 3
鸟2：4 * 1 = 4
鸟3：3 * 2 = 6
鸟4：4 * 2 = 8
鸟5：4 * 2 = 8
1≤n≤30000 0≤t≤300000
坐标范围为整数，且不超过INT_MIN~INT_MAX
威武值为不超过INT_MAX的非负整数。

题解#

哈希加Treap

把每一个点Hash对应的一棵Treap上
在插入和删除的时候不断的打标记跟新
注意不要漏情况
在最后的时候要把所有的标记都推下去
然后就出来了
细节很多调了好久

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int Max_Morale[30005], Max_Solidarity[30005];
struct Point
{
    int x, y;
    Point(int a = 0, int b = 0)
    {
        x = a, y = b;
    }
    bool operator==(const Point &a) const
    {
        return x == a.x && y == a.y;
    }
};
struct data
{
    int x, ID;
    data(int a = 0, int b = 0)
    {
        x = a, ID = b;
    }
    bool operator>(const data &a) const
    {
        return x == a.x ? ID > a.ID : x > a.x;
    }
    bool operator<=(const data &a) const
    {
        return !(*this > a);
    }
};
struct Treap
{
    struct Node
    {
        int s, key, Max_Num, Max_Size;
        data x;
        Node *ch[2];
        Node(data sa)
        {
            ch[0] = ch[1] = NULL;
            s = 1, x = sa, key = rand();
            Max_Num = Max_Size = 0;
        }
#define size(_) ((_) ? (_)->s : 0)
        void Pushup()
        {
            s = size(ch[0]) + size(ch[1]) + 1;
        }
        void Pushdown()
        {
            if (ch[0])
            {
                ch[0]->Max_Num = max(ch[0]->Max_Num, Max_Num);
                ch[0]->Max_Size = max(ch[0]->Max_Size, Max_Size);
                Max_Morale[ch[0]->x.ID] = max(Max_Morale[ch[0]->x.ID], ch[0]->Max_Num);
                Max_Solidarity[ch[0]->x.ID] = max(Max_Solidarity[ch[0]->x.ID], ch[0]->Max_Size);
            }
            if (ch[1])
            {
                ch[1]->Max_Num = max(ch[1]->Max_Num, Max_Num);
                ch[1]->Max_Size = max(ch[1]->Max_Size, Max_Size);
                Max_Morale[ch[1]->x.ID] = max(Max_Morale[ch[1]->x.ID], ch[1]->Max_Num);
                Max_Solidarity[ch[1]->x.ID] = max(Max_Solidarity[ch[1]->x.ID], ch[1]->Max_Size);
            }
            Max_Num = Max_Size = 0;
        }
    } * root;
    Treap()
    {
        root = NULL;
    }
    Node *Merge(Node *A, Node *B)
    {
        if (!A)
            return B;
        if (!B)
            return A;
        if (A->key < B->key)
        {
            A->Pushdown();
            A->ch[1] = Merge(A->ch[1], B);
            A->Pushup();
            return A;
        }
        else
        {
            B->Pushdown();
            B->ch[0] = Merge(A, B->ch[0]);
            B->Pushup();
            return B;
        }
    }
    typedef pair<Node *, Node *> DNode;
    DNode Split(Node *rt, int k)
    {
        if (!rt)
            return DNode(NULL, NULL);
        DNode o;
        rt->Pushdown();
        if (size(rt->ch[0]) >= k)
        {
            o = Split(rt->ch[0], k);
            rt->ch[0] = o.second;
            rt->Pushup();
            o.second = rt;
        }
        else
        {
            o = Split(rt->ch[1], k - size(rt->ch[0]) - 1);
            rt->ch[1] = o.first;
            rt->Pushup();
            o.first = rt;
        }
        return o;
    }
    Node *kth(int k)
    {
        DNode x = Split(root, k - 1);
        DNode y = Split(x.second, 1);
        Node *ans = y.first;
        root = Merge(Merge(x.first, ans), y.second);
        return ans;
    }
    int Rank(Node *rt, data x)
    {
        if (!rt)
            return 0;
        return x <= rt->x ? Rank(rt->ch[0], x) : Rank(rt->ch[1], x) + size(rt->ch[0]) + 1;
    }
    void Insert(data x)
    {
        int k = Rank(root, x);
        if (root)
        {
            root->Max_Size = max(root->Max_Size, size(root));
            root->Max_Num = max(root->Max_Num, x.x);
            Max_Morale[root->x.ID] = max(root->Max_Num, Max_Morale[root->x.ID]);
            Max_Solidarity[root->x.ID] = max(root->Max_Size, Max_Solidarity[root->x.ID]);
        }
        DNode y = Split(root, k);
        Node *n = new Node(x);
        root = Merge(Merge(y.first, n), y.second);
    }
    void remove(data x)
    {
        int k = Rank(root, x);
        DNode a = Split(root, k);
        DNode b = Split(a.second, 1);
        delete b.first;
        root = Merge(a.first, b.second);
    }
};
#define Hash_MOD 76543
#define Hash_MOD_x 9991
#define Hash_MOD_y 7307
int p = 0;
struct Hash_Table
{
    int first[76545];
    struct Link
    {
        Treap *rt;
        Point t;
        int next;
    } v[400000];
    Hash_Table()
    {
        memset(first, -1, sizeof(first));
    }
    void Push(int u, Point now, Treap *x)
    {
        v[p].rt = x;
        v[p].t = now;
        v[p].next = first[u];
        first[u] = p++;
    }
    Treap *&operator[](Point x)
    {
        int Hash = (((x.x % Hash_MOD_x) + Hash_MOD_x) % Hash_MOD_x) * (((x.y % Hash_MOD_y) + Hash_MOD_y) % Hash_MOD_y) % Hash_MOD;
        for (int i = first[Hash]; i != -1; i = v[i].next)
            if (v[i].t == x)
                return v[i].rt;
        Push(Hash, x, new Treap);
        return v[first[Hash]].rt;
    }
} Hash;
#define X(_) ((_) ? (_)->x : 0)

Point bird[30005];
int Num[30005];
int main()
{
    int n;
    scanf("%d", &n);
    int a, b, c;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        Max_Morale[i] = max(Max_Morale[i], X(Hash[Point(b, c)]->kth(size(Hash[Point(b, c)]->root))).x);
        Max_Solidarity[i] = max(Max_Solidarity[i], size(Hash[Point(b, c)]->root));
        Hash[Point(b, c)]->Insert(data(a, i));
        bird[i] = Point(b, c);
        Num[i] = a;
    }
    int m;
    scanf("%d", &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        Hash[bird[a]]->remove(data(Num[a], a));
        Max_Morale[a] = max(Max_Morale[a], X(Hash[Point(b, c)]->kth(size(Hash[Point(b, c)]->root))).x);
        Max_Solidarity[a] = max(Max_Solidarity[a], size(Hash[Point(b, c)]->root));
        Hash[Point(b, c)]->Insert(data(Num[a], a));
        bird[a] = Point(b, c);
    }
    for (int i = 1; i <= n; i++)
        Hash[bird[i]]->remove(data(Num[i],i));
    for (int i = 1; i <= n; i++)
        printf("%lld\n", (long long)Max_Morale[i] * Max_Solidarity[i]);
    // while(1);
}
BZOJ 2827 千山鸟飞绝 Treap
https://www.nekomio.com/posts/110/
作者
NekoMio
发布于
2017-09-24
许可协议
CC BY-NC-SA 4.0
后缀数组
BZOJ 3211 花神游历各国