bzoj千题计划218：bzoj2333: [SCOI2011]棘手的操作-白红宇

bzoj千题计划218：bzoj2333: [SCOI2011]棘手的操作

阅读量：7002 次

发布时间：2019-06-27

本文共 981 字，大约阅读时间需要 3 分钟。

上次那个是线段树，再发一个左偏树

维护两种左偏树

第一种是对每个联通块维护一个左偏树

第二种是对所有第一种左偏树的根节点维护一个左偏树

#include
     
      #include
      
       #include
       
        using namespace std;#define N 300001/*void read(int &x){    x=0; int f=1; char c=getchar();    while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }    x*=f;}*/struct Leftist{    int fa[N],lc[N],rc[N];    int dis[N];    int val[N],tag[N];        int st[N];        void addsingle(int x,int y)    {        if(!x) return;        val[x]+=y;        tag[x]+=y;    }        void down(int x)    {        if(!tag[x]) return;        addsingle(lc[x],tag[x]);        addsingle(rc[x],tag[x]);        tag[x]=0;    }        void download(int x)    {        int top=0;        for(int i=x;i;i=fa[i]) st[++top]=i;        for(;top;--top) down(top);    }        int merge(int x,int y)    {        if(!x || !y) return x+y;        if(val[x]