yukicoder : No.3330 Many Point Chmax Range Sum

結果的にそこまでコードは長くないが、AC数は少ない。
https://yukicoder.me/problems/no/3330

問題

整数列Aと以下のK種の操作が与えられる。

• 操作iは(P[i],X[i])で定義される。A[P[i]]を、max(A[P[i]],X[i])で上書きする。

以下のQ個のクエリに答えよ。

• 操作のうち区間[U,D]を適用したとき、sum(A[L..R])を答えよ。

解法

操作は順番を問わない点に留意。

総和についてはBITで算出する。
Mo's Algorithmを使い、BITを更新したり戻したりしながら、クエリを処理しよう。

操作の区間[U,D]がブロック長B以下の場合は、愚直に処理しよう。
nB≦L[i]＜(n+1)B≦R[i] となるようなクエリiをまとめて処理することを考える。
クエリをR[i]順にソートしておく。
そして区間[(n+1)B,R[i]]の操作について、順次BITを更新していく。
さらにクエリ毎に[L[i],(n+1)B)の操作を適用してBITを更新して解を求め、その分を巻き戻そう。

そうすると巻き戻し回数がクエリあたりBで済むので、ブロック長Bを√N程度に抑えておけばBITの更新回数を抑えられる。

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,18> bt;

int N,K,Q;
int A[151515],M[151515],C[151515];
int P[151515],X[151515];
int L[151515],R[151515],D[151515],U[151515];

const int DI=400;
vector<pair<int,int>> ev[DI];
ll ret[151515];

void setv(int i,int v) {
	if(v!=C[i]) {
		bt.add(i,v-C[i]);
		C[i]=v;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>Q;
	FOR(i,N) {
		cin>>A[i];
		setv(i,A[i]);
	}
	FOR(i,K) {
		cin>>P[i]>>X[i];
		P[i]--;
	}
	FOR(i,Q) {
		cin>>L[i]>>R[i]>>D[i]>>U[i];
		L[i]--,D[i]--;
		if(R[i]-L[i]<DI+10) {
			for(j=L[i];j<R[i];j++) {
				if(X[j]>C[P[j]]) setv(P[j],X[j]);
				ret[i]=bt(U[i]-1)-bt(D[i]-1);
			}
			for(j=L[i];j<R[i];j++) setv(P[j],A[P[j]]);
		}
		else {
			ev[L[i]/DI].push_back({R[i],i});
		}
	}
	FOR(i,DI) {
		FOR(j,N) {
			M[j]=A[j];
			setv(j,M[j]);
		}
		sort(ALL(ev[i]));
		int CR=(i+1)*DI;
		FORR2(r,x,ev[i]) {
			int TR=R[x];
			while(CR<TR) {
				if(X[CR]>M[P[CR]]) {
					M[P[CR]]=X[CR];
					setv(P[CR],X[CR]);
				}
				CR++;
			}
			for(j=L[x];j<(i+1)*DI;j++) {
				if(X[j]>C[P[j]]) setv(P[j],X[j]);
			}
			ret[x]=bt(U[x]-1)-bt(D[x]-1);
			for(j=L[x];j<(i+1)*DI;j++) setv(P[j],M[P[j]]);
			
		}
		
	}
	FOR(i,Q) cout<<ret[i]<<endl;
	
}

まとめ

このテクは覚えておこう。