展开

题目描述

如题，一开始有N个小根堆，每个堆包含且仅包含一个数。接下来需要支持两种操作：

操作1： 1 x y 将第x个数和第y个数所在的小根堆合并（若第x或第y个数已经被删除或第x和第y个数在用一个堆内，则无视此操作）

操作2： 2 x 输出第x个数所在的堆最小数，并将其删除（若第x个数已经被删除，则输出-1并无视删除操作）

输入格式

第一行包含两个正整数N、M，分别表示一开始小根堆的个数和接下来操作的个数。

第二行包含N个正整数，其中第i个正整数表示第i个小根堆初始时包含且仅包含的数。

接下来M行每行2个或3个正整数，表示一条操作，格式如下：

操作1 ： 1 x y

操作2 ： 2 x

输出格式

输出包含若干行整数，分别依次对应每一个操作2所得的结果。

输入输出样例

输入 #1复制

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

输出 #1复制

1
2

说明/提示

当堆里有多个最小值时，优先删除原序列的靠前的，否则会影响后续操作1导致WA。

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=10，M<=10

对于70%的数据：N<=1000，M<=1000

对于100%的数据：N<=100000，M<=100000

样例说明：

初始状态下，五个小根堆分别为:{1}、{5}、{4}、{2}、{3}。

第一次操作，将第1个数所在的小根堆与第5个数所在的小根堆合并，故变为四个小根堆：{1,3}、{5}、{4}、{2}。

第二次操作，将第2个数所在的小根堆与第5个数所在的小根堆合并，故变为三个小根堆：{1,3,5}、{4}、{2}。

第三次操作，将第2个数所在的小根堆的最小值输出并删除，故输出1，第一个数被删除，三个小根堆为：{3,5}、{4}、{2}。

第四次操作，将第4个数所在的小根堆与第2个数所在的小根堆合并，故变为两个小根堆：{2,3,5}、{4}。

第五次操作，将第2个数所在的小根堆的最小值输出并删除，故输出2，第四个数被删除，两个小根堆为：{3,5}、{4}。

故输出依次为1、2。

左偏树的模板题，但普通的模板会T，因为需要一个并查集来加快查询。当然这题有骚操作pb_ds的priority_queue，使用join进行合并

T最后一个点

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
/*
 *  合并复杂度 O(log N)
 *  INIT: init()读入数据并进行初始化;
 *  CALL: merge() 合并两棵左偏树; 
 *        ins() 插入一个新节点; 
 *        top() 取得最小结点; 
 *        pop() 取得并删除最小结点; 
 *        del() 删除某结点;
 *        add() 增/减一个结点的键值;
 *        iroot() 获取结点i的根;
 */
#define typec int       //  type of key val
const int na = -1;
const int N = 100010;
int n,m;
struct node
{
    typec key;
    int l, r, f, dist;
} tr[N];

int iroot(int i)
{   //  find i's root
    if (i == na)
    {
        return i;
    }
    while (tr[i].f != na)
    {
        i = tr[i].f;
    }
    return i;
}

int merge(int rx, int ry)
{
    //  two root:   rx, ry
    if (rx == na)
    {
        return ry;
    }
    if (ry == na)
    {
        return rx;
    }
    if (tr[rx].key > tr[ry].key)
    {
        swap(rx, ry);
    }
    int r = merge(tr[rx].r, ry);
    tr[rx].r = r;
    tr[r].f = rx;
    if (tr[r].dist > tr[tr[rx].l].dist)
    {
        swap(tr[rx].l, tr[rx].r);
    }
    if (tr[rx].r == na)
    {
        tr[rx].dist = 0;
    }
    else
    {
        tr[rx].dist = tr[tr[rx].r].dist + 1;
    }
    return rx;  //  return new root
}

int ins(int i, typec key, int root)
{   //  add a new node(i, key)
    tr[i].key = key;
    tr[i].l = tr[i].r = tr[i].f = na;
    tr[i].dist = 0;
    return root = merge(root, i);   //  return new root
}

int del(int i)
{   //  delete node i
    if (i == na)
    {
        return i;
    }
    int x, y, l, r;
    l = tr[i].l;
    r = tr[i].r;
    y = tr[i].f;
    tr[i].l = tr[i].r = tr[i].f = na;
    tr[x = merge(l, r)].f = y;
    if (y != na && tr[y].l == i)
    {
        tr[y].l = x;
    }
    if (y != na && tr[y].r == i)
    {
        tr[y].r = x;
    }
    for (; y != na; x = y, y = tr[y].f)
    {
        if (tr[tr[y].l].dist < tr[tr[y].r].dist)
        {
            swap(tr[y].l, tr[y].r);
        }
        if (tr[tr[y].r].dist + 1 == tr[y].dist)
        {
            break;
        }
        tr[y].dist = tr[tr[y].r].dist + 1;
    }
    if (x != na)    //  return new root
    {
        return iroot(x);
    }
    else return iroot(y);
}

node top(int root)
{
    return tr[root];
}

node pop(int &root)
{
    node out = tr[root];
    tr[root].key=-1;
    int l = tr[root].l, r = tr[root].r;
    tr[root].l = tr[root].r = tr[root].f = na;
    tr[l].f = tr[r].f = na;
    root = merge(l, r);
    return out;
}

int add(int i, typec val)   //  tr[i].key += val
{
    if (i == na)
    {
        return i;
    }
    if (tr[i].l == na && tr[i].r == na && tr[i].f == na)
    {
        tr[i].key += val;
        return i;
    }
    typec key = tr[i].key + val;
    int rt = del(i);
    return ins(i, key, rt);
}

