HDU--5575、Discover Water Tank （思维、优先队列）

题目链接

题面：

题意：
有一个 $1\ast n$1∗n 的水箱，水箱的四周的高度为无穷大。现在用 $n-1$n−1 高度为 $h_i$hi​ 的隔板将水箱分为 $n$n 个 $1\ast 1$1∗1 的部分。

隔板不透水，但是水的流动遵循一般的物理规律，即如果当前水位如果比某一侧的隔板要高，谁就会从一个部分流向另一个部分。

现在已知这 $n$n 个部分某些部分可能有一定高度的水，进行 $m$m 次探测，第 $i$i 次探测以 $x$x $y$y $z$z 的形式给出，如果 $z=0$z=0 ，说明第 $x$x 个部分高度为 $(y+0.5)$(y+0.5) 处没有水。如果 $z=1$z=1 ，说明第 $x$x 个部分高度为 $(y+0.5)$(y+0.5) 处有水。

但是不保证这 $m$m 个查询一定正确，问这 $m$m 个查询中最多有多少个是正确的。

题解：
考虑初始时，如果所有的部分都没有水，那么答案 $ans=\sum [z=0]$ans=∑[z=0]。

但是让一些部分有水以后，答案可能会更优。

我们从小到大枚举水的高度 $y$y（向下取整）。

找到当前如果第 $x$x 部分的水位高度为 $y$y 时，需要找到往左往右扩展多少。即找到左边第一块高度大于 $y$y 的板，右边第一块高度大于 $y$y 的板，记这个区间为 $[l,r]$[l,r]。如果当前 $x$x 部分的水位高度为 $y$y，那么 $[l,r]$[l,r] 的水位高度也应该为 $y$y。我们记 $[l,r]$[l,r] 区间水位小于等于 $y$y 且 $z=0$z=0 的数量 $cnt1$cnt1，这一部分由真变假。我们记 $[l,r]$[l,r]区间水位小于等于 $y$y 且 $z=1$z=1 的数量为 $cnt2$cnt2，这一部分由假变真。那么 $cnt2-cnt1$cnt2−cnt1 就是对答案的贡献。

具体实现时，我们对每一部分 $x$x ，开一个小根堆 $q\left[x\right]$q[x] 维护 $z=0$z=0 的 $y$y 的值。
开一个数组 $sub\left[x\right]$sub[x] 维护，到当前 $y$y 为止有多少变假， $add\left[x\right]$add[x] 维护到当前 $y$y 为止有多少变真。如果 $add\left[x\right]>sub\left[x\right]$add[x]>sub[x]，那么就说明当前部分取 $y$y 高度更优，我们令 $ans+=add\left[x\right]-sub\left[x\right]，add\left[x\right]=0,sub\left[x\right]=0$ans+=add[x]−sub[x]，add[x]=0,sub[x]=0，表示我们这一部分取水位高度 $y$y，之后的操作均在水位高度 $y$y 上进行。

在合并两个部分 $x,y$x,y时， $q\left[x\right],q\left[y\right],sub\left[x\right],sub\left[y\right],add\left[x\right],add\left[y\right]$q[x],q[y],sub[x],sub[y],add[x],add[y] 均需要合并。
其中 $sub\left[x\right],sub\left[y\right],add\left[x\right],add\left[y\right]$sub[x],sub[y],add[x],add[y] 可以 $O\left(1\right)$O(1) 合并，小根堆我们启发式合并。

时间复杂度 $O\left(nlo{g}^{2}n\right)$O(nlog2n)。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<set>
#include<ctime>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const double alpha=0.75;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=200100;
const int maxm=100100;
const int maxp=100100;
const int up=1100;



int l[maxn],r[maxn],h[maxn],lh[maxn],rh[maxn];
int f[maxn];
priority_queue<int>q[maxn];
vector<pair<int,int> >vc;
int sub[maxn],add[maxn];

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

int _merge(int x,int y)
{
    if(q[x].size()>q[y].size()) swap(x,y);
    add[y]+=add[x],sub[y]+=sub[x];
    while(q[x].size())
        q[y].push(q[x].top()),q[x].pop();
    if(x<y)
        lh[y]=lh[x],r[l[x]]=y,l[y]=l[x];
    else rh[y]=rh[x],l[r[x]]=y,r[y]=r[x];
    f[x]=y;
    return y;
}

