hdu5575

题解：

每一次最短的那块板合并

先装水到溢出

然后合并

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

typedef pair<int,int> mp;

const int N=;

vector<mp> vec;

int LH[N],RH[N],L[N],R[N],O[N],X[N],heap[N],l[N],r[N],dist[N];

int T,kase,v[N],f[N],tot,n,m,x,y,z;

int find(int x){return f[x]==x?x:f[x]=find(f[x]);}

int merge(int x,int y)

{

    if (!x||!y)return x+y;

    if (v[x]>v[y])swap(x,y);

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

    if (dist[l[x]]<dist[r[x]])swap(l[x],r[x]);

    dist[x]=dist[r[x]]+;

    return x;

}

void Union(int x,int y)

{

    x=find(x);y=find(y);

    if (x==y)return;

    f[y]=x;

    if (x<y)

     {

        RH[x]=RH[y];

        L[R[x]]=x;

        R[x]=R[y];

     }

    else

     {

        LH[x]=LH[y];

        R[L[x]]=x;

        L[x]=L[y];

     }

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

    X[x]+=X[y];

    O[x]+=O[y];

}

int pop(int x){return merge(l[x],r[x]);}

int main()

{

    scanf("%d",&T);

    while(T--)

     {

        scanf("%d%d",&n,&m);

        int ans=;LH[]=RH[n]=1e9;L[n]=n-;

        for (int i=;i<n;i++)

         {

            scanf("%d",&RH[i]);

            LH[i+]=RH[i];

            L[i]=i-;R[i]=i+;

         }

        vec.clear();

        memset(heap,,sizeof(heap));

        tot=;

        while(m--)

         {

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

            if (z)vec.push_back(mp(y+,x));

            else

             {

                ++ans;

                v[++tot]=y;

                l[tot]=r[tot]=dist[tot]=;

                heap[x]=heap[x]?merge(heap[x],tot):tot;

             }

         }

        for (int i=;i<=n;i++) f[i]=i;

        sort(vec.begin(),vec.end());

        for (int i=;i<=n;i++) O[i]=X[i]=;

        for (int i=;i<vec.size();i++)

         {

            int x=find(vec[i].second),y=vec[i].first;

            while(y>LH[x])Union(x,L[x]),x=find(x);

            while(y>RH[x])Union(x,R[x]),x=find(x);

            while(heap[x]!=&&v[heap[x]]<y)

             {

                heap[x]=pop(heap[x]);

                ++X[x];

             }

            if (++O[x]>=X[x])

             {

                ans+=(O[x]-X[x]);

                O[x]=X[x]=;

             }

         }

        printf("Case #%d: %d\n",++kase,ans);

     }

}