题解：P12493 [集训队互测 2024] 子集和

· · 题解

考虑把背包看成一个黑盒：支持 \mathcal O(m) 插入物品，以及给出两个背包 A,B，以 \mathcal O(m^2) 进行完全的合并，\mathcal O(m) 对位相加信息，\mathcal O(m) 查询合并后的一个点值，以及存储并回退。完全的背包合并因为 m^2 所以不能使用。因为模 m 意义，所以不能删除已有物品。

如果只需要处理所有 f(S-\{i\})，可以进行分治，每次递归时已经加入 [1,l-1]\cup [r+1,n] 的物品即可，时间复杂度 \mathcal O(nm\log n)。还有一个问题是总对数是 n^2 的，但是我们只需要求一个矩形区域的和，这个其实可以对背包数组对位相加然后整体维护，这样避免了合并。

考虑 l_1=r_1,l_2=r_2，查询单组 (x,y) 值的做法：此时对 (x,y) 进行猫树分治离线，挂到对应的 [l,r] 上，维护 [1,l-1] 的背包 F，[r+1,n] 的背包 G，两侧分别做一次缺一分治，以 F/G 为基础求出 [1,mid]-\{i\} 以及 [mid+1,n]-\{i\} 的背包信息，左右侧合并只需要查询合并后 0 的点值，复杂度是 \mathcal O(mn\log^2n+qm)。

拓展这个猫树分治做法，将所有询问套路化的差分为 \mathcal O(1) 对 (x,y) 询问 [1,x],[y,n] 的答案，保证 x<y。这时变成了求和。依然将其分为 \leq mid,>mid 的物品，这时会涉及 [1,l-1],[l,x] 以及 [y,r],[r+1,n]。那么贡献分为 2\times 2=4 对，分类讨论一下：

事实上并不需要拆成 4 个，只需要 f_x,g_y 分别与 [1,l-1],[r+1,n] 预先合并即可。

综上，我们可以使用 \mathcal O(n\log^2n) 次背包的基本操作就解决本题。时间复杂度 \mathcal O(mn\log^2n+qm)。本题的精髓在于对背包的对位加以实现求整体信息，以及分治算法的运用。其实可以理解成多项式的 (\times,+) 运算，然后把分配律倒过来将他合并了。

int ans[QR],n,m,zsy,a[maxn],b[maxn];
#define poly vector<int>
poly mrg(poly x,poly y){
    poly res(m);
    F(i,0,m-1)res[i]=add(x[i],y[i]);
    return res;
}
poly ins(poly x,int pos){
    poly res=x;
    F(i,0,m-1)inc(res[i+a[pos]>=m?i+a[pos]-m:i+a[pos]],x[i]);
    F(i,0,m-1)inc(res[i+b[pos]>=m?i+b[pos]-m:i+b[pos]],x[i]);
    return res;
}
void init(poly &x){
    x.resize(m);
    F(i,0,m-1)x[i]=(i==0);
}
void init1(poly &x){
    x.resize(m);
    for(int &i:x)i=0;
}
int qry(poly &x,poly &y){
    int ans=0;
    F(i,0,m-1)inc(ans,1ll*x[i]*y[i==0?0:m-i]%mod);
    return ans;
}
vector<array<int,4>>qu[maxn<<2];
void ins_query(int o,int l,int r,int ql,int qr,int coef,int id){
    if(ql>qr||ql<1||qr>n)return;
    const int mid=(l+r)>>1;
    if(ql<=mid&&mid<qr)return qu[o].push_back({ql,qr,coef,id}),void();
    if(qr<=mid)ins_query(o<<1,l,mid,ql,qr,coef,id);
    if(ql>mid)ins_query(o<<1|1,mid+1,r,ql,qr,coef,id);
}
poly pre[maxn],suf[maxn],psum[maxn],ssum[maxn],f[maxn],dp[maxn];
void dfs(int o,int l,int r){
    if(l==r)return;
    const int mid=(l+r)>>1;
    dfs(o<<1,l,mid),dfs(o<<1|1,mid+1,r);
    if(qu[o].empty())return;
    poly F;
    auto sol=[&](auto &self,int L,int R){
        if(L==R)return f[L]=F,void();
        int mid=(L+R)>>1;
        poly tmp=F;
        F(i,L,mid)F=ins(F,i);
        self(self,mid+1,R);
        F=tmp;
        F(i,mid+1,R)F=ins(F,i);
        self(self,L,mid);
    };
    F=psum[l-1],sol(sol,l,mid);
    F=ssum[r+1],sol(sol,mid+1,r);
    poly lef=pre[l-1],rig=suf[r+1];
    F(i,l,mid)lef=ins(lef,i);
    F(i,mid+1,r)rig=ins(rig,i);
    dp[l-1]=lef,dp[r+1]=rig;
    F(i,l,mid)dp[i]=mrg(dp[i-1],f[i]);
    dF(i,r,mid+1)dp[i]=mrg(dp[i+1],f[i]);
    for(auto&[ql,qr,coef,id]:qu[o]){
        int val=qry(dp[ql],dp[qr]);
        if(coef<0)dec(ans[id],val);
        else inc(ans[id],val);
    }
}
void solve(){
    cin>>n>>m>>zsy;
    F(i,1,n)cin>>a[i]>>b[i];
    init(psum[0]),init(ssum[n+1]);
    F(i,1,n)psum[i]=ins(psum[i-1],i);
    dF(i,n,1)ssum[i]=ins(ssum[i+1],i);
    init1(pre[0]),init1(suf[n+1]);
    F(i,1,n)pre[i]=mrg(ins(pre[i-1],i),psum[i-1]);
    dF(i,n,1)suf[i]=mrg(ins(suf[i+1],i),ssum[i+1]);
    F(i,1,zsy){
        int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;
        ins_query(1,1,n,r1,l2,1,i);
        ins_query(1,1,n,r1,r2+1,-1,i);
        ins_query(1,1,n,l1-1,l2,-1,i);
        ins_query(1,1,n,l1-1,r2+1,1,i);
    }
    dfs(1,1,n);
    F(i,1,zsy)cout<<ans[i]<<'\n';
}