yukicoder : No.3265 地元に帰れば天才扱い！

方針はすぐ立つけど、実装の細かいところを詰めるのに手間取る。
https://yukicoder.me/problems/no/3265

問題

M個の家がある。
初期状態で1～N番の家に人が住んでおり、そのレートはA[i]である。
各人の天才度は、家jに住んでる人のレートをB[j] (人が住んでいないとき、0とする)とすると、家の区間[L[i],R[i]]に対し(A[i]-B[j])の総和となる。

以下のクエリが与えられるので、全体の天才度の合計を求めよ。

• 人Xが、家Yに移動する。また、その区間L[X]、R[X]を更新する。

解法

人がXが家Yに移動すると、他の人の天才度計算においてB[j]の値が変化する。
また、L[X],R[X]が変化するので人Xの天才度も変化する。
クエリ毎にそれぞれ差分を求めよう。

後者は、区間和を取れるBITやSegTreeを用いればよい。
前者は、各家が、何人の区間に覆われているかを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> num,sum;

int N,M;
ll A[202020],P[202020],L[202020],R[202020];
int Q;
int X,Y,U,V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	ll ret=0;
	FOR(i,N) {
		cin>>A[i]>>L[i]>>R[i];
		P[i]=i+1;
		ret+=A[i]*(R[i]-L[i]+1);
		num.add(L[i],1);
		num.add(R[i]+1,-1);
		sum.add(i+1,A[i]);
	}
	FOR(i,N) {
		ret-=sum(R[i])-sum(L[i]-1);
	}
	
	
	cin>>Q;
	while(Q--) {
		cin>>X>>Y>>U>>V;
		X--;
		ret-=A[X]*(R[X]-L[X]+1);
		num.add(L[X],-1);
		num.add(R[X]+1,1);
		ret+=num(P[X])*A[X];
		ret+=sum(R[X])-sum(L[X]-1);
		sum.add(P[X],-A[X]);
		
		
		P[X]=Y;
		L[X]=U;
		R[X]=V;
		
		sum.add(P[X],A[X]);
		ret+=A[X]*(R[X]-L[X]+1);
		ret-=sum(R[X])-sum(L[X]-1);
		ret-=A[X]*num(P[X]);
		num.add(L[X],1);
		num.add(R[X]+1,-1);
		cout<<ret<<endl;
	}
	
}

まとめ

こういうの計算の順番とかちょくちょく戸惑うんだよな。