询问是要求

$\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<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;
inline void read(ll&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10LL)+=c-'0';}
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);
return tot;
}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;
}
if(c<pos[x]&&son[x][0])ask(son[x][0],a,pos[x]-1,c,d);
if(d>pos[x]&&son[x][1])ask(son[x][1],pos[x]+1,b,c,d);
}
int main(){
scanf("%d",&n);read(tmp);
for(int i=1;i<=n;i++){
read(X[i]),read(Y[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+
read(x),read(y);x^=ans;
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-
read(x),read(y);x^=ans;
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-
read(x),read(y);x^=ans;
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+
read(x),read(y);x^=ans;
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'){
read(x),read(y),read(z);x^=ans;
tsize=tsum=ts2=ans=0;
ask(rx[X[x]],1,n,y,z);
(ans+=(ts2-((2LL*(Y[x]%P))%P*tsum)%P+(tsize*sqr(Y[x]))%P))%=P;
while(ans<0)ans+=P;
tsize=tsum=ts2=0;
ask(ry[Y[x]],1,n,y,z);
(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 关系 { ...

  9. 使用ConcurrentLinkedQueue惨痛的教训【转】

    转自:http://blog.csdn.net/jackpk/article/details/49634577 服务端原本有个定时任务对一个集合ArrayList 中的消息做处理. 因为考虑到处理消息 ...

  10. 深入学习Make命令和Makefile(下)

    https://www.zybuluo.com/lishuhuakai/note/209300 make是Linux下的一款程序自动维护工具,配合makefile的使用,就能够根据程序中模块的修改情况 ...