Educational DP Contest : W - Intervals

個人的にはSegTreeとか出てくるとあまりDPって感じしないな…。
https://atcoder.jp/contests/dp/tasks/dp_w

問題

N文字の0/1文字列を構築することを考える。
[L[i],R[i]]の範囲に1が1個でもあるとA[i]点加算される、という条件がM個提示されている。
この時、総得点の最大値を求めよ。

解法

dp(n) := n文字目までを定めたときの得点の最大値
として、dp(0)=0から初めてdp(N)を求めよう。

n文字目に1を置く場合を考える。その直前の1がm文字目にあるとすると、
dp(n) = max(dp(m) + sum(A[k])) (ただしkはm＜L[k]≦n≦R[k]を満たすもの)
と取るとよい。区間のmaxを取るのだから、dp(i)をSegTreeで管理するのは良しとして、問題はsum(A[k])の部分である。

これは以下のように考える。
今これからn文字目を考えるとき、L[i]=nであるような条件があったとする。
すると、n文字目以降R[i]文字目を考えるまでは、dp(0)～dp(L[i]-1)から遷移する場合はA[i]が加算されるべきである。
よってSegTreeの区間[0,n)にA[i]を先に加えておく。
n＞R[i]になった瞬間、その分再度dp(0)～dp(L[i]-1)からA[i]を引いておけばよい。

static ll const def=-1LL<<60;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
		FOR(i,NV) val[i+NV]=ma[i+NV]=0;
		for(i=NV-1;i>=1;i--) ma[i]=max(ma[2*i],ma[2*i+1]);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return ma[k];
		return val[k]+max(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+max(ma[k*2],ma[k*2+1]);
		}
	}
};

SegTree_3<ll,1<<20> st;

int N,M;
vector<int> add[202020];
vector<pair<int,int>> del[202020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>l>>r>>x;
		add[l].push_back(x);
		del[r].push_back({l,x});
	}
	
	ll ma=0;
	for(i=1;i<=N;i++) {
		FORR(a,add[i]) st.update(0,i,a);
		ll v=st.getval(0,i);
		ma=max(ma,v);
		st.update(i,i+1,v);
		FORR(a,del[i]) st.update(0,a.first,-a.second);
	}
	cout<<ma<<endl;
}

まとめ

区間系の問題もだいぶ慣れてきたもんだ。