战争（war）
首先，对于数据范围1<=n,k<=500000,1<=l<=r<=n,1<=p<=n，显然对每一个斥候的情报进行填充是会超时的。
题目输出第一个与前面情报矛盾的情报，即求最多不矛盾的情报个数，可以考虑二分判断到当前斥候是否合法
check
而对于每一个p，他有一个覆盖范围l——r，只要在最小范围(maxl——minr)内还有未被比他更大值的数覆盖过的点，他就有机会是不矛盾的，否则就是矛盾的，因为覆盖过的地方表示当前位置的最小值，而不可能出现比他更小，所以矛盾
所以我们倒序枚举最小人数p，若当前这个的最小范围中有值未被覆盖，就说明合法，并将他的最大范围覆盖为当前值（minl——maxr）
但其实这个做法的时间复杂度为O（nklogk），但依然通过了此题，请求加强数据，附赠一个data可以卡掉此做法太大了传不上来
//datamaker
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
int read()
{
int s=0,bj=0;
char ch=getchar();
while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return bj?-s:s;
}
void printnum(int x)
{
if(x>9)printnum(x/10);
putchar(x%10^48);
}
void print(int x,char ch)
{
if(x<0){putchar('-');x=-x;}
printnum(x);putchar(ch);
}
int main()
{
freopen("1.in","w",stdout);
cout<<500000<<" "<<500000<<endl;
for(int i=1;i<=500000;++i)
cout<<1<<" "<<500000-i+1<<" "<<i<<endl;
return 0;
}
下为此做法代码
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;
int read()
{
int s=0,bj=0;
char ch=getchar();
while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return bj?-s:s;
}
void printnum(int x)
{
if(x>9)printnum(x/10);
putchar(x%10^48);
}
void print(int x,char ch)
{
if(x<0){putchar('-');x=-x;}
printnum(x);putchar(ch);
}
int n,k;
int l[500005],r[500005],v[500005];
int mxl[500005],mnl[500005],mxr[500005],mnr[500005];
bool vst[500005],aha[500005];
void clean(){for(int i=1;i<=n;++i)mxl[i]=mnl[i]=mxr[i]=mnr[i]=vst[i]=aha[i]=0;}
bool pd(int no)
{
clean();
for(int i=1;i<=no;++i)
{
int V=v[i];
if(!aha[V])//标记是否出现过此最小值
{
aha[V]=1;
mxl[V]=mnl[V]=l[i];
mxr[V]=mnr[V]=r[i];
}
else
{
mxl[V]=max(mxl[V],l[i]);
mxr[V]=max(mxr[V],r[i]);
mnl[V]=min(mnl[V],l[i]);
mnr[V]=min(mnr[V],r[i]);//更新maxl,maxr,minl,minr
}
}
for(int i=n;i;--i)
if(aha[i])
{
int flag=1;
for(int j=mxl[i];j<=mnr[i];++j)//寻找最小范围内是否有未被覆盖的点
flag&=vst[j];
if(flag)return 0;
for(int j=mnl[i];j<=mxr[i];++j)vst[j]=1;//覆盖自己的最大范围
}
return 1;
}
int main()
{
// freopen("aha.in","r",stdin);
n=read();k=read();
for(int i=1;i<=k;++i){l[i]=read();r[i]=read();v[i]=read();}
if(pd(k)){print(k+1,'\n');return 0;}
int l=1,r=k,mid;
while(l<=r)
{
mid=(l+r)>>1;
if(pd(mid))l=mid+1;
else r=mid-1;
}
print(l,'\n');//本应是l-1，但是我们这里求出的是前l-1个满足，不满足的应是第(l-1)+1个即第l个
return 0;
}
顺带一提这个题跟[USACO08JAN]Haybale Guessing G几乎一模一样（
吐槽完数据，还是要给个正解的，与上面的方法唯一不同的是将覆盖的过程由暴力覆盖改为使用并查集，将区间里的点全部指向右端点，这样小区间中的点就会不在区间里，从而判断是否被覆盖过
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
int read()
{
int s=0,bj=0;
char ch=getchar();
while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return bj?-s:s;
}
void printnum(int x)
{
if(x>9)printnum(x/10);
putchar(x%10^48);
}
void print(int x,char ch)
{
if(x<0){putchar('-');x=-x;}
printnum(x);putchar(ch);
}
int n,m;
struct node{int l,r,num;}a[500005],b[500005];
bool cmp(node x,node y){return x.num==y.num?x.l<y.l:x.num>y.num;}
int fa[1000005];
int GF(int x){return fa[x]==x?fa[x]:fa[x]=GF(fa[x]);}
bool check(int num)
{
for(int i=1;i<=n+2;++i)fa[i]=i;
for(int i=1;i<=num;++i)b[i]=a[i];
sort(b+1,b+num+1,cmp);
int las=b[1].num;
int jl=b[1].l,bl=b[1].l,jr=b[1].r,br=b[1].r;
b[num+1].num=0;
for(int i=2;i<=num+1;++i)
{
if(b[i].num^las)
{
if(jl>jr||GF(jl)>jr)return 0;
for(int j=GF(bl);j<=br;j=GF(j+1))fa[j]=fa[j+1];
las=b[i].num;jl=br=-INF;bl=jr=INF;
}
if(b[i].num==las){jl=max(jl,b[i].l);jr=min(jr,b[i].r);bl=min(bl,b[i].l);br=max(br,b[i].r);}
}
return 1;
}
int main()
{
n=read();m=read();
for(int i=1;i<=m;++i){a[i].l=read();a[i].r=read();a[i].num=read();}
if(check(m)){print(m+1,'\n');return 0;}
int l=1,r=m,mid;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid))l=mid+1;
else r=mid-1;
}
print(l,'\n');
return 0;
}
京公网安备 11010502036488号