void init(int n)
{
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &tr[i].key);    //  %d: type of key
        tr[i].l = tr[i].r = tr[i].f = na;
        tr[i].dist = 0;
    }
    return ;
}
int main()
{
	
	 scanf("%d%d",&n,&m);
	 init(n);
	 
	 while(m--)
	 {
	 	int op;
	 	scanf("%d",&op);
	 	if(op==1)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			if(x==y) continue;
			if(tr[x].key==-1||tr[y].key==-1)
			{
				continue;
			}
			int fx=iroot(x),fy=iroot(y);
			//cout<<fx<<"*"<<fy<<endl;
			if(fx!=fy)
				merge(fx,fy);
			//cout<<top(fx).key<<"&"<<top(fy).key<<endl;
		}
		else
		{
			int x;
			scanf("%d",&x);
			
			int fx=iroot(x);
			if(tr[fx].key==-1) 
			{
				cout<<-1<<endl;
			}
			else printf("%d\n",pop(fx).key);
		}
	 	
	 }
}

AC245ms

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXN 100010
using namespace std;

template<class T>
void swp(T &x,T &y)
{
    T t=x;
    x=y;
    y=t;
}
struct node
{
    int val;//value 表示这个数的值
    int ind;//index 表示这个数是原序列中的下标
    int dis;
    node *lk;
    node *rk;
    int flag()
    {
        if(lk==NULL&&rk!=NULL)
            return 1;
        if(lk!=NULL&&rk!=NULL&&lk->dis<rk->dis)
            return 1;
        return 0;
    }//这个flag比较丑，是判断节点是否满足左偏性质的
};

node *rt[MAXN];
int n,m,f[MAXN],rnk[MAXN],used[MAXN];//f表示并查集的父节点，rnk表示权用于按权合并，used[i]表示第i个数是否删除过

int froot(int x);
int greater(node *x,node *y);
int uni(int x,int y);
node *merge(node *x,node *y);
node *pop(node *x);
node *push(node *x,int v,int i);
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1; i<=n; i++)
        rnk[i]=1;
    int t;
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&t);
        rt[i]=push(NULL,t,i);
    }
    int flag,x,y;
    for(int i=1; i<=m; i++)
    {
        scanf("%d",&flag);
        if(flag==1)
        {
            scanf("%d %d",&x,&y);
            if(used[x]||used[y])
                continue;
            int ra=froot(x),rb=froot(y);
            if(ra==rb)
                continue;
            int rn=uni(ra,rb);
            rt[rn]=merge(rt[ra],rt[rb]);
        }
        else if(flag==2)
        {
            scanf("%d",&x);
            if(used[x])
            {
                puts("-1");// 记得输出-1 我wa了一次
                continue;
            }
            int ra=froot(x);
            printf("%d\n",rt[ra]->val);
            used[rt[ra]->ind]=1;
            rt[ra]=pop(rt[ra]);
        }
    }
    return 0;
}

int uni(int x,int y)
{
    if(rnk[x]<rnk[y])
        swp(x,y);
    f[y]=x;
    rnk[x]+=rnk[y];
    return x;//返回新的并查集的根 一般的并查集不这么打
}

int gter(node *x,node *y)
{
    if(x->val>y->val)
        return 1;
    if(x->val<y->val)
        return 0;
    if(x->ind>y->ind)
        return 1;
    return 0;
}//自定义比较函数，因为题目要求val相同优先删除ind比较小的，不妨ind较小的放到堆的上方

int froot(int x)
{
    if(!f[x])
        return x;
    f[x]=froot(f[x]);
    return f[x];
}

node *merge(node *x,node *y)
{
    if(x==NULL)
        return y;
    if(y==NULL)
        return x;
    if(gter(x,y))
        swp(x,y);
    x->rk=merge(x->rk,y);
    if(x->flag())
        swp(x->lk,x->rk);
    x->dis=x->rk==NULL?0:x->rk->dis+1;
    return x;
}

node *pop(node *x)
{
    node *p=x;
    x=merge(p->lk,p->rk);
    delete p;
    return x;
}

node *push(node *x,int v,int i)
{
    node *p=new node;
    p->val=v;
    p->ind=i;
    p->dis=0;
    p->lk=NULL;
    p->rk=NULL;
    return merge(x,p);
}

#include<bits/stdc++.h>
#include<bits/extc++.h>//ext万能头，包含各类ext头文件
using namespace std;
using namespace __gnu_pbds;
__gnu_pbds::priority_queue<pair<int,int>,greater<pair<int,int> >,pairing_heap_tag>h[100005];
int n,m,x,y,z,u,v,f[100005];//f为并查集数组
bool b[100005];//存储是否被删除
char ch[10000009],*k=ch;
pair<int,int>p;
void in(int &x){
    while(*k<48||*k>57)k++;
    for(x=*k++-48;*k>=48&&*k<=57;k++)x=(x<<1)+(x<<3)+*k-48;
}
int getf(int x){
    return f[x]==x?x:f[x]=getf(f[x]);
}//并查集
int main(){
    fread(ch,1,10000005,stdin);
    in(n),in(m);
    for(int i=1;i<=n;i++)in(x),f[i]=i,h[i].push(make_pair(x,i));
    while(m--){
        in(x);
        if(x==1){
            in(y),in(z),u=getf(y),v=getf(z);
            if(b[y]||b[z]||u==v)continue;//已被删除或在同一堆中则忽略操作
            h[u].join(h[v]),f[v]=u;
        }else{
            in(y),u=getf(y);
            if(b[y]||h[u].empty())puts("-1");//不要忘记输出-1
            else p=h[u].top(),h[u].pop(),b[p.second]=1,printf("%d\n",p.first);
        }
    }
}