CF1701F Points Solution

· · 题解

Solution

考虑将贡献拆开，分为以 a_i 为端点和跨过 a_i，长度不超过 d 的线段个数。第一个贡献随便求，考虑如何计算第二个贡献。

考虑分块，记块长为 B，加入一个点，会和左边和右边的点构成新的线段。对于完整的块，经过块内每个点的线段个数是单调的，像是样例前几个加入后，线段如下：

7 5
8 5 3 2 1 5 6

:::align{center}

样例加入前 5 个数的视图

:::

就是这个样子。比较容易看出加入的线段端点是单调的。
具体的，如果块在 a_i 的左边，则经过块内的点是的线段个数是单调递增的，并且是在已经加入过的点的位置 +1。对于右侧的点也是一样的，可以开两个标记。

容易发现删除是对称的，即反过来操作即可。

如果这个块没有被更新过，那么显然，加入新的标记对于之前的标记变化的位置是相同的，那么就可以合并标记。如果现在要更新这个块，那么肯定是现在询问了这个块，那么直接 O(B) 更新一下，清除一下标记即可。

复杂度 O(q(\frac{d}{B}+B))，取 B=\sqrt{d} 即可。代码非常短。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N=4e5+10;

int q,d,tr[N],p;
#define lb(u) ((u)&-(u))
inline void upd(int u,int v) {while(u<N)tr[u]+=v,u+=lb(u);}
inline int sum(int u) {int res=0;while(u>0)res+=tr[u],u-=lb(u);return res;}
ll tp[N],cp[N],ts[N],cs[N],val[N],v[N],vis[N],res;

inline ll calc(const int B,int p){
    if(d<2) return 0;
    ll id=(p-1)/B+1,l=(id-1)*B+1,r=id*B,t,td,nw,f;
    if(tp[id]||cp[id]) for(int i=l;i<=r;i++) tp[id]-=vis[i]*cp[id],val[i]+=tp[id];
    if(ts[id]||cs[id]) for(int i=r;i>=l;i--) ts[id]-=vis[i]*cs[id],val[i]+=ts[id];
    tp[id]=ts[id]=cp[id]=cs[id]=0; f=vis[p]?-1:1; res+=val[p]*f;

    t=sum(p-1)-sum(p-d-1),res+=t*(t-1)/2*f,td=d-1,nw=id-1;
    for(int i=p-1;i>=l&&td;i--,--td) t-=vis[i],val[i]+=t*f;
    while(nw&&td>=B) td-=B,ts[nw]+=t*f,cs[nw]+=f,t-=v[nw],--nw;
    if(td&&nw) for(int i=nw*B;td;--td,--i) t-=vis[i],val[i]+=t*f;

    t=sum(p+d)-sum(p),res+=t*(t-1)/2*f,td=d-1,nw=id+1;
    for(int i=p+1;i<=r&&td;i++,--td) t-=vis[i],val[i]+=t*f;
    while(td>=B) td-=B,tp[nw]+=t*f,cp[nw]+=f,t-=v[nw],++nw;
    if(td) for(int i=(nw-1)*B+1;td;--td,++i) t-=vis[i],val[i]+=t*f;

    vis[p]+=f,v[id]+=f; upd(p,f); return res;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>q>>d; const int B=sqrt(d)/2+5;
    while(q--) cin>>p,cout<<calc(B,p)<<"\n";
    return 0;
}