hdu 5575 Discover Water Tank(可合并堆)

题目链接：hdu 5575 Discover Water Tank

题意：

有一个大水箱，里面有N-1个隔板，将这个大水箱分成了N个小水箱，每个隔板有一定的高度。

现在有m条信息，每条信息表示第x个水箱的y高度是否有水。

现在有一些信息有矛盾，问你最多可以选多少条信息出来，他们相互都不矛盾。

题解：

队友写了一个排序后模拟的程序，跑的飞快，hdu上第一。(不是很懂~~)

然后自己写了个n(logn)^2的预处理再模拟，然后T了，(太菜了)

然后看完网上的题解后，发现队友写的那个就是巧妙的用数组维护了堆维护的东西。

这里我还是用堆维护的，可合并堆用的pd_ds库里面的，方便快捷。

这篇写的比较详细：详细题解传送门

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 #include<ext/pb_ds/priority_queue.hpp>
 4 using namespace std;
 5 typedef long long ll;
 6 typedef pair<int,int>P;
 7 using namespace __gnu_pbds;
 8 const int N=4e5+7;
 9 P LR[N];
10 int t,n,m,h[N],f[N],cas,O[N],X[N];
11 struct Line
12 {
13     int x,y,is;
14     bool operator<(const Line &B)const
15     {    
16         if(y!=B.y)return y<B.y;
17         if(is!=B.is)return is<B.is;
18         return x<B.x;
19     }
20 }line[N];
21 __gnu_pbds::priority_queue<int,greater<int>,pairing_heap_tag>heap[N];
22 
23 int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
24 void merge(int x,int y)
25 {
26     int fx=find(x),fy=find(y);
27     if(fx!=fy)
28     {
29         f[fy]=fx;
30         LR[fx].first=min(LR[fx].first,LR[fy].first);
31         LR[fx].second=max(LR[fx].second,LR[fy].second);
32         heap[fx].join(heap[fy]);
33         O[fx]+=O[fy];
34         X[fx]+=X[fy];
35     }
36 }
37 
38 int main(){
39     scanf("%d",&t);
40     while(t--)
41     {
42         scanf("%d%d",&n,&m);
43         F(i,1,n)f[i]=i,heap[i].clear();
44         F(i,1,n-1)scanf("%d",h+i);
45         F(i,1,n)LR[i]=P(i,i),O[i]=X[i]=0;
46         int ans=0;
47         F(i,1,m)
48         {
49             scanf("%d%d%d",&line[i].x,&line[i].y,&line[i].is);
50             ans+=!line[i].is;
51             if(!line[i].is)heap[line[i].x].push(line[i].y);
52         }
53         sort(line+1,line+1+m);
54         F(i,1,m)if(line[i].is)
55         {
56             int fx=find(line[i].x);
57             while(line[i].y>=h[LR[fx].second]&&LR[fx].second+1<=n)
58                 merge(fx,LR[fx].second+1),fx=find(fx);
59             while(line[i].y>=h[LR[fx].first-1]&&LR[fx].first-1>=1)
60                 merge(fx,LR[fx].first-1),fx=find(fx);
61             while(!heap[fx].empty()&&heap[fx].top()<=line[i].y)
62                 X[fx]++,heap[fx].pop();
63             if(++O[fx]>=X[fx])
64             {
65                 ans+=(O[fx]-X[fx]);
66                 O[fx]=X[fx]=0;
67             }
68         }
69         printf("Case #%d: %d
",++cas,ans);
70     }
71     return 0;
72 }

View Code