阅读量:0
题意：有n个怪物，每个怪物都有一个等级，主角从左到右打怪物，如果主角的等级严格大于了怪物的等级，那么怪物就会逃跑，主角每升一级需要杀死k个怪物，多组询问题目给出第几个怪物和升级一次需要杀死的怪物，问主角能不能和这个怪物战斗？
思路：二分+树状数组。可以发现一个明显的规律，如果k越小那么，主角升级的一定越快，那么主角从1到i(i代表题目里面问能不能战斗的怪物的位置)，可以发现是具有单调性的，那便是k大于等于某个值之后，主角一定和怪物战斗，那么就可以二分的寻找这个最小的k。二分最重要的就是检查中间值是否合理了，每次check的是时候，去比较一下当前怪物等级*mid和k=mid的时候前面能够杀死几个怪物，当前怪物等级*mid这个很容易就可以得到，后者因该如何得到呢？可以每次二分结束后将值放入树状数组里面维护，如果下一次给出的mid大于等于当前点的结果，那么这个怪物就可以提供贡献，然后查询一下大于mid的怪物有多少个，就可以了。每个点拿数组在记录一下，对于每组询问判断一下题目给出的k是大于等于求出来的还是小于求出来的。
//冷静，冷静，冷静 //调不出来就重构 #pragma GCC optimize(2) #pragma GCC optimize("O3") #include<bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pii; const int N=1e6+10,mod=1000000007; ll t[N],p[N],op[N]; ll lowbit(ll x){return x&(-x);} void add(ll x,ll vel) { while(x<N) { t[x]+=vel; x+=lowbit(x); } } ll query(ll x) { ll ans=0; while(x) { ans+=t[x]; x-=lowbit(x); } return ans; } bool is(ll x,ll v) { return p[x]*v>query(v);//v为每次升级需要杀死的怪物，p[x]为当前怪物的等级，杀死v*p[x]主角的等级就会超过p[x] //query(v)是查询v情况下，能够杀死几只怪物 } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); ll n,q;cin>>n>>q; for(int i=1;i<=n;i++) { cin>>p[i]; ll l=1,r=n+10;//二分出能和当前怪物战斗的最下k while(l+1<r) { ll mid=l+r>>1; if(is(i,mid))r=mid; else l=mid; } if(is(i,l))r=l; op[i]=r; add(r,1);//把能和当前怪物战斗的最小k放入树状数组里面 } while(q--) { ll x,v;cin>>x>>v;//如果v大于等于当前位置的最小k那么就是yes if(op[x]<=v)cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; } 