就是说，对于分治区间 \([l,r]\)，记 \(mid=\lfloor\dfrac{l+r}{2}\rfloor\)，对于 \([l,mid]\) 和 \([mid+1,r]\) 内的询问继续递归，把跨越两边的询问用左右的信息合并处理。
P6240 好吃的题目
物品 \(i\) 有体积 \(w_i\) 和价值 \(c_i\)，多次询问，对 \([l,r]\) 做 01 背包，问体积 \(\le t\) 的最大价值。
\(n\le 4\times 10^4\)，\(m\le 2\times 10^5\)，\(w_i,t\le 200\)，\(c_i\le 10^7\)。
板。对于左边处理所有后缀的背包，右边处理前缀。
\(O(nV\log n+qV)\)。
GJ Round 2024.2.20
给定 \(n,m,\{a_n\}\)，每次查询 \([l,r]\) 中和为 \(m\) 的倍数的子集数 \(\bmod {10^9+7}\)。
\(n,q\le 2\times 10^5\)，\(m\le 20\)。
这是一样的。\(O(nm\log n+qm^2)\)。
点击查看代码
#include<bits/stdc++.h>
#define N 200010
#define M 20
#define P 1000000007
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int n,m,p,a[N];
int L[N][M],R[N][M],ans[N];
struct Q{
int l,r,id;
}q[N],b[N];
void solve(int l,int r,int ql,int qr){
if(ql>qr)return;
int mid=(l+r)>>1;
memset(L[mid+1],0,sizeof(L[mid+1]));
memset(R[mid],0,sizeof(R[mid]));
L[mid+1][0]=1;
for(int i=mid;i>=l;i--)
for(int j=0,k;j<p;j++){
k=(j+a[i])%p;
L[i][k]=(L[i+1][j]+L[i+1][k])%P;
}
R[mid][0]=1;
for(int i=mid+1;i<=r;i++)
for(int j=0,k;j<p;j++){
k=(j+a[i])%p;
R[i][k]=(R[i-1][j]+R[i-1][k])%P;
}
int tl=ql,tr=qr;
for(int i=ql;i<=qr;i++)b[i]=q[i];
for(int i=ql;i<=qr;i++){
if(b[i].r<mid)q[tl++]=b[i];
else if(b[i].l>mid)q[tr--]=b[i];
else{
int cur=0;
for(int j=0;j<p;j++)
cur=(cur+1ll*L[b[i].l][j]*R[b[i].r][j?p-j:0])%P;
ans[b[i].id]=cur;
}
}
solve(l,mid,ql,tl-1),solve(mid+1,r,tr+1,qr);
}
int main(){
n=read(),p=read();
for(int i=1;i<=n;i++)a[i]=read()%p;
m=read();
for(int i=1,l,r;i<=m;i++){
l=read(),r=read();
q[i]={l,r,i};
}
solve(1,n,1,m);
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
return 0;
}