由于没有区间被其它区间包括这个条件,也就是假设li 假如区间[l,r]都已经被覆盖,那么能够继续找一个li在[l,r]范围内的最大的一个,继续扩展覆盖的区间,然后再以相同的方式找下一个战士 这样能够依照左端点排序,然后每个战士要找的下一个战士都是确定的,然后用倍增找出一共须要多少战士就能够了 #include #include #include #include #include #include #include #include #include #include #define ll long long #define N 402020 #define pa pair using namespace std; int sc() { int i=0,f=1; char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar(); return i*f; } struct W{int l,r,p;}a[N]; int n,m,tot,fa[N][19],ans[N]; set bool cmp(W a,W b) { return a.l } void solve(int x) { int p=a[x].p,L=a[x].l+m; for(int i=18;i>=0;i--) if(fa[x][i]) if(a[fa[x][i]].r x=fa[x][i],ans[p]+=(1< } int main() { n=sc(),m=sc(); for(int i=1;i<=n;i++) { a[++tot].l=sc(),a[tot].r=sc(),a[tot].p=i;
上一篇
发表评论