二分答案(二分没冲突的前Q-1个问题),用并查集判定(用法同bzoj 1576)
假设一个询问区间[l,r],最小干草堆数目是A,我们可以得出[l,r]上的干草堆数目都>=A。
二分出mid后,把1~mid个询问按照最小干草数量A降序排序。。如果这些询问的回答自相矛盾的话,就存在一个询问区间[l,r],它的每个位置都存在于之前的询问区间(指那些A值比当前A值大的区间)中。也就是说根据以前的询问我们得出[l,r]里面任何一堆干草数目都大于当前的A值,那就自相矛盾了。(注意如果多个区间A值相同的话就取交集。
就变成判断一段区间是否已被完全覆盖。。那就可以上并查集了。fa[i]表示i点所在的被覆盖的区间的左端点。
这样的话是O(nlogQ*alpha(n))的。。我们可以离散化一下。。因为只要知道当前区间中是否存在一个点没被覆盖过,所以只要从离散化后相邻两个值中多拿出一个点做代表就行了(前提是相邻的差值>1)。这样就只剩4*Q堆干草了。
卡了半天常。。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
struct zs{
int l,r,id,mn;
}q[];
int fa[],now[],map[],L[],R[],mp[];
int j,k,n,m,l,r,mid,tot,premx,mnx,mny,mxx,mxy;
bool flag;
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
bool cmp(zs a,zs b){return a.mn>b.mn;}
inline bool can(int x){
register int i,j,k;now[]=;
for(i=;i<=m;i++)if(q[i].id<=x)L[++now[]]=q[i].l,R[now[]]=q[i].r,now[now[]]=i;
memset(fa,,(premx+)<<);premx=;
for(i=;i<=now[];i=j+){
for(j=i;j<now[]&&q[now[j+]].mn==q[now[i]].mn;j++);
mnx=mny=tot;mxx=mxy=;
for(k=i;k<=j;k++){
if(L[k]<mnx)mnx=L[k];if(L[k]>mxx)mxx=L[k];if(R[k]<mny)mny=R[k];if(R[k]>mxy)mxy=R[k];
}
for(flag=,k=mny;k>=mxx;k=fa[k]-)
if(!fa[k]){flag=;break;}
if(!flag)return ;
if(mxy>premx)premx=mxy;
for(k=mxy;k>=mnx;k--)
if(!fa[k])fa[k]=mnx;
else{k=fa[k];if(k>=mnx)fa[k]=mnx;}
}
return ;
}
inline int get(int x){
l=;r=tot;
while(l<r){
mid=(l+r+)>>;
if(mp[mid]>x)r=mid-;else l=mid;
}return l;
}
int main(){
register int i;
n=read();m=read();tot=m<<;
for(i=;i<=m;i++)q[i].l=map[i]=read(),q[i].r=map[i+m]=read(),q[i].mn=read(),q[i].id=i;
sort(map+,map++tot);int tmp=;
for(i=;i<=tot;i++)if(map[i]!=map[i-])map[++tmp]=map[i];tot=tmp;tmp=;
for(i=;i<=tot;i++)if(map[i]+<map[i+])mp[++tmp]=map[i],mp[++tmp]=map[i]+;else mp[++tmp]=map[i];
tot=tmp;
for(i=;i<=m;i++)q[i].l=get(q[i].l),q[i].r=get(q[i].r);
sort(q+,q++m,cmp);
l=;r=m;
while(l<r){
mid=(l+r+)>>;
if(can(mid))l=mid;else r=mid-;
}
if(l==m)puts("");else printf("%d\n",l+);
return ;
}
UPD:妈呀之前有个地方大和小打反了>_<..已更正
UPD2: 还需要特判 值不够用的情况..因为数字互不相同&上限是10^9。
一个询问(L,R,A)意味着这个区间里有R-L+1个>=A的数...数据(可能出题人也)没有考虑到这部分..
正常版本见51nod1336。有个做法是二分图匹配,不过复杂度感人。