如何通过E. Level Up实现技能提升？
摘要：E. Level Up 题意 玩家初始等级为 (1)， 有 (n) 只怪物，每个怪物有一个等级 (a_i), 如果怪物等级高于你，则你们会战斗，战斗后经验加1，否则怪物会逃跑，你不会获得经验，每 k 点经验就会升级。给你 (q
E. Level Up
题意
玩家初始等级为 \(1\)， 有 \(n\) 只怪物，每个怪物有一个等级 \(a_i\), 如果怪物等级高于你，则你们会战斗，战斗后经验加1，否则怪物会逃跑，你不会获得经验，每 k 点经验就会升级。给你 \(q\) 个询问，给个询问给出 \(i，x\), 问你当 \(k = x\) 时，会不会发生战斗（即问你你的等级会不会小于等于此时的\(a_i\)
\(1≤n,q≤2⋅10^5, 1≤ai≤2⋅10^5, 1≤i,x≤ n\)
听说根号分治的 sqrt 会被 hack，这里讲一个\(nlognlogn\)的做法
可以根据\(q\)，问的是到\(i\)时\(k = x\)时的\(lv\)会不会小于等于\(a_i\), 因为lv与k是反比例关系，k越小，lv就会越高，对于每个位置处理出如果能发生战斗所需要的最大的k,记为\(b_i\), 如过\(b_i <= x\), 则可以说明，比能发生战斗所需的k还大，则到这个位置的lv会比\(a_i\)还小，则会发生战斗（因为是反比例函数，你求得是最大上界，小于k的都会比\(a_i\) 大，这里要仔细想一下
因为这样k具有单调性，比当前界限大的话，lv会变小，则以后战斗的怪只会增加不会减少，我们可以二分一个最大的mid, 满足在这个位置的战斗的怪所能到达的等级小于等于\(a_i\), mid - 1位置的战斗的怪所能到达的等级都大于\(a_i\), 因为是反函数。
现在我们需要一个数据结构来维护，在一段k的范围内加 1，这里记为k能战斗的数量（经验值），询问某个位置的数量(经验值),来当作二分得\(check\)函数计算等级, 也就是区间修改和单点查询，这里可以用线段树维护(树状数组也是可以得)。最后二分出的位置记录下来，当查询的判断，修改时修改的是大于等于答案的位置，因为大于等于的位置k越大，lv越小，战斗的次数越多。多想一下边界问题
#include<bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using ll = long long;
using PII = pair<ll,ll>;
using PIII = pair<ll, pair<ll,ll>>;
#define endl "\n"
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define lowbit(x) (x) & (-x)
#define point(x) setiosflags(ios::fixed)<<setprecision(x)
const int N=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
struct Info {//一定要初始化
int val;
int add = 0;
Info (int x) {
val = x;
}
Info () {
val = 0;
}
};
Info merge(const Info& a, const Info& b) {
Info c;
c.val = b.val + c.val;
return c;
}
struct segtree {
#define ls (u << 1)
#define rs (u << 1 | 1)
int n;
segtree(int n) {init(n);};
vector<Info> info;
vector<int> a;
void init(int n) {
this->n = n;
info.resize(n << 2);
a.resize(n << 1);
}
void push_up(int u) {
info[u] = merge(info[ls], info[rs]);
}
void build(int u, int l, int r)
{
if(l == r)
{
info[u] = Info();//填值
return ;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
push_up(u);
}
void settag(int u, int k) {//处理数据
info[u].val += k;
info[u].add += k;
}
void push_down(int u)
{
if(info[u].add)
{
settag(ls, info[u].add);
settag(rs, info[u].add);
info[u].add = 0;
}
}
void update(int u, int l, int r, int pos, int k) {
if(l == r) {
info[u] = Info(k);
return;
}
push_down(u);
int mid = l + r >> 1;
if(pos <= mid) update(ls, l, mid, pos, k);
else update(rs, mid + 1, r, pos, k);
push_up(u);
};
void update(int u, int l, int r, int x, int y, int k) {
if(x <= l && r <= y) {
settag(u, k);
return;
}
push_down(u);
int mid = l + r >> 1;
if(x <= mid) update(ls, l, mid, x, y, k);
if(mid < y) update(rs, mid + 1, r, x, y, k);
push_up(u);
}
void update(int pos, int v) {
update(1, 1, n, pos, v);
}
void update(int x, int y, int k) {
update(1, 1, n, x, y, k);
}
Info query(int u, int l, int r, int x, int y) {
if (x <= l && r <= y) return info[u];
push_down(u);
int mid = l + r >> 1;
if (y <= mid) return query(ls, l, mid, x, y);
else if (mid < x) return query(rs, mid + 1, r, x, y);
else return merge(query(ls, l, mid, x, y), query(rs, mid + 1, r, x, y));
}
Info query(int l, int r) {
return query(1, 1, n, l, r);
}
};
void solve(){
int n, q;
cin >> n >> q;
vector<int> a(n + 1), b(n + 1);
for(int i = 1; i <= n; i ++) cin >> a[i];
segtree tr(n);//维护区间加，直接lazy标记就行
for(int i = 1; i <= n; i ++) {
int l = 1, r = n;
while(l < r) {
int mid = l + r >> 1;
if(tr.query(1, 1, n, mid, mid).val / mid + 1 <= a[i]) r = mid;//判断等级，单点查询
else l = mid + 1;
}
b[i] = l;
tr.update(1, 1, n, l, n, 1);
}
while(q --) {
int x, y; cin >> x >> y;
if(b[x] <= y) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
int main()
{
int T=1;
//cin>>T;
while(T--){
solve();
}
return 0;
}