yukicoder : No.789 範囲の合計

なぜ今この問題？という気はする。
https://yukicoder.me/problems/no/789

問題

10^9要素の数列Aがあるとする。
以下のクエリを順次答えよ。

• 入力x,yに対し、A[x]にyを加算する。
• 入力L,Rに対し、A[L..R]の総和を求め、解に加える。

解法

クエリを先読みして座標圧縮すれば、単純なBITの問題に落とし込める。
動的にエントリを作るSegTreeでもよい。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,20> bt;

int N;
int A[101010],B[101010],C[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<int> cand;
	cin>>N;
	ll ret=0;
	FOR(i,N) {
		cin>>A[i]>>B[i]>>C[i];
		if(A[i]==0) {
			cand.push_back(B[i]);
		}
		else {
			cand.push_back(B[i]);
			cand.push_back(C[i]);
		}
	}
	sort(ALL(cand));
	cand.erase(unique(ALL(cand)),cand.end());
	FOR(i,N) {
		if(A[i]==0) {
			x=lower_bound(ALL(cand),B[i])-cand.begin();
			bt.add(x,C[i]);
		}
		else {
			x=lower_bound(ALL(cand),B[i])-cand.begin();
			y=lower_bound(ALL(cand),C[i])-cand.begin();
			ret+=bt(y)-bt(x-1);
		}
	}
	cout<<ret<<endl;
}

まとめ

★3の中では簡単だけど、BITと座標圧縮あると★2.5はつらいのかな？