数点问题_杂项

数点问题

开坑，数点基础太弱了，总是被坐标转换折磨的痛不欲生。

来一些自己总结的减轻痛苦的技巧吧。

• 用演算纸，这个肯定是基础，如果你的大脑不是 64 位的，不要自信到纸也不拿。
• 多换元，一些线性的坐标变换直接用新元代替，不要保留一坨加一减一加常数之类的，譬如说后缀和前缀在后缀数组上的编号不同，但那没关系，你可以先用 $P_i$ 和 $S_i$ 代替，最后再代换。
• 尝试寻找锚定物，寻找一个柿子的现实意义，不要只是对着一个条件做抽象变换，也不要总想着直接从条件推到结果，例如 NOI2023 字符串 的回文部分，推一个式子可能是推出一个不等关系，很难化简，但你先锚定到哪个字符串是合法的哪个是不合法的，就能建出坐标系完成数点。
  • 一般的线性锚定都是无信息损失的。

P9482 [NOI2023] 字符串

给定一个字符串，$q$ 次询问，每次给出 $i,r$，求有多少 $l\in[1,r]$ 满足 $s_{[i,i+l-1]}<\text{rev}(s_{[i+l,i+2l-1]})$，其中 $\text{rev}(s)$ 表示 $s$ 左右翻转。

$n,q\le 10^5$。

首先把 $s_{[i,i+l-1]}<\text{rev}(s_{[i+l,i+2l-1]})$ 变成 $\text{Suf}_i<\text{Pre}_{i+2l-1}$，当然这样会有一些副作用，等会再说，先来解决这个新问题。

比较字典序我们自然想到后缀数组的 $\text{rk}$，于是我们把这个串翻转之后接到自己身上，但不能直接接，为了避免各种麻烦，中间要加上隔断，形如 $s-c_1-\text{rev}(s)-c_2$，其中 $c_1,c_2$ 不能在字符集内，且二者不能相等，为了避免 $\text{rev}(s)$ 错误参与到 $s$ 的比较中。

然后我们就可以愉快列式子，下标从 $1$ 开始的话则 $\text{Suf}_i<\text{Pre}_{i+2l-1}$ 应该写成 $\text{rk}_i<\text{rk}_{2n+3-i-2l}$，发现这就是一个二维数点，将询问按照 $\text{rk}_i$ 从大到小排序，用两棵树状数组分奇偶性询问即可。

然后就是看这个副作用，答案无疑会多统计一些部分，这些部分的 $s_{[i,i+l-1]}=\text{rev}(s_{[i+l,i+2l-1]})$ 但 $\text{Suf}_i<\text{Pre}_{i+2l-1}$，我们瞪大眼仔细看发现这描述了一个回文中心在 $[i+l-1,i+l]$ 的回文串，于是我们用 $\text{manacher}$ 求个回文半径先。

你发现求完回文半径之后，回文串两边的两个不相等的字符唯一决定了 $\text{Suf}_i$ 和 $\text{Pre}_{i+2l-1}$ 的大小关系，所以只需要回文串右边的字符比左边的小那么整个回文串都是被多统计的，应当减掉。

小细节：如果回文串顶到边界了怎么办？

根据我们上面的后缀数组构建规则，我们钦定整个字符串的最后有一个 $c_1$，最前面有一个 $c_2$，使用这个来比较即可。

这个数点问题需要寻找一个锚定物，直接从条件推到结果是很麻烦的，这里的锚定物找的就是左半边字符串是否合法。

设回文串是 $[i-l_i,i+l_i+1]$（$l_i$ 是回文半径），则我们把 $\forall x\in[i-l_i,i],[x,i]$ 都应当被统计到，建立关于 $l,r$ 的平面直角坐标系，你发现这是一条横线。

我们看原来的询问的左半边字符串，$\forall l\in[1,r],[i,i+l-1]$ 是询问范围，这在平面直角坐标系里是一条竖线，扫描线完事！

这个题 Alex_Wei 选了整个串作为锚定物，于是他之后进行了一系列的坐标变换把斜线变成直线，所以说选好锚定物很重要。

HIT2023NOIP联测D2T4 斜线加矩形查

给定 $n$ 个矩形 $(x_1,y_1,x_2,y_2)$ 和 $m$ 次矩形变换 $(f,d)$，每个矩形变换会将某个矩形向八个方向的其中之一 $f$ 位移 $d$ 秒，每秒位移一个单位长度，并在当前的矩形范围进行一次矩形加。初始时刻 $n$ 个矩形初始的位置也执行矩形加。

所有操作之后，给定 $q$ 次询问，每次询问一个点 $(x,y)$ 的值。

$n,m\leq 2.5\times 10^5,x,y,x_1,y_1,x_2,y_2,d\leq 2.5\times 10^5,f\in [1,7],d\geq 0$。

保证任意时刻所有点的坐标都是正数。

