HackerRank HourRank 23 : C. Selective Additions

こっちも慣れないテク。
https://www.hackerrank.com/contests/hourrank-23/challenges/selective-additions

問題

初期状態でN要素の数列Aが与えられる。
ここにM回クエリを適用していく。
各クエリでは区間[L,R]と数値Xが与えられるので、A[L...R]にそれぞれXを加算後、A全体の総和を答える。

ただし、K要素の整数集合Sが別途与えられ、A中でS中の要素と一致した値は、以降加算の影響を受けないこととする。

解法

Aの各要素が、処理途中どこかで以後影響を受けない状態になるとする。
各クエリでは、通常(R-L+1)個の要素がXだけ増えるので、総和は(R-L+1)*Xだけ増加するはずである。
しかし影響を受けない要素が存在すると、その分増加量が減る。

各要素がどこから加算の影響を受けないかがわかれば、以後BITを用いて各クエリで影響受けない要素数並びに増加量の減少分がわかる。
よって、あとは各要素が最初にS中の要素と一致した状態になるか、最短のタイミングを求めよう。

この処理は各s∈Sに対して行う。
Aの全要素について、log(M)回程度クエリを繰り返し、各要素がsを保つ最後のタイミングを並列に二分探索すればよい。

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;}
};


int N,M,K;
int A[101010],S[10];
int L[101010],R[101010],X[101010];
int mi[101010];

int LL[101010],RR[101010];
vector<int> ev[102010];
BIT<int,20> bt;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,N) cin>>A[i], mi[i]=101010;
	FOR(i,K) {
		cin>>S[i];
		FOR(j,N) if(A[j]==S[i]) mi[j]=0;
	}
	sort(S,S+K);
	FOR(i,M) {
		cin>>L[i]>>R[i]>>X[i];
		R[i]++;
	}
	
	FOR(i,K) {
		int s=S[i];
		
		FOR(j,N) LL[j]=0, RR[j]=M+1;
		
		FOR(j,20) {
			FOR(x,102000) ev[x].clear();
			ZERO(bt.bit);
			FOR(x,N) {
				ev[(LL[x]+RR[x])/2].push_back(x);
				bt.add(x+1,A[x]-(x?A[x-1]:0));
			}
			
			FOR(x,M) {
				bt.add(L[x],X[x]);
				bt.add(R[x],-X[x]);
				FORR(e,ev[x]) {
					int sum=bt(e+1);
					if(sum==s) mi[e]=min(mi[e],x+1);
					if(sum>s) RR[e]=x;
					else LL[e]=x;
				}
			}
		}
	}
	FOR(i,102000) ev[i].clear();
	ll sum=0;
	ZERO(bt.bit);
	FOR(i,N) ev[mi[i]].push_back(i), sum+=A[i], bt.add(i+1,1);
	FOR(i,M) {
		FORR(e,ev[i]) bt.add(e+1,-1);
		int cnt=bt(R[i]-1)-bt(L[i]-1);
		sum += 1LL*X[i]*cnt;
		cout<<sum<<endl;
	}
	
}

まとめ

並列二分探索、前に1回AGCで出たっけか。
慣れない手法なのでちゃんと身に着けないとな。