【每日一题】 换个角度思考 题解

太棒了, 学到了许多.jpg

Solution

题意要求 次区间查询小于等于 的数有多少个, 区间问题首先就想到线段树/树状数组
优先考虑树状数组(常数小, 写法简单), 但是我们做不到直接一边查询一边插入然后用 求解
因为原序列是无序的, 每次查询 时, 都未知, 因此很难处理
注意到问题给的区间是定的, 区间查询的先后不会影响结果
那么我们考虑一下离线操作, 对询问的值进行排序, 再对原序列按权值排序
预处理出区间 中满足题意的元素再查询
此时我们从序列中最小的元素(第一个)开始, 只要当前的值小于所查询的值
那么它就可能有贡献, 我们把它插在它原序列的位置上, 直到出现序列的值大于当前的值
我们停止插入操作, 查询 有多少元素满足条件, 此时可以转换成查询 的元素个数
注意最后答案是按原顺序输出, 如果 的话要离散化, 这道题数据范围比较友好, 省去了这一步

/*
  autor: Kurisu
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const long long inf = 1e18;
const int N = 1e5 + 5;
const double eps = 1e-10;
const ll mod = 1e9 + 7;
int t[N];
pair<int, int> a[N];
int lowbit(int x) {
  return x & (-x);
}
void update(int x, int add) {
  while(x < N) {
    t[x] += add, x += lowbit(x);
  }
}
int get_sum(int x) {
  int res = 0;
  while(x) {
    res += t[x];
    x -= lowbit(x);
  }
  return res;
}
struct node {
  int l, r, val, i;
  bool operator < (const node &s) const {
    return val < s.val;
  }
}query[N];
int ans[N];
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  for(int i = 1; i <= n; i++) cin >> a[i].first, a[i].second = i;
  sort(a + 1, a + 1 + n);
  for(int i = 1; i <= m; i++) {
    cin >> query[i].l >> query[i].r >> query[i].val;
    query[i].i = i;
  }
  sort(query + 1, query + 1 + m);
  int cur = 1;
  for(int i = 1; i <= m; i++) {
    int val = query[i].val;
    while(cur <= n && a[cur].first <= val) {
      update(a[cur].second, 1);
      ++cur;
    }
    ans[query[i].i] = get_sum(query[i].r) - get_sum(query[i].l - 1);
  }
  for(int i = 1; i <= m; i++) {
    cout << ans[i] << "\n";
  }
  return 0;
}