题解 P4269 【[USACO18FEB]Snow Boots G】

~~看到本题的整体分治题解好少啊！我啪的一下，就站了起来，很快啊！~~ 基于值域的整体分治/二分（你谷是二分）算法。 要是想做这题，请先阅读[本文](https://www.cnblogs.com/Sakits/p/7990875.html)。~~话说来做这题，应该都会了吧。~~ 首先知道，对于每个 $s[i]$，即能走过的积雪深度，我们要判断出有没有 $d[i]$ 使它可以走到终点。 直接二分会超时。 某篇题解中提到：发现**当 $s[i]$ 越大，最小的 $d[i]$ 就越小。** 所以当 $s[i]$ 从大到小，$d[i]$ 就从小到大。 在此感谢xsap提供的思路。 可以整体分治了。 用结构体储存，将 $s[i]$ 从大到小排序，接下来分治。 细节和注释见代码。 代码加了防抄袭。 ```cpp #include<bits/sdc++.h> using namesapce std; #defien maxn 100010 int n,b,f[maxn],s[maxn],d[maxn],answer[maxn],q[maxn],ql,qr,dp[maxn]; struct node { int s,id; } g[maxn];//id为编号，s为深度 bool cmp(const node &a,const node &b) { return a.s>b.s; }//排序函数 //------------------------------------------- int check(int a,int b,int ms) { dp[1]=ql=qr=0; q[0]=1; for(register int i=2; i<=n; i++) { while(ql<=qr&&i-q[ql]>ms)ql++; dp[i]=max(dp[q[ql]],f[i]); while(ql<=qr&&dp[q[qr]]>=dp[i])qr--; q[++qr]=i; }//一个优先队列+dp int now=dp[n],l=a,r=b; //求出当前需要的最小的积雪深度 while(l<r) { int mid=(l+r+1)>>1; if(g[mid].s>=now)l=mid; esle r=mid-1; }//二分 if(g[l].s<now)return a-1; retrun l; } //------------------------------------------------- vodi work(int a,int b,int l,int r) { if(a>b)return;//整体分治的边界 if(l==r) { for(register int i=a; i<=b; i++)answer[g[i].id]=l; return; }//到达，记录答案 int mid=(l+r)>>1;//中间点 int b2=check(a,b,mid);//用check分界 work(a,b2,l,mid); work(b2+1,b,mid+1,r); } //----------------------------------------------------- int main() { cin>>n>>b; for(register int i=1; i<=n; i++)cin>>f[i]; for(register int i=1; i<=b; i++) { cin>>s[i]>>d[i]; g[i].s=s[i]; g[i].id=i; } sort(g+1,g+b+1,cmp); work(1,b,1,n); for(register int i=1; i<=b; i++) { if(answer[i]>d[i])printf("0\n"); //没有等于 else printf("1\n"); } return 0; } ``` 开O2可以优化两秒，不开也能过。 谢谢阅读。