题意
\(m * m\)的网格，有\(n\)个点。\(t\)个询问：操作一：第\(x\)个点向四个方向移动了\(d\)个单位。操作二：询问同行同列其他点到这个点的曼哈顿距离和。强制在线。（\(n \le 10^5，m \le 10^{18}\)）
分析
没啥好分析的，就是推一下能推出每行每列的一个式子来，然后套两个区间维护的结构就行了。
题解
set + 线段树
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mo=1e9+7, N=100005;
int n;
ll x[N], y[N];
template<class T>
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<R) {ret=ret+ask(L, R, mid+1, r, x->c[1]);}return ret;
}
map<ll, node *> X, Y;
void add(ll x, int s, int go, int id, map<ll, node *> &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<ll, node *> &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;
}
