题目:
http://acm.hdu.edu.cn/diy/diy_previewproblem.php?cid=30741&pid=1004
http://cogs.pro/cogs/problem/problem.php?pid=1407
The water tank has an infinite height, but with a narrow bottom. The length of the tank is
and the width is only
Now
has divided the tank into
each with an
Boards may have different heights. Water cannot flow through the boards, but can run freely if the water level is higher, following the basic physical rules.
The Frog King wants to know more details of the tank, so he sent someone to choose
and find whether there’s water at that position.
For example, each time he’ll choose
checking the
of the tank(
counting from left to right, and find whether there’s water at height
Now the King gets
but he finds some of them might be wrong. The King wants to find out the maximum possible number of the correct results.
题解:
代码:
#include#include #include #include #include #include using namespace std; typedef multiset ::iterator ITER; const int SIZEN=100010; const int INF=0x7fffffff/2; void printset(multiset s){ for(ITER key=s.begin();key!=s.end();key++){cout<<(*key)<<" ";}cout< >=1;} if(ans<0) ans=0; return ans; } int ST[20][SIZEN]; void build_st(int a[],int n){ int m=log2(n); for(int i=0;i a[q]?p:q); } } } } int RMQ(int a[],int l,int r){ int m=log2(r-l+1); int p=ST[m][l],q=ST[m][r-(1< a[q]?p:q; } int N; int H[SIZEN]; multiset SL[SIZEN],SH[SIZEN]; int calc(multiset &sl,multiset &sh,int high){//l:0,h:1 ITER key1=sl.begin(),key2=sh.begin(); int now=sl.size(),ans=now; for(;key1!=sl.end()&&(*key1)<=high;key1++){ while(key2!=sh.end()&&(*key1)>=(*key2)) now++,key2++; ans=max(ans,now); now--; } key1=sl.begin(),key2=sh.begin(); now=sl.size(); for(;key2!=sh.end()&&(*key2)<=high;key2++){ now++; while(key1!=sl.end()&&(*key2)>(*key1)) now--,key1++; ans=max(ans,now); } return ans; } int merge(int a,int b,int lim,int &cnt){ if(SL[a].size()+SH[a].size()>SL[b].size()+SH[b].size()) swap(a,b); for(ITER key=SL[a].begin();key!=SL[a].end();key++){ if((*key)>lim) SL[b].insert(*key); } for(ITER key=SH[a].begin();key!=SH[a].end();key++){ if((*key)>lim) SH[b].insert(*key); else cnt++; } for(ITER key=SL[b].begin();key!=SL[b].end();){ ITER key1=key;key1++; if((*key)<=lim){ SL[b].erase(key); key=key1; } else break; } for(ITER key=SH[b].begin();key!=SH[b].end();){ if((*key)<=lim){ ITER key1=key;key1++; SH[b].erase(key); key=key1; cnt++; } else break; } return b; } int DQ(int a,int b,int mx,int &s,int &cnt){ if(a==b){ cnt=0; s=a; return calc(SL[a],SH[a],mx); } int p=RMQ(H,a,b-1); int ans=0; int s1,s2,cnt1,cnt2; ans=DQ(a,p,H[p],s1,cnt1)+DQ(p+1,b,H[p],s2,cnt2); cnt=cnt1+cnt2; s=merge(s1,s2,H[p],cnt); ans=max(ans,calc(SL[s],SH[s],mx)+cnt); return ans; } void read(void){ int Q; scanf("%d%d",&N,&Q); for(int i=1;i