yukicoder : No.3494 一点挿入区間和取得

これはどうにか解けた。
https://yukicoder.me/problems/no/3494

問題

N要素の整数列Aと、Q個のクエリが与えられる。
各クエリに順次答えよ。

• クエリは(i,x,L,R)で与えられる。
  • Aのi要素目の後ろに値xを挿入後、A[L]...A[R]の和を答えよ。

解法

クエリを逆順に見ていき、最終的なAの各要素がどのタイミングで挿入されるかを求めよう。
これは有効な要素のbitmapをBITで表現し、二分探索すれば求められる。

その後、また順番にクエリを実行していけばよい。
区間和なのでこちらもBITで計算できる。

int N,Q;
int A[808080];
int P[202020],X[202020],L[202020],R[202020],pos[202020];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[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) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	void set(int e,V v) { add(e,v-val[e]);}
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};
BIT<ll,20> num,sum;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>A[i];
	FOR(i,Q) {
		cin>>P[i]>>X[i]>>L[i]>>R[i];
	}
	FOR(i,N+Q) num.add(i,1);
	for(i=Q-1;i>=0;i--) {
		pos[i]=num.lower_bound(P[i]+1);
		num.add(pos[i],-1);
	}
	FOR(i,N) {
		x=num.lower_bound(i+1);
		sum.add(x,A[i]);
	}
	FOR(i,Q) {
		num.add(pos[i],1);
		sum.add(pos[i],X[i]);
		x=num.lower_bound(L[i]);
		y=num.lower_bound(R[i]);
		cout<<sum(y)-sum(x-1)<<endl;
	}
}

まとめ

そこまでコードは長くならずに済んだ。