kmjp's blog

競技プログラミング参加記です

Codeforces #546 Div2 E. Nastya Hasn't Written a Legend

無理やり1Hackして1位になった回。
https://codeforces.com/contest/1136/problem/E

問題

整数列AとKが与えられる。
以下のクエリに順次答えよ。

  • A[i]をxだけ加算する。なお、その後A[i]とA[i+1]の差が、K[i]以上となるようにしなければならない。
    • 条件を満たさない場合、満たすようにA[i+1]から順次値を増していく。
  • 区間[L,R]に対しsum(A[L..R])を答える。

解法

範囲加算・範囲総和を取れるSegTreeを準備しておけば、あとは範囲加算を工夫すればよくなる。

すでにA[i]+K[i]=A[i+1]を満たすような部分列がある場合、先頭要素を加算すると部分列全体が加算される。
そこで、逆にA[i]+K[i]!=A[i+1]であるようなsetを管理しよう。
前者のクエリでは、その要素で区切られた区間に対し同じ値が加算される。

均しでsetへの要素の追加・削除はO(クエリ回数)になるので、計算量は問題ない。

int N;
ll A[101010],K[101010];
int Q;

template<class V, int ME> class BIT_r {
public:
	V bit[2][1<<ME];
	BIT_r(){clear();};
	void clear() {ZERO(bit);};
	
	void update(int entry, V val0, V val1) {
		entry++;
		while(entry <= 1<<ME) bit[0][entry-1]+=val0, bit[1][entry-1] += val1, entry += entry & -entry;
	}
	V total(int entry) {
		int e=entry++;
		V v0=0,v1=0;
		while(entry>0) v0+=bit[0][entry-1], v1+=bit[1][entry-1], entry -= entry & -entry;
		return e*v0+v1;
	}
	V get(int entry) {
		return total(entry)-total(entry-1);
	}
	void add(int L, int R, V val) { // add val to L<=x<=R
		update(L,val,-val*(L-1));
		update(R+1,-val,val*R);
	}
};
BIT_r<ll,20> bt;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i+1];
		bt.add(i+1,i+1,A[i+1]);
	}
	set<int> B;
	for(i=1;i<=N-1;i++) {
		cin>>K[i];
		if(bt.get(i+1)-bt.get(i)!=K[i]) B.insert(i+1);
	}
	A[N+1]=1LL<<60;
	B.insert(N+1);
	cin>>Q;
	FOR(i,Q) {
		cin>>s>>x>>y;
		if(s=="+") {
			while(y) {
				int nex=*B.lower_bound(x+1);
				bt.add(x,nex-1,y);
				if(x>1) {
					if(bt.get(x)-bt.get(x-1)!=K[x-1]) {
						B.insert(x);
					}
					else {
						B.erase(x);
					}
				}
				if(nex>N) break;
				if(bt.get(nex)-bt.get(nex-1)>=K[nex-1]) {
					B.insert(nex);
					break;
				}
				y=K[nex-1]-(bt.get(nex)-bt.get(nex-1));
				x=nex;
			}
		}
		else {
			cout<<bt.total(y)-bt.total(x-1)<<endl;
		}
	}
}

まとめ

ややこしいだけで面白味は少ないかな…。