[Bzoj5179][Jsoi2011]任务调度（左偏树）

5179: [Jsoi2011]任务调度

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 5 Solved: 4
[Submit][Status][Discuss]

Description

一台超级计算机共有N颗CPU。现在这台超级计算机有M个任务要做，但同时还要考虑到不能让CPU过热。所幸的是这

台超级计算机已经将任务安排好了，现在要做的只是请你根据安排好的指令来模拟它的工作过程。一开始，这N颗C

PU都没有被分配任何的任务。之后，会给你以下几类指令（CPU的编号为1到N的整数，任务的编号为1到M的整数）

指令格式作用

ADD n k w 将 k 号任务（权值为 w）分配给 n 号 CPU

DEC n k w 将 k 号任务的权值减少 w（已知 k 号任务被分配给了 n 号 CPU）

TRANS n1 n2 将分配给 n1 号 CPU 的任务全部转移给 n2 号 CPU

MIN n 输出分配给 n 号 CPU 的任务中权值最小的任务的权值

WORK n w 将分配给 n 号 CPU 的任务中权值最小的任务的权值加上 w，

如果权值最小的任务不唯一，则不更改权值，并输出一行“ ERROR”

Input

包含N+1行。

第1行包含三个正整数N、M、K，分别表示CPU的数目、任务数和指令数。

第2行到N+1行，每行包含一条指令。

N≤500， M≤300000， K≤300000。

保证任务的权值在 32 位有符号整型的范围内。

保证一个任务只会被分配一次（即至多被 ADD 一次）。

保证 ADD 指令、DEC 指令和 WORK 指令中的 w 是非负整数。

保证 TRANS 指令的两个参数不相同。

Output

若干行，其中包括MIN语句的输出和“ERROR”输出，每个输出占一行

Sample Input

ADD

ADD

MIN

WORK

TRANS

MIN

ADD

TRANS

MIN

DEC

MIN

DEC

WORK

Sample Output


-

ERROR

分析：

裸裸的可并堆题，用左偏树乱搞即可

代码：

# include <iostream>

# include <cstdio>

# include <algorithm>

using namespace std;

const int N = 3e5 + ;

int d[],n,m,k;

struct node{

   int w,d,lc,rc,fa;

}t[N];

int merge(int x,int y)

{

    if(!x)return y;

    if(!y)return x;

    if(t[x].w > t[y].w)swap(x,y);

    t[x].rc = merge(t[x].rc,y);

    t[t[x].rc].fa = x;

    if(t[t[x].rc].d > t[t[x].lc].d)swap(t[x].rc,t[x].lc);

    t[x].d = t[t[x].rc].d + ;

    return x;

}

void erase(int x,int y,int z)

{

    int u = merge(t[y].lc,t[y].rc),g = t[y].fa;

    if(d[x] == y)d[x] = u;

    if(t[g].lc == y)t[g].lc = u;

    else if(t[g].rc == y)t[g].rc = u;

    t[u].fa = g;t[y].lc = t[y].rc = t[y].fa = t[y].d = ;

    t[y].w += z;

    d[x] = merge(d[x],y);

}

int main()

{

   scanf("%d %d %d",&n,&m,&k);char ch[];int x,y,z;

   while(k--)

   {

    scanf("%s",ch);

    if(ch[] == 'A')

    {

        scanf("%d %d %d",&x,&y,&z);

        t[y].w = z;

        d[x] = merge(d[x],y);

    }

    if(ch[] == 'D')

    {

        scanf("%d %d %d",&x,&y,&z);

        erase(x,y,-z);

    }

    if(ch[] == 'T')

    {

        scanf("%d %d",&x,&y);

        d[y] = merge(d[x],d[y]);

        d[x] = ;

    }

    if(ch[] == 'M')

    {

        scanf("%d",&x);

        printf("%d\n",t[d[x]].w);

    }

    if(ch[] == 'W')

    {

        scanf("%d %d",&x,&y);

        bool flag = true;int l = t[d[x]].lc,r = t[d[x]].rc;

        if(l && t[l].w == t[d[x]].w)flag = false;

        if(r && t[r].w == t[d[x]].w)flag = false;

        if(flag)erase(x,d[x],y);

        else puts("ERROR");

    }

   }

}

巴特西