题解：CF1701F Points

违规用户名1271019 · 2026-10-22 16:47:02 · 题解

模拟赛 T2，比较简单。

考虑以第 i 个节点为结尾，若区间 [i-d,i-1] 中有 k 个数，那么这个点的贡献是 \frac{k\times(k-1)}{2}。

考虑加数，首先以这个数为末尾会贡献 \frac{k\times(k-1)}{2}，它会使得区间 [i+1,d] 中的每一个数的 k 值加一，那么贡献就加上 \frac{(k+1)\times k}{2}-\frac{k\times(k-1)}{2}=k。删数同理。

我们维护每个数的 k 值与有没有出现这个数，需要的操作有区间加一，区间查询所有出现的数的和，单点修改是否出现，单点查询某个数的 k 值。这是可以用线段树维护的，时间 \mathcal{O}(n\log n)。

::::info[code] 代码中 k 与 d 定义相反。

int q,k,a[N],ans,d[N]; 
struct SegTree {
    int tr[N<<2],q[N<<2],qd[N<<2],lz[N<<2];
    //分别是 区间sum 区间1个数 区间1的sum 加法懒标记
    #define ls (u<<1)
    #define rs (ls|1)
    #define mid (l+r>>1)
    void pu(int u) {tr[u]=tr[ls]+tr[rs],q[u]=q[ls]+q[rs],qd[u]=qd[ls]+qd[rs];}
    void cg(int u,int l,int r,int x) {tr[u]+=x*(r-l+1),qd[u]+=x*q[u],lz[u]+=x;}
    void pd(int u,int l,int r) {cg(ls,l,mid,lz[u]),cg(rs,mid+1,r,lz[u]),lz[u]=0;}
    void update(int u,int l,int r,int pos) {
        if(l>pos||r<pos) return;
        if(l==r) {
            if(a[l]==0) a[l]=1,qd[u]=tr[u],q[u]=1;
            else a[l]=0,qd[u]=0,q[u]=0;
            return ;
        }
        pd(u,l,r),update(ls,l,mid,pos),update(rs,mid+1,r,pos),pu(u);
    }
    void update(int u,int l,int r,int ql,int qr,int d) {
        if(l>qr||r<ql||ql>qr) return;
        if(ql<=l&&r<=qr) return cg(u,l,r,d);
        pd(u,l,r),update(ls,l,mid,ql,qr,d),update(rs,mid+1,r,ql,qr,d),pu(u);
    }
    int query(int u,int l,int r,int pos) {
        if(l>pos||r<pos) return 0;
        if(l==r) return tr[u];
        return pd(u,l,r),query(ls,l,mid,pos)+query(rs,mid+1,r,pos);
    }
    int query(int u,int l,int r,int ql,int qr) {
        if(l>qr||r<ql||ql>qr) return 0;
        if(ql<=l&&r<=qr) return qd[u];
        return pd(u,l,r),query(ls,l,mid,ql,qr)+query(rs,mid+1,r,ql,qr);
    }
}t;
void Solve(int Ti=0) {
    cin >> q >> k;
    rep(_,1,q) {
        int opt,i; cin >> i;
        if(a[i]==0) {
//          a[i]=1;
//          ans+=d[i]*(d[i]-1)/2;
//          rep(j,i+1,min(V,i+k)) {
//              if(a[j]) ans+=d[j];
//              d[j]++;
//          }
            t.update(1,1,V,i);
            int d=t.query(1,1,V,i); ans+=d*(d-1)/2;
            ans+=t.query(1,1,V,i+1,min(V,i+k));
            t.update(1,1,V,i+1,min(V,i+k),1);
        } else if(a[i]==1) {
//          a[i]=0;
//          ans-=d[i]*(d[i]-1)/2;
//          rep(j,i+1,min(V,i+k)) {
//              d[j]--;
//              if(a[j]) ans-=d[j];
//          }
            t.update(1,1,V,i);
            int d=t.query(1,1,V,i); ans-=d*(d-1)/2;
            t.update(1,1,V,i+1,min(V,i+k),-1);
            ans-=t.query(1,1,V,i+1,min(V,i+k));
        }
        cout << ans << "\n";
    }
    return;
}

::::