我觉得最妙的一个转化就是把每个点的询问转化成求左下角的和，并将矩形的四个端点变成权值：右上左下 $1$，右下左上 $-1$。

然后发现这个可爱的矩形拖影就变成了线段加矩阵和了。

到这里都是基础。

上下左右四个方向的线段肯定好做，就是扫描线。

关键是斜线。

（这个玩意在线似乎做不了。）

老师讲的很笼统，于是我找到了伟大的 @yszs。

先斜线加再矩形查。

本节需要配合图理解。

（每个点差分的方向不同性质也不同，总的规律是不贴边界的一边不能被切。）

下图这种情况就需要换方向差分：

那么我们看怎么做吧。

首先把斜线改成直线，换纵轴。

由于把 $y$ 凭空减掉了 $x$，肯定越往右的地方越靠下，就相当于把整个图压下去一样。

发现变化后的下边界左边并不可能有线段，将其补成一个矩形（下面的矩形实际可以认为是延伸到负无穷，省一次差分，反正保证了全程坐标正数。）。

现在就形如一个矩形查和一个三角查了。

我们不会三角查，所以考虑利用贴着边界的条件将其转化为矩形查。

再开一个区间加区间求和数据结构，将每条线段加入的时候从本来的 $[l,r]$ 变为 $[l+y',r+y']$（$y'=y-x$），查询时也查询 $[l+y',r+y']$。

考虑这样做之后为什么对。

每个相关的横坐标都变成了越靠上越靠右，相当于把整个图向右推了。

同样，利用左边贴着边界的特性，将这个图形补成矩形即可。

（扫描线时差分，扫到下方时候减，上方时加。）

带入坐标：

形如 $y=x+b$ 的直线处理完了，那么 $y=-x+b$ 呢？

如果你还在左下角傻呆呆差分，你会发现套路不好用了，果断改策略，每个点询问右上角的矩形端点（毒瘤的一点，你需要更改你的差分端点位置。）

然后就差不多做完了。

注意不一定所有时候都是 add - query - delete 的顺序，因为有的 delete 起的是 add 的作用，需要仔细甄别。

