hdu 5575 Discover Water Tank left-handed tree

Topic link: http://acm.hdu.edu.cn/showproblem.php?pid=5575

Topic:

Now there is a huge reservoir (which can be regarded as two-dimensional), and the middle of the reservoir is divided into n n n parts by n_1n-1n_1 baffles. You know the height of these baffles. Now you know the results of mmm detection. Each detection result is x,y,flagx,y,flagx,y,flag. Flag represents the xxx part. Whether there is water at the position of y+0.5y+0.5y+0.5, flagflag 1 means there is water, flagflag 0 means there is no water.

But some of the mmm messages you get are conflicting, some are wrong, and if you ask you the most correct questions, some of the results are correct.

Practice:

Because in doing this problem, I intentionally learned the left-leaning tree, if I don't know what the left-leaning tree is. Poke here If you can't understand it. Go and find the blog trumpet of the big man.

The approach to this question is to assume that there is no water in all places, and then update the answer from the small to the large position marked with water. If there is water in the enumeration of height h, then the anhydrous mark less than this height in the set will be subtracted from the current answer, but if the subtraction will be smaller than the original answer, then we can not subtract. Only when the number of water marks is greater than 0 (that is, when there is water, it can be more than the original answer) can we update the answer and remove all the marks (that is, we have default water here).

The general approach is the implementation of the algorithm, where the left-sided tree is used to maintain a small top heap of anhydrous height in each set. What we need to do is to find and maintain the range of the baffle that is submerged by the current water level. That is, if the baffle is 254 and the water level I enumerated in the first part is 3, then after exceeding 2, we need to merge the current situation of the first and second parts. If the current height of my water is higher than the minimum height in my collection, then delete the top heap from the left-hand tree.

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
using namespace std;
const int maxn=200005;
const int inf=(int) 2e9+7;
int lson[maxn],rson[maxn],va[maxn],sub[maxn];
int n,m,op,x,y,dis[maxn],fa[maxn],add[maxn],htop[maxn];
int lh[maxn],rh[maxn],ans,lp[maxn],rp[maxn],tot;
struct node{
    int pos,h;
    node(){}
    node(int pos,int h):pos(pos),h(h){}
    bool operator < (const node &a)const{
        return h<a.h;
    }
};
vector<node> ve;
int fin(int x){
    return fa[x]==x?x:fa[x]=fin(fa[x]);
}
int Merge(int x,int y){
    if(!x||!y) return x+y;
    if(va[x]>va[y]||va[x]==va[y]&&x>y) swap(x,y);
    rson[x]=Merge(rson[x],y);
    if(dis[rson[x]]>dis[lson[x]]) swap(rson[x],lson[x]);
    dis[x]=(rson[x]==0?0:dis[rson[x]]+1);
    return x;
}
int Delete(int x){
    int ne=Merge(lson[x],rson[x]);
    return ne;
}
int NewNode(int v){
    va[tot]=v;
    lson[tot]=rson[tot]=dis[tot]=0;
    return tot++;
}
void init(){
    ve.clear();
    rep(i,1,n){
        add[i]=sub[i]=0;
        fa[i]=i;
    }
    tot=1;ans=0;
    memset(htop,0,sizeof(htop));
}
int Un(int x,int y){
    x=fin(x),y=fin(y);
    add[y]+=add[x],sub[y]+=sub[x];
    htop[y]=Merge(htop[x],htop[y]);
    if(x<y) lp[y]=lp[x],lh[y]=lh[x],rp[lp[x]]=y;
    else rp[y]=rp[x],rh[y]=rh[x],lp[rp[x]]=y;
    fa[x]=y; return y;
}
int main(){
    int T,cas=0; scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        init();
        rep(i,2,n){
            int x; scanf("%d",&x);
            lp[i]=i-1, rp[i]=i+1;
            lh[i]=x,rh[i-1]=x;
        }
        rp[1]=2; lh[1]=rh[n]=inf;
        rep(i,1,m){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            if(z){ve.push_back(node(x,y+1));}
            else{
                htop[x]=Merge(htop[x],NewNode(y));
                ans++;
            }
        }
        sort(ve.begin(),ve.end());
        for(int i=0;i<ve.size();i++){
            int p=fin(ve[i].pos),h=ve[i].h;
            while(lh[p]<h) p=Un(lp[p],p);
            while(rh[p]<h) p=Un(rp[p],p);
            while(htop[p]&&va[htop[p]]<h){
                htop[p]=Delete(htop[p]);
                sub[p]++;
            }
            add[p]++;
            if(add[p]>sub[p]){
                ans+=add[p]-sub[p];
                add[p]=sub[p]=0;
            }
        }
        printf("Case #%d: %d\n",++cas,ans);
    }
    return 0;
}

Tags: PHP less

Posted on Tue, 13 Aug 2019 00:00:17 -0700 by jaapoost