luogu2119题解

本题考察对于枚举的方式对程序的性能的提升。

有一个小的优化，\(n\) 的范围比 \(m\) 的范围小，由于我们不关心顺序，我们既可以在值域上枚举也可以在物品上枚举，这里为了优化在值域上枚举更好。

最简单的枚举是直接枚举 \(a,b,c,d\) 或是枚举其中三个数枚举另一个，时间复杂度为 \(O(n^4)\) 或 \(O(n^3)\)，显然不能通过。

简单的枚举并没有完全利用题中的物品的关系。
如果枚举 \(X_d-X_c\) 的值可以得到 \(X_b-X_a\) 和 \(X_c-X_b\) 的下限。
此时枚举 \(d\) 可以确定 \(c\)，进而确定 \(b\) 的范围，然后通过 \(b\) 的范围确定 \(a\) 的范围。

在求作为 \(c,d\) 物品出现次数时我们并不需要知道 \(a,b\) 的具体的值，我们只需要知道有多少对 \(a,b\) 即可。
同时我们求作为 \(a,b\) 物品出现次数时我们也不关心 \(c,d\) 具体的值。
我们可以统计符合条件的 \(a,b\) 有多少对，在枚举 \(d\) 的过程中把不符合要求的 \(a,b\) 丢掉，计算 \(c,d\) 的出现次数，同时统计 \(c,d\) 的对数，累加 \(a,b\) 的答案，最后再一起输出即可。

代码如下。

#include<bits/stdc++.h>
using namespace std;
constexpr int MAXN=15000+10,MAXM=4e4+10;
int a[MAXM],bucket[MAXN],n,m,ans[MAXN][4],maxa=-114514,mina=114514;
namespace sol{
    void solve(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;++i){scanf("%d",&a[i]);++bucket[a[i]];maxa=max(maxa,a[i]);mina=min(mina,a[i]);}
        for(int dcd=1;dcd*9<maxa-mina;++dcd){
            //dab=dcd*2,dbc>dcd*6
            int pab=0,pb=maxa,pcd=0;
            for(int a1=mina;a1+(dcd<<1)<=maxa;++a1){
                pab+=bucket[a1]*bucket[a1+(dcd<<1)];
            }
            for(int d=maxa;d-dcd*9>mina;--d){
                //c=d-dcd
                while(pb>=d-dcd*7){
                    ans[pb][1]+=pcd*bucket[pb-(dcd<<1)];
                    ans[pb-(dcd<<1)][0]+=pcd*bucket[pb];
                    pab-=bucket[pb-dcd*2]*bucket[pb];
                    --pb;
                }
                ans[d][3]+=pab*bucket[d-dcd];
                ans[d-dcd][2]+=pab*bucket[d];
                pcd+=bucket[d-dcd]*bucket[d];
            }
            while(pb-(dcd<<1)>=mina){
                ans[pb][1]+=pcd*bucket[pb-(dcd<<1)];
                ans[pb-(dcd<<1)][0]+=pcd*bucket[pb];
                --pb;
            }
        }
        for(int i=1;i<=m;++i){
            for(int j=0;j<4;++j){
                printf("%d ",ans[a[i]][j]);
            }
            puts("");
        }
    }
}
int main(){
    sol::solve();
    return 0;
}