BZOJ3542：DZY Loves March

询问是要求

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

最新文章

热门文章