Level Up
算法
又是 Monocarp
较复杂算法(学习思路)
暴力
观察到对于每一个 \(k\) , 其最大升级次数为 \(\left\lfloor{\frac{n}{k}}\right\rfloor\)
对于所有的 \(k \in [1, n]\), 我们可以知道其升级次数为 \(\displaystyle\sum_{i = 1}^{n} {\left\lfloor{\frac{n}{k}}\right\rfloor} = n \ln n\)
考虑对 \(\text{each } k = x\), 我们求出其每一个每次升级后, 保持这个等级的升级段 \([L, R]\) , 其中, 当确定每次的 \(L =\) 上次的 \(R + 1\), \(R\) 显然二分可求, 考虑 \([L, R]\) 中等级为 \(level\) , 那么这个升级段必须满足
使用主席树等数据结构可 \(\mathcal{O}(\log n)\) check
于是求右端点为 \(\mathcal{O}(\log ^ 2 n)\) , 一共有 \(\mathcal{O}(n \ln n)\) 个升级段
总时间复杂度约为 \(\mathcal{O}(n \log^3 n)\) ( \(\ln n \approx \log_2 n\) )
总结 \(1\)T
对于这种典型的调和级数类问题, 考虑离线询问, 每一级单独运算, 这属于一个典型套路
暴力优化 1
三 \(\log\) 算法无法通过, 考虑优化掉 \(\rm{check}\)T 的 \(\log\)
容易想到前缀和优化, 令 \(sum_{i, j}\) 表示前 \(i\) 个数, 怪物等级 \(\leq j\) 的怪物个数, 那么可以预处理 \(a_i\) 值域较小的情况 (即 \(k\) 偏大), 使得 \(\mathcal{O}(1)\) check
对于 \(a_i\) 值域较大的情况, 显然此时 \(k\) 偏小, 于是可以直接枚举数列进行一个模拟
这个有点像根号分治
假设
-
\(k \geq B\) 时, 使用 \(\mathcal{O}(\frac{n ^ 2}{B})\) 的预处理, \(\mathcal{O}(n \log^2 n)\) 的回答询问
-
\(k < B\) 是, 使用 \(\mathcal{O}(nB)\) 的暴力
均值不等式求得 \(B = \sqrt{n}\), 于是总时间复杂度为 \(\mathcal{O}(n \sqrt{n} + n \log^2 n)\)
代码
#include <bits/stdc++.h>
const int MAXN = 2e5 + 20;
const int MAXSQRTN = 500;
int n, q;
int Mons_Level[MAXN];
int Sum[MAXN][MAXSQRTN]; // Sum_{i, j} 表示前 i 个数里面 <= j 的数的多少
inline int read()
{
int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
return x * w;
}
void Pre_Calc()
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= 450; j++)
{
Sum[i][j] += Sum[i - 1][j];
Sum[i][j] += (int)(Mons_Level[i] <= j);
}
}
}
std::string Brute(int Pos, int k)
{
int Now_Level = 1;
int Fight_Time = 0;
for (int i = 1; i <= Pos; i++)
{
if (Fight_Time == k)
{
Now_Level++;
Fight_Time = 0;
}
if (i == Pos)
{
if (Now_Level > Mons_Level[i])
{
return "NO";
}
else
{
return "YES";
}
}
if (Now_Level <= Mons_Level[i])
{
Fight_Time++;
}
}
return "ERROR";
}
struct node
{
int Pos;
int Num;
};
std::vector<node> Que[MAXN];
std::string Ans[MAXN];
bool cmp(node a, node b);
bool check(int k, int Left, int Right, int Now_Level)
{
return (Right - Left + 1) - (Sum[Right][Now_Level - 1] - Sum[Left - 1][Now_Level - 1]) >= k;
}
/*二分查找符合要求的 R*/
int Bin_Search(int Now_Left, int &Now_Right, int Now_Level, int k)
{
int Left = Now_Left, Right = n;
Now_Right = n;
while (Left < Right)
{
int Mid = Left + ((Right - Left) >> 1);
if (check(k, Now_Left, Mid, Now_Level))
{
Now_Right = Mid;
Right = Mid;
}
else
{
Left = Mid + 1;
}
}
return Now_Right;
}
bool cmp(node a, node b) { return ((a.Pos == b.Pos) ? (a.Num < b.Num) : (a.Pos < b.Pos)); }
int main()
{
n = read(), q = read();
for (int i = 1; i <= n; i++)
{
Mons_Level[i] = read();
}
/*预处理*/
Pre_Calc();
for (int i = 1; i <= q; i++)
{
int Pos, k;
Pos = read(), k = read();
Que[k].push_back((node){Pos, i});
}
for (int k = 1; k <= n; k++)
{
if (Que[k].empty())
continue;
int Have_Done = 0;
/*暴力处理*/
if (k <= 448)
{
for (int i = 0; i < Que[k].size(); i++)
{
Ans[Que[k][i].Num] = Brute(Que[k][i].Pos, k);
}
}
else
{
/*这里需要对查询排序*/
sort(Que[k].begin(), Que[k].end(), cmp);
int Now_Left = 1, Now_Right = -1, Now_Level = 1;
Have_Done = 0;
/*分段处理当前 k*/
while (Now_Left <= n)
{
Now_Right = Bin_Search(Now_Left, Now_Right, Now_Level, k);
while (Have_Done < Que[k].size() && Now_Left <= Que[k][Have_Done].Pos && Que[k][Have_Done].Pos <= Now_Right)
{
if (Now_Level <= Mons_Level[Que[k][Have_Done].Pos])
{
Ans[Que[k][Have_Done].Num] = "YES";
}
else
{
Ans[Que[k][Have_Done].Num] = "NO";
}
Have_Done++;
}
Now_Left = Now_Right + 1;
Now_Level++;
}
}
}
for (int i = 1; i <= q; i++)
{
std::cout << Ans[i] << '\n';
}
return 0;
}
卡卡常即可通过, 没时间了
总结 \(2\)
对于一种优化技巧, 可以使用根号分治使其达到最优
离线处理可降低需处理的可能情况总数
暴力优化 2
再可持久化线段树上进行树上二分
代码
后补: 可持久化线段树上的二分
// LUOGU_RID: 169632761
#include <bits/stdc++.h>
#define ls t[cur].lc
#define rs t[cur].rc
#define mid ((l + r) >> 1)
using namespace std;
int n, m, a[200005], top, rt[200005], p, x, ans[200005], ret;
vector<pair<int, int>> v[200005];
pair<int, int> b[200005];
struct node
{
int val, lc, rc;
} t[40000005];
int clone(int cur)
{
top++, t[top] = t[cur];
return top;
}
int build(int cur, int l, int r)
{
cur = ++top;
if (l == r)
{
t[cur].val = 0;
return cur;
}
ls = build(ls, l, mid), rs = build(rs, mid + 1, r), t[cur].val = t[ls].val + t[rs].val;
return cur;
}
int update(int cur, int l, int r, int p)
{
cur = clone(cur);
if (l == r)
{
t[cur].val = 1;
return cur;
}
if (p <= mid)
ls = update(ls, l, mid, p);
else
rs = update(rs, mid + 1, r, p);
t[cur].val = t[ls].val + t[rs].val;
return cur;
}
int find(int cur, int l, int r, int val)
{
if (l == r)
return l;
if (val <= t[ls].val)
return find(ls, l, mid, val);
else
return find(rs, mid + 1, r, val - t[ls].val);
}
void query(int cur, int l, int r, int x, int y, int &val)
{
if (!val || x > y)
return;
if (x <= l && r <= y)
{
if (val <= t[cur].val)
ret = find(cur, l, r, val), val = 0;
else
val -= t[cur].val;
return;
}
if (x <= mid)
query(ls, l, mid, x, y, val);
if (y > mid)
query(rs, mid + 1, r, x, y, val);
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i], a[i] = min(a[i], n);
rt[n + 1] = build(0, 1, n);
for (int i = 1; i <= n; i++)
b[i] = {a[i], i};
sort(b + 1, b + n + 1, greater<>());
for (int i = n, p = 1; i >= 1; i--)
{
rt[i] = rt[i + 1];
while (p <= n && b[p].first == i)
rt[i] = update(rt[i], 1, n, b[p].second), p++;
}
assert(top <= 40000000);
for (int i = 1; i <= m; i++)
cin >> p >> x, v[x].emplace_back(p, i);
for (int k = 1, p, i, tmp; k <= n; k++)
{
sort(v[k].begin(), v[k].end());
auto it = v[k].begin();
for (p = 0, i = 1;; i++)
{
tmp = k, ret = 0, query(rt[i], 1, n, p + 1, n, tmp);
if (tmp || it == v[k].end())
break;
p = ret;
while (it != v[k].end() && it->first <= p)
ans[it->second] = (a[it->first] >= i), it++;
}
while (it != v[k].end())
ans[it->second] = (a[it->first] >= i), it++;
}
for (int i = 1; i <= m; i++)
cout << (ans[i] ? "YES\n" : "NO\n");
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0), solve();
return 0;
}
总结 \(3\)
注意树上二分非常滴高效
较简单算法
感性发现, \(k\) 增大时, 显然有升级更困难
于是考虑对于每一个怪物 \(i\), 找到其阈值 \(T_i\) (当 \(k \geq T_i\) 时迎战, \(k < T_i\) 时跑路)
这个 \(T_i\) 显然可以使用二分求得, 总时间复杂度是 \(\mathcal{O} (n ^ 2 \log n)\), 而 \(check\) 函数的时间复杂度是 \(\mathcal{O}(n)\)
观察 \(check\) 函数, 发现其本质为找前面下标, 有多少已经满足条件
于是可以开一个 树状数组 , 记录当前 \(k\) 值对应满足条件的下标数, 那么每次计算之后, 从 \(T_i \rightarrow n\) 整体 \(+ 1\) (后面的显然满足阈值)
时间复杂度优化到 \(\mathcal{O}(n \log^2 n)\)
代码
#include <iostream>
#include <tuple>
using namespace std;
const int N = 2e5 + 10;
int a[N], n, q, tr[N], idx = 1, l, r, mid, req[N];
inline void update(int x, int v)
{
while (x < N)
{
tr[x] += v;
x += (x & -x);
}
}
inline int query(int x)
{
int res = 0;
while (x)
res += tr[x], x -= (x & -x);
return res;
}
inline bool check(int x, int v) // xth monster will fl, x=v
{
return 1ll * a[x] * v <= query(v);
}
int main()
{
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++)
{
scanf("%d", a + i);
}
for (int i = 1; i <= n; i++)
{
l = 1, r = n;
while (l < r)
{
mid = (l + r) >> 1;
if (check(i, mid))
l = mid + 1;
else
r = mid;
}
update(l, 1);
req[i] = l;
}
for (int i = 1, x, k; i <= q; i++)
{
scanf("%d%d", &x, &k);
puts(k < req[x] ? "NO" : "YES");
}
}
总结
当一个操作涉及到其之前的区间, 考虑用区间类数据结构 \(n \rightarrow \log n\)