题解：AT_abc147_f [ABC147F] Sum Difference

· · 题解

萌新题解，管理员求放过

这题感觉挺好的。

首先，我们注意到：

\begin{aligned} \sum_{i \in S} a_{i}-\sum_{i \notin S} a_{i} = 2 \times \sum_{i\in S} a_{i}-\sum_{i=1}^na_{i} \end{aligned}

然后我们容易发现，\sum_{i=1}^na_{i} 和 2 都是定值，问题转化为 \sum_{i\in S} a_{i} 的不同和的数量 。

我们将 a_{i} 拆开，得到 x+(i-1) \times d 。

我们考虑集合中有 t 个数的情况，他们和为 t \times x + l \times d ， l 有连续区间 t \times (t-1) \le 2 \times l \le (2*n-t-1) \times t ，在 l 取前 t 小个数字时有最小值，取前 k 大个数字时有最大值。

我们考虑出现重合的地方，我们注意到，当 t_{1} \times x \equiv t_{2} \times x \pmod d 时，取 t_{1} 的值与取 t_{2} 的值在一直线上，有且仅有这种情况会出现重合。

我们将问题转换成直线上线段并，然后就可以解决它啦。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int n,d,x,tot,ans=0;
map<int,int> m;
vector<pair<int,int>> vec[N];//pair自带按第一关键字排序 
signed main(){
    cin>>n>>x>>d;
    if(d==0){//特判 
        if(x==0) cout<<1<<endl;
        else cout<<n+1<<endl;
        return 0;
    }
    for(int i=0;i<=n;i++){
        int now=i*x%d;
        int lef=i*(i-1)/2,rig=(2*n-i-1)*i/2;
        if(d<0) swap(lef,rig);//特殊处理d<0的情况 
        if(m[now]==0){
            tot++;
            m[now]=tot;
        }
        vec[m[now]].push_back(make_pair(lef*d+i*x,rig*d+i*x));
    }
    d=abs(d); 
    for(int i=1;i<=tot;i++){
        sort(vec[i].begin(),vec[i].end());
        int lef=vec[i].front().first,rig=vec[i].front().second;
        ans+=(rig-lef)/d+1;
        for(auto j:vec[i]){
            if(j.second<=rig) continue; //当前区间被完全覆盖 
            if(j.first<=rig) ans+=(j.second-rig)/d; //当前区间与之前线段有重叠 
            else ans+=(j.second-j.first)/d+1; //当前线段与之前无重叠 
            rig=j.second; 
        }
    }
    cout<<ans;
}