题意

一个整数数列，多次询问某段区间[li,ri][l_i,r_i][li,ri]内，选出若干个长度为LLL且不相交的连续段使选出来的数和最大。

分析

首先想朴素的区间DPDPDP

设f[i][j]f[i][j]f[i][j]表示区间[i,j][i,j][i,j]的答案。O(n2)O(n^2)O(n2)转移比较显然。

f[i][j]=max(f[i][j−1],f[i][j−L]+∑k=j−L+1ja[j])f[i][j]=max(f[i][j-1],f[i][j-L]+\sum_{k=j-L+1}^ja[j])f[i][j]=max(f[i][j−1],f[i][j−L]+k=j−L+1∑ja[j])

为了方便我们把∑k=j−L+1ja[j]\sum_{k=j-L+1}^ja[j]∑k=j−L+1ja[j]记作b[j]b[j]b[j]，则

f[i][j]=max(f[i][j−1],f[i][j−L]+b[j])f[i][j]=max(f[i][j-1],f[i][j-L]+b[j])f[i][j]=max(f[i][j−1],f[i][j−L]+b[j])

空间和时间都会爆。然后想想多组询问怎么做。

发现L≤50L\le50L≤50，于是就有巧妙的分治做法。

对于区间[qL,qR][qL,qR][qL,qR]，中点是midmidmid。我们把跨越midmidmid的询问拿出来求答案，没有跨越的分治下去，就变成了子问题。

那么对于一个询问[qL,qR][qL,qR][qL,qR]，它的答案有两种情况。

一种是没有选跨越midmidmid的连续段，那么就是[qL,mid][qL,mid][qL,mid]和[mid+1,qR][mid+1,qR][mid+1,qR]的答案加起来。
另一种是跨越了midmidmid的。因为LLL很小我们枚举跨越midmidmid的一段在左边有多长，记作jjj，则右边长为L−jL-jL−j。那么有1<j<L,1<L−j<L1<j<L,1<L-j<L1<j<L,1<L−j<L。

那么答案就是[qL,mid−j][qL,mid-j][qL,mid−j]的答案加上[mid+1+L−j,qR][mid+1+L-j,qR][mid+1+L−j,qR]的答案再加上中间一段的答案b[mid+L−j]b[mid+L-j]b[mid+L−j]

发现上面需要算答案的区间只有O(nL)O(nL)O(nL)级别的且连续，可以直接预处理。

然后就做完了。时间复杂度O(nLlog⁡n)O(nL\log n)O(nLlogn)。具体实现见代码。

CODE

#include <bits/stdc++.h>

using namespace std;

char cb[1<<18],*cs,*ct;

#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<18,stdin),cs==ct)?0:*cs++)

inline void rd(int &x) {

	x = 0; char ch; int flg=1; while(!isdigit(ch=getc()))if(ch=='-')flg=-flg;

	do x=x*10+ch-'0'; while(isdigit(ch=getc())); x *= flg;

}

const int MAXN = 100005;

const int MAXL = 55;

int n, m, L, a[MAXN], ans[MAXN];

struct query { int l, r, id; }q[MAXN], tmp1[MAXN], tmp2[MAXN];

int fL[MAXL][MAXN], fR[MAXL][MAXN];

inline void workL(int l, int r) {

	for(int i = 0; i <= r-l && i < L; ++i) {

		fL[i][r-i+1] = 0;

		for(int j = r-i; j >= l; --j)

			fL[i][j] = j+L-1 > r-i ? 0 : max(fL[i][j+1], fL[i][j+L] + a[j+L-1]);

	}

}

inline void workR(int l, int r) {

	for(int i = 0; i <= r-l && i < L; ++i) {

		fR[i][l+i-1] = 0;

		for(int j = l+i; j <= r; ++j)

			fR[i][j] = j-L+1 < l+i ? 0 : max(fR[i][j-1], fR[i][j-L] + a[j]);

	}

}

void cdq(int l, int r, int ql, int qr) {

	if(ql > qr || r-l+1 < L) return;

	int mid = (l + r) >> 1, it1 = 0, it2 = 0;

	workL(l, mid); workR(mid+1, r);

	for(int i = ql; i <= qr; ++i) {

		if(q[i].r <= mid) tmp1[++it1] = q[i];

		else if(q[i].l > mid) tmp2[++it2] = q[i];

		else {

			ans[q[i].id] = fL[0][q[i].l] + fR[0][q[i].r];

			for(int j = max(1, L-(q[i].r-mid)); j <= mid-q[i].l+1 && j < L; ++j)

				ans[q[i].id] = max(ans[q[i].id], (mid-j < l ? 0 : fL[j][q[i].l]) + (mid+L-j+1 > r ? 0 : fR[L-j][q[i].r]) + a[mid+L-j]);

		}

	}

	for(int i = 1; i <= it1; ++i) q[ql+i-1] = tmp1[i];

	for(int i = 1; i <= it2; ++i) q[ql+it1+i-1] = tmp2[i];

	cdq(l, mid, ql, ql+it1-1); cdq(mid+1, r, ql+it1, ql+it1+it2-1);

}

int main () {

	rd(n), rd(L);

	for(int i = 1; i <= n; ++i) rd(a[i]), a[i] += a[i-1];

	for(int i = n; i >= L; --i) a[i] -= a[i-L];

	rd(m);

	for(int i = 1; i <= m; ++i) rd(q[i].l), rd(q[i].r), q[i].id = i;

	cdq(1, n, 1, m);

	for(int i = 1; i <= m; ++i) printf("%d\n", ans[i]);

}

ql

BZOJ 3636 教义问答手册 （分治）

题意

分析

CODE

BZOJ 3636 教义问答手册（分治）