题目概述

CF1701F

解题报告

对于 $x$ ，设 $[x-d,x-1]$ 上共有 $cnt$ 个点，那么以 $x$ 作为结尾的三元组个数为 ${cnt\choose 2}={1\over 2}(cnt^2-cnt)$ 。

然后就是个维护平方和的题，和南京E差不多，只不过这题一个节点上的区间长度需要改成区间当前存在的点的个数。

每个节点上定义 $si,sum,val$ 表示该节点对应区间上的：存在的点的个数，区间中 $cnt$ 的和，区间中 $cnt^2$ 的和。

每次插入 $x$ 时，分为两部分，第一部分在 $x$ 这个位置上更新 $si,sum,val$ 的信息，第二部分在 $[x+1,x+d]$ 这个区间进行区间 $cnt+1$ 。删除 $x$ 时同理。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200000,maxt=maxn<<2;

int m,D,c[maxn+5];
bool vis[maxn+5];
struct Matrix{
    LL s[3][3];
    void zero() {for (int i=0;i<3;i++) for (int j=0;j<3;j++) s[i][j]=0;}
    void unit() {zero();for (int i=0;i<3;i++) s[i][i]=1;}
};
Matrix tag[maxt+5],tem;
int cnt[maxt+5];LL M[maxt+5][3];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
struct fastO{
    int si;char buf[100000];
    fastO() {si=0;}
    void putc(char ch){
        buf[si++]=ch;
        if (si==100000) fwrite(buf,1,100000,stdout),si=0;
    }
    ~fastO() {fwrite(buf,1,si,stdout);}
}fo;
template<typename T> void writei(T x,char ch='\n'){
    static int buf[100],len=0;
    do buf[len++]=x%10,x/=10; while (x);
    while (len) fo.putc(buf[--len]+48);
    fo.putc(ch);
}
void Add(int x,int y) {for (;x<=maxn;x+=x&-x) c[x]+=y;}
int Sum(int x) {int sum=0;for (;x;x-=x&-x) sum+=c[x];return sum;}
void Make(LL k){
    tem.unit();
    tem.s[0][1]=k;tem.s[0][2]=k*k;
    tem.s[1][2]=k*2;
}
Matrix operator * (const Matrix &a,const Matrix &b){
    static Matrix c;c.zero();
    for (int i=0;i<3;i++)
        for (int j=i;j<3;j++)
            for (int k=i;k<=j;k++)
                c.s[i][j]+=a.s[i][k]*b.s[k][j];
    return c;
}
void Mul(LL *a,Matrix &A){
    a[2]=A.s[0][2]*a[0]+A.s[1][2]*a[1]+A.s[2][2]*a[2];
    a[1]=A.s[0][1]*a[0]+A.s[1][1]*a[1];
    a[0]=A.s[0][0]*a[0];
}
void Build(int L,int R,int p=1){
    tag[p].unit();
    if (L==R) return;
    int mid=L+(R-L>>1);
    Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);
}
void Pushup(int p) {for (int i=0;i<3;i++) M[p][i]=M[p<<1][i]+M[p<<1|1][i];}
void Addtag(int p,Matrix &A) {Mul(M[p],A);tag[p]=tag[p]*A;cnt[p]++;}
void Pushdown(int p){
    if (cnt[p]){
        Addtag(p<<1,tag[p]);Addtag(p<<1|1,tag[p]);
        cnt[p]=0;tag[p].unit();
    }
}
void Update(int pos,int f,int x,int l=1,int r=maxn,int p=1){
    if (l==r) {M[p][0]+=f;M[p][1]+=f*x;M[p][2]+=(LL)f*x*x;return;}
    int mid=l+(r-l>>1);Pushdown(p);
    pos<=mid?Update(pos,f,x,l,mid,p<<1):Update(pos,f,x,mid+1,r,p<<1|1);
    Pushup(p);
}
void Insert(int L,int R,int l=1,int r=maxn,int p=1){
    if (L==l && r==R) return Addtag(p,tem);
    int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) Insert(L,R,l,mid,p<<1); else if (L>mid) Insert(L,R,mid+1,r,p<<1|1);
    else Insert(L,mid,l,mid,p<<1),Insert(mid+1,R,mid+1,r,p<<1|1);
    Pushup(p);
}
int main(){
    readi(m);readi(D);
    Build(1,maxn);
    for (int i=1;i<=m;i++){
        int x;readi(x);
        int f=(vis[x]?-1:1);vis[x]^=1;
        int sum=Sum(x-1)-(x-D>0?Sum(x-D-1):0);
        Add(x,f);
        Update(x,f,sum);
        Make(f);if (x<maxn) Insert(x+1,min(x+D,maxn));
        writei((M[1][2]-M[1][1])/2);
    }
    return 0;
}