JOI春合宿2008 Day4 Typhoon

解法

適当に座標圧縮してセグ木に台風の情報を持たせれば通る問題。
持たせ方に迷ったけど、そのまま節に突っ込めばO(Qlog(N+Q)logK)くらいになっていい感じになることに気づいた。
台風が小さい方から追加していけば節の台風の番号群は昇順になるから、それからクエリごとにセグメントツリー的に範囲を二分していって、二分探索してサイズを求めれば良さがある。

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef pair< int, int > Pi;
typedef pair< int, Pi > Pii;
 
vector< int > nums;
int n, m, k, a[100000], b[100000];
int p[100000], q[100000], r[100000];
 
const int sz = 1 << 19;
vector< int > seg[2 * sz + 1]; 
 
void add(int a, int b, int value, int k, int l, int r){
  if(a >= r || b <= l) return;
  if(a <= l && r <= b) {
    seg[k].push_back(value);
  } else {
    add( a, b, value, 2 * k + 1, l, (l + r) >> 1);
    add( a, b, value, 2 * k + 2, (l + r) >> 1, r);
  }
}
int query(int a, int b, int tA, int tB, int k, int l, int r){
  if(a >= r || b <= l) return(0);
  if(a <= l && r <= b) return(lower_bound( seg[k].begin(), seg[k].end(), tB) - lower_bound( seg[k].begin(), seg[k].end(), tA));
  return query( a, b, tA, tB, 2 * k + 1, l, (l + r) >> 1) + query( a, b, tA, tB, 2 * k + 2, (l + r) >> 1, r) + lower_bound(seg[k].begin(), seg[k].end(), tB) - lower_bound( seg[k].begin(), seg[k].end(), tA);
}
 
 
int main(){
  cin >> n >> m >> k;
  for(int i = 0; i < n; i++){
    cin >> a[i] >> b[i];
    nums.push_back(a[i]);
    nums.push_back(b[i]);
  }
  for(int i = 0; i < m; i++){
    cin >> p[i] >> q[i] >> r[i];
    nums.push_back(p[i]);
  }
  sort( nums.begin(), nums.end());
  nums.erase( unique(nums.begin(), nums.end()), nums.end());
  for(int i = 0; i < n; i++){
    a[i] = lower_bound( nums.begin(), nums.end(), a[i]) - nums.begin();
    b[i] = lower_bound( nums.begin(), nums.end(), b[i]) - nums.begin();
  }
  for(int i = 0; i < m; i++){
    p[i] = lower_bound( nums.begin(), nums.end(), p[i]) - nums.begin();
  }
  for(int i = 0; i < n; i++){
    add( a[i], b[i] + 1, i + 1, 0, 0, 1 << 19);
  }
  for(int i = 0; i < m; i++){
    cout << query( p[i], p[i] + 1, q[i], r[i] + 1, 0, 0, 1 << 19) << endl;
  }
}