题目大意
一共有$N$条语录。Pear决定从中选出某一段时间内的所有语录，在此基础上印制大小为$L$的若干本教义问答手册。Pear对印制的手册有如下要求：
$1.$每本手册必须包含这个区间内连续的恰好L条语录。
$2.$不同手册包含的语录不能相同。
$3.$每条语录有一个“主题相关程度”，这个数可正可负。Pear希望所有手册的语录的“主题相关程度”之和尽可能大。
例如，对于区间$[3,15]$和$L=3$，一种选择方法是：$[4,6]+[9,11]+[12,14]$。这三个区间长度都恰好为$L$，且互不重叠。
Pear并没有决定选哪段时间的语录，因此他有$Q$次询问。每次询问，给出两个数$[l,r]$表示候选语录的范围是第$l$条到第$r$条。你能回答出每个询问的最大“主题相关程度”之和么？
题目分析
显然的CDQ分治，直接叫做分治也可以。
以前总结过的模板题啊。
对手册区间进行分治，每次处理跨越$i\in[mid-L+1,mid]$的询问。
从$i$向左向右分别动规/递推一次求出$fL[i],fR[i]$表示结束位置为$i$的满足要求的最大权值和。
因此第$i$层的时间复杂度为$O(L\left|Q[i]\right|)$，其中$Q[i]$是到达第$i$层的询问数量，对手册区间分治保证递归深度最多为$\log n$。
在递归下一层前对询问进行划分与减少（因此也可以看做对区间与询问同时分治）。
需要注意的是，若询问区间覆盖了当前整个区间就没有必要继续递归它了，因为当前层一定能够找到一个对于其最优的分界线，不继续递归可以保证一个询问被计算$O(\log n)$次。
代码
用vector有点小卡常。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
using namespace std;
namespace FastIO {
const int L=1<<15;
char buf[L],*S,*T;
char getchar() {
if(S==T) {T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
return *S++;
}
int Get_Int() {
int res=0,bj=1;char c=getchar();
while(!isdigit(c)) {if(c=='-')bj=-1;c=getchar();}
while(isdigit(c)) {res=res*10+c-'0';c=getchar();}
return res*bj;
}
}
using FastIO::Get_Int;
int max(int a,int b) {
return a>b?a:b;
}
const int maxn=100005;
struct Query {
int left,right,id;
Query(int l=0,int r=0,int x=0):left(l),right(r),id(x) {}
};
vector<Query> q[maxn<<2];
int n,m,L,sum[maxn],Ans[maxn],fL[maxn],fR[maxn];
void Division(int index,int Left,int Right) {
int mid=(Left+Right)>>1;
for(auto Q:q[index]) {
if(Q.right<mid)q[ls].push_back(Query(Q.left,Q.right,Q.id));
else if(Q.left>mid)q[rs].push_back(Query(Q.left,Q.right,Q.id));
else if(Q.left!=Left||Q.right!=Right) {
q[ls].push_back(Query(Q.left,mid,Q.id));
q[rs].push_back(Query(mid+1,Q.right,Q.id));
}
}
}
void CDQBinary(int index,int Left,int Right) {
if(Right-Left+1<L)return;
int mid=(Left+Right)>>1;
for(int st=max(mid-L+1,Left); st<=mid; st++) {
fL[st]=fR[st-1]=0;
for(int i=st-1; i>=Left; i--) {
if(i+L-1>=st)fL[i]=0;
else fL[i]=max(fL[i+1],fL[i+L]+(sum[i+L-1]-sum[i-1]));
}
for(int i=st; i<=Right; i++) {
if(i-L+1<st)fR[i]=0;
else fR[i]=max(fR[i-1],fR[i-L]+(sum[i]-sum[i-L]));
}
for(auto Q:q[index])if(Q.left<=st&&Q.right>=st)Ans[Q.id]=max(Ans[Q.id],fL[Q.left]+fR[Q.right]);
}
Division(index,Left,Right);
CDQBinary(ls,Left,mid);
CDQBinary(rs,mid+1,Right);
}
int main() {
n=Get_Int();
L=Get_Int();
for(int i=1; i<=n; i++)sum[i]=sum[i-1]+Get_Int();
m=Get_Int();
for(int i=1; i<=m; i++) {
int l=Get_Int(),r=Get_Int();
q[1].push_back(Query(l,r,i));
}
CDQBinary(1,1,n);
for(int i=1; i<=m; i++)printf("%d\n",Ans[i]);
return 0;
}
