NC19427 换个角度思考

题目地址：

https://ac.nowcoder.com/acm/problem/19427

基本思路：

离线+树状数组，将查询离线，把待查询数组按照值从小到大排序，将查询按照x的大小从小到大排序，那么我们每次查询时先在树状数组插入比当前查询的x小的所有下标位置(因为数组是有序的所以直接接着上次的位置往后不会重复操作)，然后查询[L,R]范围内里有多少个数就是了。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define ll long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 1e5 + 10;
struct Node1{
  int id,val;
  bool operator < (const Node1 &no) const{
    return val < no.val;
  }
}a[maxn];
struct Node2{
  int id,l,r,x;
  bool operator < (const Node2 &no) const{
    return x < no.x;
  }
}b[maxn];
int n,m,x,ans[maxn];
struct BIT{
  int t[maxn << 2];
  int lowbit(int x){
    return x & (-x);
  }
  void clear(){
    memset(t,0,sizeof(t));
  }
  int sum(int x){//求和;
    int res = 0;
    while(x){
      res += t[x];
      x -= lowbit(x); 
    }
    return res;
  }
  void update(int x,int v){//更新;
    while(x <= n){
      t[x] += v;
      x += lowbit(x);
    }
  }
}bit;
signed main() {
  IO;
  cin >> n >> m;
  rep(i,1,n){
    a[i].id = i;
    cin >> a[i].val;
  }
  rep(i,1,m){
    b[i].id = i;
    cin >> b[i].l >> b[i].r >> b[i].x;
  }
  //离线排序;
  sort(a+1,a+1+n);
  sort(b+1,b+1+m);
  int p = 1;
  rep(i,1,m){
    //接着上次位置往后找就是了;
    while(a[p].val <= b[i].x && p <= n){
      bit.update(a[p++].id,1);
    }
    ans[b[i].id] = bit.sum(b[i].r) - bit.sum(b[i].l - 1);
  }
  rep(i,1,m) cout << ans[i] << '\n';
  return 0;
}