询问是要求

$\sum_{i=1}^n((x[i]-a)^2+(y[i]-b)^2)(x[i]=a||y[i]=b)$

即求

$\sum_{i=1}^n(x[i]-a)^2(y[i]=b)+\sum_{i=1}^n(y[i]-b)^2(x[i]=a)$

拆开得

$\sum_{i=1}^n(x[i]^2-2ax[i]+a^2)(y[i]=b)+\sum_{i=1}^n(y[i]^2-2by[i]+b^2)(x[i]=a)$

所以只要算出编号在区间[l,r]中x[i]=a的所有点的个数、y的和、y的平方和，以及编号在区间[l,r]中y[i]=b的所有点的个数、x的和、x的平方和。

对所有x[i]=a的点建立一棵平衡树，维护区间内y的信息，对所有y[i]=b的点建立一棵平衡树，维护区间内x的信息。

由于$x[i],y[i]\leq10^{18}$，所以不能直接建立2M棵平衡树，于是我就用了map，

rx[i]表示维护x=i的所有点的平衡树的根节点下标，ry[i]表示维护x=i的所有点的平衡树的根节点下标

 

修改：

1.x[i]+=k

在rx[x[i]]树中找到id=i的点，把val置0

x[i]+=k

在rx[x[i]]树中把id=i的点的val修改为y[i]

在ry[y[i]]树中把id=i的点的val修改为x[i](不存在该点则插入)

2.y[i]+=k

在ry[y[i]]树中找到id=i的点，把val置0

y[i]+=k

在ry[y[i]]树中把id=i的点的val修改为x[i]

在rx[x[i]]树中把id=i的点的val修改为y[i](不存在该点则插入)

时间复杂度$O(\log n)$，每次修改最多插入一个新节点

 

查询：

查询编号在区间[l,r]内的x[i]=a或者y[i]=b的军队集结到(a,b)的费用

在rx[a]树中查询区间[l,r]的和s、平方和s2、以及真实存在的节点个数n

$ans+=s2-2bs+nb^2$

在ry[b]树中查询区间[l,r]的和s、平方和s2、以及真实存在的节点个数n

$ans+=s2-2as+na^2$

时间复杂度$O(\log n)$

 

所以总的时间复杂度为$O((n+t)\log n)$，空间复杂度为$O(n+t)$。

由于我用了map，以及为了偷懒打了替罪羊树，以及%用的太多，所以常数比较大。

 

 

 

#include
     
      #include