$\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)$

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

1.x[i]+=k

x[i]+=k

2.y[i]+=k

y[i]+=k

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

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

#include<cstdio>
#include<map>
#include<cmath>
#define N 100010
#define M 300010
using namespace std;
typedef long long ll;
const double A=0.6;
const ll P=1000000007;
int size[M],son[M][2],ex[M],pos[M],f[M],tot;
int balance[M];
bool real[M],tr[M];
ll val[M],sum[M],s2[M],tv[M],tmp;
int tp[M],id[M],cnt;
ll tsum,ts2,tsize;
ll X[N],Y[N],x,y,z,ans;
int n,T;
char ch;
map<ll,int>rx,ry;
inline ll sqr(ll x){return ((x%P)*(x%P))%P;}
int ins(int x,int p,ll v){
size[x]++;
int b=p>=pos[x];
if(!son[x][b]){
son[x][b]=++tot;f[tot]=x;size[tot]=ex[tot]=real[tot]=1;
pos[tot]=p;
sum[tot]=val[tot]=v;
s2[tot]=sqr(v);
}else return ins(son[x][b],p,v);
}
void dfs(int x){
if(son[x][0])dfs(son[x][0]);
tp[++cnt]=pos[x];tv[cnt]=val[x];tr[cnt]=real[x];id[cnt]=x;
if(son[x][1])dfs(son[x][1]);
}
inline void up(int x){
size[x]=size[son[x][0]]+size[son[x][1]]+1;
sum[x]=(sum[son[x][0]]+sum[son[x][1]]+val[x])%P;
s2[x]=(s2[son[x][0]]+s2[son[x][1]]+sqr(val[x]))%P;
ex[x]=ex[son[x][0]]+ex[son[x][1]]+real[x];
}
int build(int fa,int l,int r){
int mid=(l+r)>>1,x=id[mid];
f[x]=fa;son[x][0]=son[x][1]=0;
pos[x]=tp[mid];val[x]=tv[mid];real[x]=tr[mid];
if(l==r){
size[x]=1;
sum[x]=val[x];
s2[x]=sqr(val[x]);
ex[x]=real[x];
return x;
}
if(l<mid)son[x][0]=build(x,l,mid-1);
if(r>mid)son[x][1]=build(x,mid+1,r);
up(x);
return x;
}
inline int rebuild(int x){
cnt=0;dfs(x);return build(f[x],1,cnt);
}
inline void insert(int&root,int p,int v){
if(!root){
size[root=++tot]=1;
balance[tot]=1;
ex[tot]=real[tot]=1;
pos[tot]=p;
sum[tot]=val[tot]=v;
s2[tot]=sqr(v);
return;
}
balance[root]++;
int x=ins(root,p,v),d=0,z=x;
while(f[z])up(z=f[z]),d++;
if(d<log(balance[root])/log(1/A))return;
while((double)size[son[x][0]]<A*size[x]&&(double)size[son[x][1]]<A*size[x])x=f[x];
if(!x)return;
if(x==root){
int t=balance[root];
root=rebuild(x);
balance[root]=t;
return;
}
int y=f[x],b=son[y][1]==x,now=rebuild(x);
son[y][b]=now;
}
int find(int x,int p){
if(!x)return 0;
return pos[x]==p?x:find(son[x][p>pos[x]],p);
}
inline void change(int&root,int p,ll v,bool r){
int x=find(root,p);
if(x){
val[x]=v;
real[x]=r;
while(x)up(x),x=f[x];
return;
}
insert(root,p,v);
}
void ask(int x,int a,int b,int c,int d){
if(c<=a&&b<=d){
tsize+=ex[x];
(tsum+=sum[x])%=P;
(ts2+=s2[x])%=P;
return;
}
if(c<=pos[x]&&pos[x]<=d){
if(real[x])tsize++;
(tsum+=val[x])%=P;
(ts2+=sqr(val[x]))%=P;
}
}
int main(){
for(int i=1;i<=n;i++){
insert(rx[X[i]],i,Y[i]%P);
insert(ry[Y[i]],i,X[i]%P);
}
scanf("%d",&T);
while(T--){
while(!((ch=getchar())=='U'||(ch=='D')||(ch=='L')||(ch=='R')||(ch=='Q')));
if(ch=='U'){//y+
change(ry[Y[x]],x,0,0);
Y[x]+=y;
change(ry[Y[x]],x,X[x]%P,1);
change(rx[X[x]],x,Y[x]%P,1);
}
if(ch=='D'){//y-
change(ry[Y[x]],x,0,0);
Y[x]-=y;
change(ry[Y[x]],x,X[x]%P,1);
change(rx[X[x]],x,Y[x]%P,1);
}
if(ch=='L'){//x-
change(rx[X[x]],x,0,0);
X[x]-=y;
change(rx[X[x]],x,Y[x]%P,1);
change(ry[Y[x]],x,X[x]%P,1);
}
if(ch=='R'){//x+
change(rx[X[x]],x,0,0);
X[x]+=y;
change(rx[X[x]],x,Y[x]%P,1);
change(ry[Y[x]],x,X[x]%P,1);
}
if(ch=='Q'){
tsize=tsum=ts2=ans=0;
(ans+=(ts2-((2LL*(Y[x]%P))%P*tsum)%P+(tsize*sqr(Y[x]))%P))%=P;
while(ans<0)ans+=P;
tsize=tsum=ts2=0;
(ans+=(ts2-((2LL*(X[x]%P))%P*tsum)%P+(tsize*sqr(X[x]))%P))%=P;
while(ans<0)ans+=P;
printf("%lld\n",ans);
}
}
return 0;
}


