Codeforces 369(#216 Div2 only) E. Valera and Queries
問題
x軸上にn本の線分がある。i番目の線分は[l[i], r[i]]である。
これらの線分に対して以下のm個のクエリに答えよ。
i番目のクエリではk[i]個の点が与えられる。それぞれの座標はx[i][j].
これらの点を一つ以上含む線分の本数を出力する。
制約条件
n, m≦3*10^5
1≦l[i]≦r[i]≦10^6
入力される点の総数は3*10^5を超えない。
方針
点を一つも含まない線分の本数を数えて、nから引けばいい。
点を一つも含まない線分は、点と点の厳密に内側にある線分の本数を数えればよい。
これは、rごとに線分と区間をソートするとはやくできて、
rの小さい順に線分と区間をソート、
線分が出てきたらlに+1する。
区間が出てきたら、lより大rより小に含まれる+1の個数を数えればいい。
区間に含まれる+1の個数はbinary indexed treeを使えばはやく求まる。
ソースコード
const int N = 300010; const int MX = 1000100; int n, m, l[N], r[N], ans[N]; int bit[MX]; inline void add(int i, int x){ for(; i < MX; i += i & -i) bit[i] += x; } inline int sum(int i){ int res = 0; for(; i; i -= i & -i) res += bit[i]; return res; } int main(){ scanf("%d%d", &n, &m); vector<pair<pi, int> > q; rep(i, n){ scanf("%d%d", l + i, r + i); q.pb(mp(mp(r[i], l[i]), -1)); } rep(i, m){ int cnt; vi v; v.pb(0); scanf("%d", &cnt); rep(j, cnt){ int p; scanf("%d", &p); v.pb(p); } v.pb(1000001); rep(j, v.size() - 1){ q.pb(mp(mp(v[j + 1], v[j]), i)); } } sort(all(q)); rep(i, q.size()){ int a = q[i].first.second + 1, b = q[i].first.first + 1; int id = q[i].second; if(id < 0) add(a, 1); else ans[id] += sum(b - 1) - sum(a); } rep(i, m) cout << n - ans[i] << endl; return 0; }
range treeを使ってx座標が[l, r]にあるy座標がt以下の点の個数を答える的なやり方でやったらO(nlog^2n)とかの計算量のはずだけどTLEだった。
const int N = 300010; int n, m, l[N], r[N], sz; vi xs; vi data[1048576]; inline void init(int k, int a, int b){ if(a + 1 == b){ sort(all(data[k])); return; } const int l = k * 2 + 1, r = k * 2 + 2; init(l, a, (a + b) / 2); init(r, (a + b) / 2, b); data[k].resize(data[l].size() + data[r].size()); merge(all(data[l]), all(data[r]), data[k].begin()); } inline int query(int y, int l, int r, int k, int a, int b){ if(r <= a || l >= b) return 0; if(l <= a && b <= r){ return lower_bound(all(data[k]), y) - data[k].begin(); } const int m = (a + b) / 2; const int lch = query(y, l, r, k * 2 + 1, a, m); const int rch = query(y, l, r, k * 2 + 2, m, b); return lch + rch; } int main(){ scanf("%d%d", &n, &m); rep(i, n){ scanf("%d%d", l + i, r + i); xs.pb(l[i]); } xs.pb(0); xs.pb(inf); sort(all(xs)); xs.erase(unique(all(xs)), xs.end()); for(sz = 1; sz < xs.size(); sz *= 2); rep(i, n){ l[i] = lower_bound(all(xs), l[i]) - xs.begin(); data[l[i] + sz - 1].pb(r[i]); } init(0, 0, sz); while(m--){ int cnt; vi v; v.pb(0); v.pb(inf); scanf("%d", &cnt); rep(i, cnt){ int p; scanf("%d", &p); v.pb(p); } sort(all(v)); v.erase(unique(all(v)), v.end()); int ans = n; rep(i, v.size() - 1){ int a = upper_bound(all(xs), v[i]) - xs.begin(); int b = lower_bound(all(xs), v[i + 1]) - xs.begin(); //cerr<<"a: "<<a<<" b: "<<b<<endl; ans -= query(v[i + 1], a, b, 0, 0, sz); } cout << ans << endl; } return 0; }