無理やり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; } } }
まとめ
ややこしいだけで面白味は少ないかな…。