int main(void)
{
    int tt;
    scanf("%d",&tt);
    int pp=0;
    while(tt--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        vc.clear();
        //l[i] 第i个桶左边第一个桶
        //r[i] 第i个桶右边第一个桶
        //lh[i] 第i个桶左侧板的高度
        //rh[i] 第i个桶右侧板的高度
        for(int i=1;i<n;i++)
        {
            l[i+1]=i,r[i]=i+1;
            scanf("%d",&h[i]);
            lh[i+1]=h[i],rh[i]=h[i];
        }
        r[n]=l[1]=0;
        lh[1]=inf,rh[n]=inf;

        for(int i=1;i<=n;i++)
        {
            f[i]=i;
            while(q[i].size()) q[i].pop();
            sub[i]=add[i]=0;
        }

        int x,y,z;
        int ans=0;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            if(z==0) q[x].push(-y),ans++;
            else vc.pb(pr(y,x));
        }
        sort(vc.begin(),vc.end());
        for(int i=0;i<vc.size();i++)
        {
            int xx=fi(vc[i].second),yy=vc[i].first;
            while(lh[xx]<=yy) xx=_merge(l[xx],xx);
            while(rh[xx]<=yy) xx=_merge(r[xx],xx);
            while(q[xx].size()&&(-q[xx].top())<=yy)
            {
                q[xx].pop();
                sub[xx]++;
            }
            add[xx]++;
            if(add[xx]>sub[xx])
            {
                ans+=add[xx]-sub[xx];
                add[xx]=sub[xx]=0;
            }
        }
        printf("Case #%d: %d\n",++pp,ans);
    }
    return 0;
}

但是如果要是题目卡掉 $O\left(nlo{g}^{2}n\right)$O(nlog2n) 怎么办，有什么较快的合并两个优先队列的方法吗？

好像有某种树是支持在 $O\left(logn\right)$O(logn) 时间内进行合并的优先队列---->左偏树。

好吧，和上一种方法跑的一样快。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<set>
#include<ctime>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
//#define lc (cnt<<1)
//#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const double alpha=0.75;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=200100;
const int maxm=100100;
const int maxp=100100;
const int up=1100;

struct node
{
    int val,lc,rc,dis;
    friend bool operator <(const node &a,const node &b)
    {
        return a.val<b.val;
    }
}t[maxn];
int root[maxn],cnt;


int _merge(int x,int y)
{
    if(!x||!y) return x+y;
    if(t[x].val>t[y].val) swap(x,y);
    t[x].rc=_merge(t[x].rc,y);
    if(t[t[x].lc].dis<t[t[x].rc].dis) swap(t[x].lc,t[x].rc);
    t[x].dis=t[t[x].rc].dis+1;
    return x;
}

int newtree(int x)
{
    ++cnt;
    t[cnt].lc=t[cnt].rc=t[cnt].dis=0;
    t[cnt].val=x;
    return cnt;
}

int tadd(int x,int val)
{
    return _merge(x,newtree(val));
}

int del(int x)
{
    int l=t[x].lc,r=t[x].rc;
    t[x].lc=t[x].rc=t[x].dis=t[x].val=0;
    return _merge(l,r);
}


int l[maxn],r[maxn],h[maxn],lh[maxn],rh[maxn];
int f[maxn];
vector<pair<int,int> >vc;
int sub[maxn],add[maxn];

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

int __merge(int x,int y)
{
    add[y]+=add[x],sub[y]+=sub[x];
    root[y]=_merge(root[x],root[y]);
    if(x<y)
        lh[y]=lh[x],r[l[x]]=y,l[y]=l[x];
    else rh[y]=rh[x],l[r[x]]=y,r[y]=r[x];
    f[x]=y;
    return y;
}

int main(void)
{
    int tt;
    scanf("%d",&tt);
    int pp=0;
    while(tt--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        vc.clear();
        cnt=0;
        //l[i] 第i个桶左边第一个桶
        //r[i] 第i个桶右边第一个桶
        //lh[i] 第i个桶左侧板的高度
        //rh[i] 第i个桶右侧板的高度
        for(int i=1;i<n;i++)
        {
            l[i+1]=i,r[i]=i+1;
            scanf("%d",&h[i]);
            lh[i+1]=h[i],rh[i]=h[i];
        }
        r[n]=l[1]=0;
        lh[1]=inf,rh[n]=inf;

        for(int i=1;i<=n;i++)
        {
            f[i]=i;
            root[i]=0;
            sub[i]=add[i]=0;
        }
        for(int i=0;i<=m;i++)
            t[i].lc=t[i].rc=t[i].val=t[i].dis=0;

        int x,y,z;
        int ans=0;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            if(z==0) root[x]=tadd(root[x],y),ans++;
            else vc.pb(pr(y,x));
        }
        sort(vc.begin(),vc.end());
        for(int i=0;i<vc.size();i++)
        {
            int xx=fi(vc[i].second),yy=vc[i].first;
            while(lh[xx]<=yy) xx=__merge(l[xx],xx);
            while(rh[xx]<=yy) xx=__merge(r[xx],xx);
            while(root[xx]&&t[root[xx]].val<=yy)
            {
                root[xx]=del(root[xx]);
                sub[xx]++;
            }
            add[xx]++;
            if(add[xx]>sub[xx])
            {
                ans+=add[xx]-sub[xx];
                add[xx]=sub[xx]=0;
            }
        }
        printf("Case #%d: %d\n",++pp,ans);
    }
    return 0;
}