题目链接
题目
题目描述
给定一个序列，有多次询问，每次查询区间里小于等于某个数的元素的个数
即对于询问 \((l,r,x)\) ，你需要输出 \(\sum_{i=l}^{r}[a_i \le x]\) 的值
其中 \([exp]\) 是一个函数，它返回 \(1\) 当且仅当 \(exp\) 成立，其中 \(exp\) 表示某个表达式
输入描述
第一行两个整数 \(n,m\)
第二行 \(n\) 个整数表示序列 \(a\) 的元素，序列下标从 \(1\) 开始标号，保证 \(1 ≤ a_i ≤ 10^5\)
之后有 \(m\) 行，每行三个整数 \((l,r,k)\) ，保证 \(1 ≤ l ≤ r ≤ n\) ，且 \(1 ≤ k ≤ 10^5\)
输出描述
对于每一个询问，输出一个整数表示答案后回车
示例1
输入
5 1
1 2 3 4 5
1 5 3
输出
3
备注
数据范围
\(1 ≤ n ≤ 10^5\)
\(1 ≤ m ≤ 10^5\)
题解
知识点：树状数组，离线。
我们可以类比逆序对问题，求一个数 \(a_i\) 贡献的逆序对个数的公式 \(\displaystyle \sum_{j \leq i} [a_j > a_i]\) ，其中我们规定了 \(i\) 的枚举方向是从左到右，如此保证了 \(j\leq i\) 的偏序排除了干扰信息，再用数据结构维护 \([a_j > a_i]\) 的计算。同样的，我们可以把这个经典的公式变个形， \(\displaystyle \sum_{a_j > a_i} [j \leq i]\) ，也是同样可行的，我们从大到小枚举 \(a\) 保证 \(a_j > a_i\) 的偏序，再用数据结构维护 \([j \leq i]\) 的计算即可。
可以看出二维偏序问题中，离线将输入按照某偏序条件排序再枚举，等价于用了时间轴维护这个偏序，如此我们就可以使用线性数据结构（树状数组、线段树等）维护另一维偏序。
回到原问题，对于一个询问 \((l,r,x)\) 我们要计算 \(\displaystyle \sum_{i=l}^{r}[a_i \le x]\) ，我们可以转化为 \(\displaystyle \sum_{a_i \leq x} [l \leq i \leq r]\) 。我们可以利用时间轴维护 \(a_i < x\) 这个偏序，即将询问按 \(x\) 从小到大排序并枚举，随后用树状数组维护数字出现的区间查询即可。
但是显然，时间轴维护 \(l \leq i \leq r\) 不是那么显然，因为这不是单纯的一个偏序关系，其具有下界，需要维护数据的时效性。一个朴素的做法是带修莫队 \(O(n^{\frac{5}{3}})\) ，能过但很慢（我也不会qwq。另一个做法就是主席树，能天然维护这种关系（我更不会qwq。
时间复杂度 \(O((n+m) \log n + m \log m)\)
空间复杂度 \(O(n+m)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T>
class Fenwick {
int n;
vector<T> node;
public:
Fenwick(int _n = 0) { init(_n); }
void init(int _n) {
n = _n;
node.assign(n + 1, T());
}
void update(int x, T val) { for (int i = x;i <= n;i += i & -i) node[i] += val; }
T query(int x) {
T ans = T();
for (int i = x;i;i -= i & -i) ans += node[i];
return ans;
}
T query(int x, int y) {
T ans = T();
ans += query(y);
ans -= query(x - 1);
return ans;
}
};
struct T {
int sum = 0;
T &operator+=(const T &x) { return sum += x.sum, *this; }
T &operator-=(const T &x) { return sum -= x.sum, *this; }
};
pair<int, int> a[100007];
struct Query {
int l, r, x, id;
}q[100007];
int ans[100007];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1;i <= n;i++) {
int x;
cin >> x;
a[i] = { x,i };
}
for (int i = 1;i <= m;i++) {
int l, r, x;
cin >> l >> r >> x;
q[i] = { l,r,x,i };
}
sort(a + 1, a + n + 1, [&](auto a, auto b) {return a.first < b.first;});
sort(q + 1, q + m + 1, [&](auto a, auto b) {return a.x < b.x;});
int pos = 1;
Fenwick<T> fw(n);
for (int i = 1;i <= m;i++) {
while (pos <= n && a[pos].first <= q[i].x) {
fw.update(a[pos].second, { 1 });
pos++;
}
ans[q[i].id] = fw.query(q[i].l, q[i].r).sum;
}
for (int i = 1;i <= m;i++) cout << ans[i] << '\n';
return 0;
}
