JOI joisc2008_typhoon - 台風 (Typhoon)

Difficulty:None (JOI難易度:9)

問題

長さkの数列がある。はじめは全ての要素が0である。ここに区間加算クエリがN回飛んでくる。そのあと、q番目の加算クエリからr番目の加算クエリまでで数列のp番目に何回加算されたか？というクエリがM回飛んでくる。クエリを処理せよ。

解法

問題を言い換えると上のようになる。まずkが大きいので座標圧縮をする必要がある。

また、「q番目からr番目までの加算クエリ」という要求は、r番目時点の値からq-1番目時点の値を引くことで求められる。区間加算についてはBITやセグ木や遅延セグ木で実現可能。計算量は登場する数字の種類数（セグ木などの要素数）をKとして$ O((N+Q)log_2K)ぐらい。

実装

code:cpp

bool solve(){

LL(n,m,k);

vector<pair<ll,ll>>tai;

set<ll>s;

rep(i,n){

LL(a,b);

a--;

tai.pb({a,b});

s.insert(a);

s.insert(b);

}

vector<vector<tuple<ll,ll,ll>>>queries(n);

rep(i,m){

LL(p,q,r);

p--;

s.insert(p);

q--,r--;

q--;

if(q>=0)queriesq.pb({i,-1,p});

queriesr.pb({i,1,p});

}

map<ll,ll>rev;

for(auto i:s){

revi=rev.size();

}

vector<ll>ans(m);

fenwick_tree<ll>seg(rev.size());

rep(i,n){

//加算

autol,r=taii;

seg.add(revl,1);

seg.add(revr,-1);

for(autopos,dir,num:queriesi){

anspos+=dir*seg.sum(0,revnum+1);

}

rep(i,m)cout<<ansi<<endl;

return 1;

}