SPOJ METEORS - Meteors
問題
問題概要
ある惑星の軌道上には隕石が降り注いでくる。その軌道を個の領域に分割し、と番号をふる。このとき、番号は連続的に振られ、番目の領域と番目の領域は繋がっている。その個の領域に分けた領域に対してそれぞれつずつ拠点が設置されており、その拠点は国のものである。
それぞれの拠点では、この隕石を収集することができる。各国は隕石を個収集したいと思っている。今、隕石の落下予測が周期先のぶんまで予測されている。その予想はそれぞれの値で特徴付けられており、
- のとき、の範囲に個ずつ
- のとき、の範囲に個ずつ
隕石が降ってくることを表す。
このとき、各国が目標の隕石の個数個を収集するまでにかかる周期を求めよ。周期後にも回収しきれない場合にはNIE
と出力せよ。
アイデア
各国ごとに、どのタイミングでできるのかを知りたいとなったときに、二分探索によって探すのが良さそう。そこで、二分探索で周期番目までを見る時はクエリを最初から順番に見ていって区間に足していくということをすれば良い。
この区間に足していくという処理も愚直にやると時間がかかってしまうので、今回は自分がライブラリとして持っていたSegment Treeを少し改造したものを作って、区間に対してaddをするクエリと、ある1つの位置の値をgetするクエリのどちらもで実現出来るものを用意して処理することにした(動作については後述)。
これによって、クエリの処理は、その位置が条件を満たすかどうかの判定をにより行えるようになる。そして、これを各国に対して行うので、全体として計算量はとなって、明らかに間に合わない。
そこで、各国に対して二分探索するのではなく、この個の国を同時に処理していくParallel Binary Searchをする。結局、二分探索の部分でSegment Treeを構成しているが、これを各国ごとに毎回初めから構築しているのがとてもムダな部分になっていて、時間もかかってしまっている部分になる。そこをまとめていこうという考え方である。
今回作成したSegment Treeの挙動
今回実現したかったものは、区間に対するaddと1つの位置の値を取り出すgetがどちらもでできるようなsegtreeである。
まず、addクエリについて考えていくと、次の図のような挙動にした。範囲にすっぽり収まった時点でそこにaddして止めておくということをする。
- [3,5]に+3
- [4,8]に+5
そして、このような状態でgetしたい時には葉からスタートして真上に辿って足し上げることでその位置の値が何か、つまり今までに回収できた隕石の個数がわかるようになる。
さて、これによってsegtreeを構成する必要のある回数は回となる。その各回について、個の国のクエリを平行に分割してsegtreeを構成しつつクエリを処理する。これによって全体の計算量はとなり、間に合う。
また、クエリを処理している時、各国が回収できる隕石の個数がlong longの範囲を超えうるので、目標に到達した時点即数え上げをやめないといけないことに注意。
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second struct SumSegTree{ int n; vector<ll> dat; //初期化 SumSegTree(int _n){ n=1; while(n<_n) n*=2; dat=vector<ll>(2*n-1,0); } ll get(int idx){ idx+=n-1; ll ret=dat[idx]; while(idx>0){ idx=(idx-1)/2; ret+=dat[idx]; } return ret; } //内部的に投げられるクエリ void _query(int a, int b, ll v, int k, int l, int r){ if(r<=a || b<=l) return; if(a<=l && r<=b) dat[k]+=v; else{ _query(a,b,v,2*k+1,l,(l+r)/2); _query(a,b,v,2*k+2,(l+r)/2,r); } } //[a,b)に+v void add(int a, int b, ll v){ _query(a,b,v,0,0,n); } }; const int N=300000; int n,m,k; // stations that i-th state has vector<int> state[N]; int target[N]; int l[N],r[N]; ll a[N]; int L[N],R[N]; int main() { //input scanf(" %d %d", &n, &m); rep(i,m) { int o; scanf(" %d", &o); --o; state[o].pb(i); } rep(i,n) scanf(" %d", &target[i]); scanf(" %d", &k); rep(i,k) { scanf(" %d %d %lld", &l[i], &r[i], &a[i]); --l[i]; --r[i]; } // initialize rep(i,n) { L[i]=-1; R[i]=k; } rep(T,20) { vector<int> q[N]; rep(i,n) q[(L[i]+R[i])/2].pb(i); SumSegTree st(m+1); rep(i,k) { if(l[i]<=r[i]) st.add(l[i],r[i]+1,a[i]); else { st.add(l[i],m,a[i]); st.add(0,r[i]+1,a[i]); } rep(j,q[i].size()) { int s=q[i][j]; ll tmp=0; rep(x,state[s].size()) { tmp+=st.get(state[s][x]); if(target[s]<=tmp) break; } if(target[s]<=tmp) R[s]=i; else L[s]=i; } } } rep(i,n) { if(R[i]<k) printf("%d\n", R[i]+1); else printf("NIE\n"); } return 0; }