[题解] Educational Codeforces Round 168 (Rated for Div. 2) E - level up

链接

思路 1

注意到在 $k\in [1,n]$ 可以得到的最高等级分别为: $n,\frac{n}{2},\frac{n}{3}.....\frac{n}{n}$, 总的个数是一个调和级数, $sum=n\ast \ln n$, 完全可以处理出每个 k 下, 每一个等级时玩家对应的在哪一段.

vector<vector<pair<int, int>>>f(n + 1); //f[k,{i,j}] 对于 k,升到 i level 需要的最少长度 j.

用树状数组实时维护出当前队列内大于等于当前玩家等级的怪物的区间数量( 同权值线段树的用法 ), 注意 check 时要减去在当前位置前的等级高于等于玩家的怪物(now = -ask(l);):

int tr[200010];
void upd(int x, int val) {for (; x <= n; x += x & -x)tr[x] += val;
}
int ask(int x) {int ans = 0;for (; x; x -= x & -x)ans += tr[x];return ans;
}
int select(int l, int k, int &now) {now = -ask(l);int x = 0;for (int i = 1 << (int)log2(n); i; i /= 2) {if (x + i <= n && now + tr[x + i] <= k) {x += i;now += tr[x];}}return x;
}

  cin >> n >> q;vector<int>a(n + 1);vector<vector<int>>pos(200010); // i 的位置for (int i = 1; i <= n; ++i) {cin >> a[i];upd(i, 1);pos[a[i]].emplace_back(i);}vector<vector<pair<int, int>>>f(n + 1); //f[k,{i,j}] 对于 k,升到 i level 需要的最少长度 j.for (int i = 1; i <= n; ++i) {f[i].emplace_back(1, 0);}for (int level = 2; level <= n; ++level) {for (int k = 1; k * (level - 1) <= n; ++k) {int now = 0;int p = select(f[k].back().second, k, now);if (now < k)p++;f[k].emplace_back(level, p);}for (auto c : pos[level - 1]) {upd(c, -1);}}

处理出来 f[] 后, 对于每个输入, 只需要二分对应的 f[a[i]], 找到玩家达到 $a[i]+1$ 等级的最早位置, 小于 $i$ 的话, 玩家到达 $i$ 时等级就已经大于 $a[i]$ 了, 这个怪就会逃跑.

 while (q--) {int i, x;cin >> i >> x;auto p = upper_bound(f[x].begin(), f[x].end(), pair(a[i], LLONG_MAX));string ans;if (p == f[x].end())ans = "Yes";else {if (p->second >= i)ans = "Yes";else ans = "No";}cout << ans << endl;}

思路 2

考虑根号分治.

待补充…