## BZOJ3542：DZY Loves March的更多相关文章

1. BZOJ3542 DZY Loves March 【map + 线段树】

题目链接 BZOJ3542 题解 线段树裸题,,对每一行每一列开线段树 由于坐标很大,用$$map$$维护根下标 化一下式子,只用维护区间和,区间平方和,区间存在的个数 #include<alg ...

2. 【BZOJ】3542: DZY Loves March

题意 $$m * m$$的网格,有$$n$$个点.$$t$$个询问:操作一:第$$x$$个点向四个方向移动了$$d$$个单位.操作二:询问同行同列其他点到这个点的曼哈顿距离和.强制在线.($$n \l ... 3. 数学（数论）BZOJ 3309：DZY Loves Math Description 对于正整数n,定义f(n)为n所含质因子的最大幂指数.例如f(1960)=f(2^3 * 5^1 * 7^2)=3, f(10007)=1, f(1)=0. 给定正整数a,b, ... 4. BZOJ3512：DZY Loves Math IV 传送门 Sol 好神仙的题目.. 一开始就直接莫比乌斯反演然后就 \(GG$$ 了 orz 题解 permui 枚举 $$n$$,就是求 $$\sum_{i=1}^{n}S(i,m)$$ 其中\(S( ...

5. [BZOJ3561] DZY Loves Math VI

(14.10.28改) 本来只想写BZOJ3739:DZY Loves Math VIII的,不过因为和VI有关系,而且也没别人写过VI的题解,那么写下. 不过我还不会插公式…… http://www ...

6. hdu-5646 DZY Loves Partition(贪心)

题目链接: DZY Loves Partition Time Limit: 4000/2000 MS (Java/Others)     Memory Limit: 262144/262144 K ( ...

7. Codeforces 446C —— DZY Loves Fibonacci Numbers（线段树）

题目:DZY Loves Fibonacci Numbers 题意比較简单,不解释了. 尽管官方的题解也是用线段树,但还利用了二次剩余. 可是我没有想到二次剩余,然后写了个感觉非常复杂度的线段树,还是 ...

8. DZY Loves Chemistry 分类： CF 比赛 图论 2015-08-08 15:51 3人阅读 评论(0) 收藏

DZY Loves Chemistry time limit per test 1 second memory limit per test 256 megabytes input standard ...

9. 周赛-DZY Loves Chessboard 分类： 比赛 搜索 2015-08-08 15:48 4人阅读 评论(0) 收藏

DZY Loves Chessboard time limit per test 1 second memory limit per test 256 megabytes input standard ...

## 随机推荐

1. 准备 LVM Volume Provider - 每天5分钟玩转 OpenStack（49）

Cinder 真正负责 Volume 管理的组件是 volume provider. Cinder 支持多种 volume provider,LVM 是默认的 volume provider.Devs ...

2. opencv4-highgui之视频的输入和输出以及滚动条

这是<opencv2.4.9tutorial.pdf>的highgui的三个例子.通过简短的介绍来实现不同函数的理解,省去一些不需要说的东西. 一.增加滑动条 这是opencv中为数不多的 ...

3. spark新能优化之多次使用RDD的持久化或checkPoint

如果程序中,对某一个RDD,基于它进行了多次transformation或者action操作.那么就非常有必要对其进行持久化操作,以避免对一个RDD反复进行计算. 此外,如果要保证在RDD的持久化数据 ...

4. 安装交叉编译arm-linux-gcc环境

设置好交叉编译的执行文件路径贴加到环境变量PATH 设置如下 export PATH=\$PATH:/XXX/XXX/bin /etc/profile /~/.bashrc source  /etc/p ...

5. [经典] Best Time to Buy and Sell Stock

这一系列求最优值的问题变种挺多 1. Say you have an array for which the ith element is the price of a given stock on ...

6. PS 滤镜算法原理——高反差保留 （High Pass）

这个特效简单来说,就是一个高通滤波器, 对图像做高斯滤波,用原图减去高斯滤波后的图,再将差值加上128. clc; clear all; close all; Image=imread('4.jpg' ...

7. rabbitmq安装与高可用集群配置

rabbitmq版本:3.6.12 rabbitmq安装 1.安装openssl wget http://www.openssl.org/source/openssl-1.0.0a.tar.gz &a ...

8. effective c++ 笔记 (31-34)

//---------------------------15/04/20---------------------------- //#32   确定你的public继承塑膜出 is-a 关系 { ...