E. Level Up

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;
}