#include<bits/stdc++.h>
#define gc getchar
#define F(i,a,b) for(int i(a),i##end(b);i<=i##end;i++)
#define def(L1,l,r,y) \
struct L1 {\
    int l,r,y,v,id;\
    bool operator<(const L1 &b)const{return y==b.y?v==b.v?r<b.r:v>b.v:y<b.y;}\
}
#define l(x) ls[x]
#define r(x) rs[x]
#define mid (L+R>>1)
using namespace std;typedef long long ll;
int read() {
    int s=0;char c=gc(),w=0;
    while(c<'0'||c>'9') w|=c=='-',c=gc();
    while(c>='0'&&c<='9') s=s*10+(c^48),c=gc();
    return w?-s:s;
} const int dx[8]={1,1,0,-1,-1,-1,0,1},dy[8]={0,1,1,1,0,-1,-1,-1};
const int N=5e5,M=N,Q=M,C=2e7+5,X=N<<1;
struct P {
    int x,y,v;
} p[N*4],p2[N*4];int pnt,pnt2;    
int rt,snt,sum[C],tg[C],l(C),r(C);
int v[M],r[M],d[M];
struct L {
    void clr() {rt=snt=0;}
    #define up(d) {sum[d]=(R-L+1)*tg[d]+sum[l(d)]+sum[r(d)];}
    void add(int l,int r,int x,int L=-X,int R=X,int &d=rt) {
        if(R<l||r<L) return;!d&&(d=++snt,l(d)=r(d)=sum[d]=tg[d]=0);if(l<=L&&R<=r) return tg[d]+=x,sum[d]+=(R-L+1)*x,void();
        add(l,r,x,L,mid,l(d));add(l,r,x,mid+1,R,r(d));up(d);
    }
    ll q(int l,int r,int L=-X,int R=X,int d=rt,ll t=0) {
        if(R<l||r<L) return 0;if(l<=L&&R<=r) return sum[d]+t*(R-L+1);
        return q(l,r,L,mid,l(d),t+tg[d])+q(l,r,mid+1,R,r(d),t+tg[d]);
    }
} T;ll ans[Q];int n,m,q,lnt1,lnt2,lnt3,lnt4;
def(L1,l,r,y) l1[M+4*N+Q];//for query:r means val(1/-1)
def(L2,d,u,x) l2[M+Q];//for query:u means val(1/-1)
def(L3,l,r,syx) l3[M+3*Q];//sub of y and x
def(L4,l,r,fxy) l4[M+3*Q];//(-x)+(-y)
//L3,L4 id<0 means that triangular query
//L3,L4 true l default to 0,so the l means val(1/-1)
int main() {
    n=read();m=read();q=read();
    F(i,1,n) {
        int x1=read(),y1=read(),x2=read()+1,y2=read()+1;//[x1,x2)[y1,y2)
        p[++pnt]={x1,y1,1};
        p[++pnt]={x2,y2,1};
        p[++pnt]={x1,y2,-1};
        p[++pnt]={x2,y1,-1};
        x2--;y2--;x2++;y1--;
        p2[++pnt2]={x1,y1,-1};
        p2[++pnt2]={x2,y2,-1};
        p2[++pnt2]={x1,y2,1};
        p2[++pnt2]={x2,y1,1};
    }
    F(i,1,m) {
        v[i]=read();r[i]=read();d[i]=read();
        if(!d[i]) continue;
        d[i]--;
        switch(v[i]) {
            case 0:case 4:
                F(j,(r[i]-1<<2)+1,r[i]<<2) {
                    int l=p[j].x,r=p[j].x+dx[v[i]]*d[i];
                    if(l>r) swap(l,r);
                    l1[++lnt1]={l,r,p[j].y,p[j].v,0};
                }
            break;
            case 2:case 6:
                F(j,(r[i]-1<<2)+1,r[i]<<2) {
                    int dd=p[j].y,uu=p[j].y+dy[v[i]]*d[i];
                    if(dd>uu) swap(dd,uu);
                    l2[++lnt2]={dd,uu,p[j].x,p[j].v,0};
                }
            break;
            case 1:case 5:
                F(j,(r[i]-1<<2)+1,r[i]<<2) {
                    int l=p[j].x,r=p[j].x+dx[v[i]]*d[i];
                    if(l>r) swap(l,r);
                    l3[++lnt3]={l,r,p[j].y-p[j].x,p[j].v,0};
                }
            break;
            case 3:case 7:
                F(j,(r[i]-1<<2)+1,r[i]<<2) {
                    int l=p2[j].x,r=p2[j].x+dx[v[i]]*d[i];
                    if(l>r) swap(l,r);
                    l4[++lnt4]={l,r,-p2[j].y-p2[j].x,p2[j].v,0};
                }
            break;
        } d[i]++;
        //将r[i]沿v[i]移动d[i]-1步
        F(j,(r[i]-1<<2)+1,r[i]<<2) p[j].x+=dx[v[i]]*d[i],p[j].y+=dy[v[i]]*d[i];
        F(j,(r[i]-1<<2)+1,r[i]<<2) p2[j].x+=dx[v[i]]*d[i],p2[j].y+=dy[v[i]]*d[i];
    }
    F(i,1,pnt) l1[++lnt1]={p[i].x,p[i].x,p[i].y,p[i].v};
    F(i,1,q) {
        int x=read(),y=read();
        l1[++lnt1]={x,1,y,-2,i};
        l2[++lnt2]={y,1,x,-2,i};
        l3[++lnt3]={1,x,y-x,-2,i};
        l3[++lnt3]={-1,x,y-x,-2,-i};
        l3[++lnt3]={1,0,y,-2,-i};
        l4[++lnt4]={1,x,-x-y,-2,i};
        l4[++lnt4]={-1,x,-x-y,-2,-i};
        l4[++lnt4]={1,0,-y,-2,-i};
    }
    sort(l1+1,l1+lnt1+1);sort(l2+1,l2+lnt2+1);sort(l3+1,l3+lnt3+1);sort(l4+1,l4+lnt4+1);
    T.clr();F(i,1,lnt1) {
        auto x=l1[i];
        if(x.v==-2) ans[x.id]+=x.r*T.q(0,x.l);
        else T.add(x.l,x.r,x.v);
    }
    T.clr();F(i,1,lnt2) {
        auto x=l2[i];
        if(x.v==-2) ans[x.id]+=x.u*T.q(0,x.d);
        else T.add(x.d,x.u,x.v);
    }
    T.clr();F(i,1,lnt3) {
        auto x=l3[i];
        if(x.v==-2) {
            if(x.id>0) ans[x.id]+=x.l*T.q(0,x.r);
        } else {
            T.add(x.l,x.r,x.v);
        }
    }
    T.clr();F(i,1,lnt3) {
        auto x=l3[i];
        if(x.v==-2) {
            if(x.id<0) ans[-x.id]+=x.l*T.q(0,x.r+x.syx);
        } else {
            T.add(x.l+x.syx,x.r+x.syx,x.v);
        }
    }
    T.clr();F(i,1,lnt4) {
        auto x=l4[i];
        if(x.v==-2) {
            if(x.id>0) ans[x.id]+=x.l*T.q(-X,x.r);
        } else {
            T.add(x.l,x.r,x.v);
        }
    }
    T.clr();F(i,1,lnt4) {
        auto x=l4[i];
        if(x.v==-2) {
            if(x.id<0) ans[-x.id]+=x.l*T.q(-X,x.r+x.fxy);
        } else T.add(x.l+x.fxy,x.r+x.fxy,x.v);
    }
    F(i,1,q) printf("%lld\n",ans[i]);
    return 0;
}