kmjp's blog

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

Codeforces #465 Div2 F. Fafa and Array

Codeforces

面倒だけど何とか通った。
http://codeforces.com/contest/935/problem/F

問題

N要素の数列Aがある。f(A)を以下のように定める。
f(A) := 隣接要素の差の絶対値の総和

以下のクエリに順次答えよ。

  • Aの要素のうち[L,R]の範囲の１か所にX加算できる場合、f(A)の最大値を答えよ。(クエリ終了後はXの加算は取り消される)
  • Aの部分列A[L]～A[R]にXを加算する

解法

数列は値を直接持たず、前の要素の差を持つ形にすればBITで高速に各要素の値を求められるし、後者のクエリも容易に対応できる。

基本的にf(A)を常時保持しておくことにする。
２番目のクエリに対してはA[L-1]とA[L]とA[R]とA[R+1]のみ隣接要素との差が変化するので、そこだけ更新すればf(A)の値を維持できる。

問題は1つめである。
A[L]～A[R]の間に、A[i-1]≦A[i]≧A[i+1]であるような要素A[i]があれば、そこにXを加算すればf(A)に2X加算されて良い。

ここで、あえて逆にA[j-1]＞A[j]＜A[j+1]となるiの存在を考える。
このようなjが2つ以上ある場合、その場合は上記iに相当する値が最低1個は存在する。

さて、A[k-1]≧A[k]≧A[k+1]またはA[k-1]≦A[k]≦A[k+1]であるようなkを考える。
A[k]にXを足したときのf(A)の変化は、A[k-1]またはA[k+1]がA[k]よりどれだけ大きいかによって決まる。
当然差分が小さいときの方が、Xを加算することでf(A)を大きくできる。
そこで、「隣接要素の片方が自身以上であるとき、その差を格納しておき、区間における最小値を求める」というようなSegTreeを準備しよう。
なお、A[i-1]≦A[i]≧A[i+1]の場合は差を0としておけば、同じSegTreeで扱える。

すると、解の候補は以下のいずれか。

  • A[j-1]＞A[j]＜A[j+1]となるjが区間内に存在するなら1個だけX加算を試す
  • 前記SegTreeで最小となる要素を求め、X加算を試す
  • 以下では念のため区間の両端であるA[L]やA[R]に加算するケースも試している

A[j-1]＞A[j]＜A[j+1]となるjが2個以上ある場合、SegTreeにおける差の最小値が0となる要素が必ず存在するのでその時が最適解となるため、2個以上探索する必要はない。

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

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=1LL<<60;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,1LL<<60);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

int N,Q;
ll AS;
set<int> S;
SegTree_1<ll,1<<20> penalty;

void update(int cur) {
	if(cur<=1 || cur>=N) return;
	S.erase(cur);
	penalty.update(cur,1LL<<60);
	if(bt[cur]<bt[cur-1]&&bt[cur]<bt[cur+1]) {
		S.insert(cur);
	}
	else {
		penalty.update(cur,max({0LL,bt[cur-1]-bt[cur],bt[cur+1]-bt[cur]}));
	}
}

ll hoge(int cur,int add) {
	ll ret=0;
	ret-=abs(bt[cur]-bt[cur-1]);
	ret+=abs(bt[cur]+add-bt[cur-1]);
	ret-=abs(bt[cur]-bt[cur+1]);
	ret+=abs(bt[cur]+add-bt[cur+1]);
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	int pre=0;
	for(i=1;i<=N;i++) {
		scanf("%d",&x);
		bt.add(i,x-pre);
		if(i>1) AS+=abs(x-pre);
		pre=x;
	}
	for(i=2;i<=N-1;i++) update(i);
	S.insert(N+1);
	
	scanf("%d",&Q);
	while(Q--) {
		int T,L,R,X;
		scanf("%d%d%d%d",&T,&L,&R,&X);
		if(T==1) {
			ll ret= AS + max(hoge(L,X),hoge(R,X));
			auto it=S.lower_bound(L);
			if(*it<=R) ret = max(ret, AS + hoge(*it,X));
			ll p=penalty.getval(L,R+1);
			if(p<X) ret=max(ret,AS+X+X-2*p);
			
			cout<<ret<<endl;
		}
		else {
			AS-=abs(bt[L]-bt[L-1]);
			AS-=abs(bt[R]-bt[R+1]);
			bt.add(L,X);
			bt.add(R+1,-X);
			AS+=abs(bt[L]-bt[L-1]);
			AS+=abs(bt[R]-bt[R+1]);
			update(L);
			update(L-1);
			update(R);
			update(R+1);
		}
	}
	
	
}

まとめ

本番はもっと冗長なコードを書いていた。
通ったのでまぁいいけど…。