题意

\(m * m\)的网格，有\(n\)个点。\(t\)个询问：操作一：第\(x\)个点向四个方向移动了\(d\)个单位。操作二：询问同行同列其他点到这个点的曼哈顿距离和。强制在线。（\(n \le 10^5，m \le 10^{18}\)）

分析

没啥好分析的，就是推一下能推出每行每列的一个式子来，然后套两个区间维护的结构就行了。

题解

set + 线段树

#include 
    
     using namespace std;typedef long long ll;const int mo=1e9+7, N=100005;int n;ll x[N], y[N];template
     
      inline void fix(T &x) {    if(x>=mo || x<=-mo) x%=mo;    if(x<0) x+=mo;}struct dat {    int s, sum1, sum2;    void init() {        s=sum1=sum2=0;    }    void add(int _s, int go) {        s+=_s;        sum1+=(ll)go*go%mo*_s; fix(sum1);        sum2+=go*_s; fix(sum2);    }};dat operator + (const dat &a, const dat &b) {    static dat x;    x.s=a.s+b.s;    x.sum1=a.sum1+b.sum1; fix(x.sum1);    x.sum2=a.sum2+b.sum2; fix(x.sum2);    return x;}struct node *null;struct node {    node *c[2];    dat d;    void up() {        d=c[0]->d+c[1]->d;    }    void init() {        d.init();        c[0]=c[1]=null;    }}Po[5000005], *iT=Po, *bin[5000005], **iTbin=bin;node *newnode() {    node *x;    if(iTbin!=bin) x=*(--iTbin);    else {        if(iT==Po+5000000) x=new node;        else x=iT++;    }    x->init();    return x;}void delnode(node *&x) {    *iTbin=x;    iTbin++;    x=null;}void seginit() {    null=newnode();    null->init();}void update(int p, int s, int go, int l, int r, node *&x) {    if(x==null) {        x=newnode();    }    if(l==r) {        x->d.add(s, go);        if(x->d.s==0) {            delnode(x);        }        return;    }    int mid=(l+r)>>1;    if(p<=mid) {        update(p, s, go, l, mid, x->c[0]);    }    else {        update(p, s, go, mid+1, r, x->c[1]);    }    x->up();    if(x->d.s==0) {        delnode(x);    }}dat ask(int L, int R, int l, int r, node *x) {    static dat nul={0, 0, 0};    if(x==null) {        return nul;    }    if(L<=l && r<=R) {        return x->d;    }    int mid=(l+r)>>1;    dat ret;    ret.init();    if(L<=mid) {        ret=ask(L, R, l, mid, x->c[0]);    }    if(mid
      
       c[1]);    }    return ret;}map
       
         X, Y;void add(ll x, int s, int go, int id, map
        
          &a) {    if(a.find(x)==a.end()) {        a[x]=null;    }    node *&it=a[x];    update(id, s, go, 1, n, it);    if(it==null) a.erase(a.find(x));}dat ask(ll x, int L, int R, map
         
           &a) { return ask(L, R, 1, n, a[x]);}int main() { seginit(); int m; scanf("%d%d", &n, &m); for(int i=1; i<=n; ++i) { ll _x, _y; scanf("%lld%lld", &_x, &_y); x[i]=_x; y[i]=_y; fix(_x); fix(_y); add(x[i], 1, _y, i, X); add(y[i], 1, _x, i, Y); } int T, ans=0; scanf("%d", &T); while(T--) { char s[5]; int pos; scanf("%s%d", s, &pos); pos^=ans; if(s[0]=='Q') { int L, R; scanf("%d%d", &L, &R); dat d1, d2; d2=ask(x[pos], L, R, X); d1=ask(y[pos], L, R, Y); ans=0; ll ans1=0, ans2=0, tx=x[pos], ty=y[pos]; fix(tx); fix(ty); ans1=-((tx*d1.sum2%mo)<<1)+tx*tx%mo*d1.s+d1.sum1; ans2=-((ty*d2.sum2%mo)<<1)+ty*ty%mo*d2.s+d2.sum1; fix(ans1); fix(ans2); ans=ans1+ans2; fix(ans); printf("%d\n", ans); } else { ll d; scanf("%lld", &d); ll _x=x[pos], _y=y[pos]; if(s[0]=='U') y[pos]+=d; if(s[0]=='D') y[pos]-=d; if(s[0]=='R') x[pos]+=d; if(s[0]=='L') x[pos]-=d; add(_x, -1, _y%mo, pos, X); add(_y, -1, _x%mo, pos, Y); add(x[pos], 1, y[pos]%mo, pos, X); add(y[pos], 1, x[pos]%mo, pos, Y); } } return 0;}