题目概述

CF GYM 102861M

解题报告

首先要仔细读题，题目保证了覆盖的点的个数总和不超过 $10^6$ ，因此只需要想办法快速找到被覆盖的点就行了。

如果按照题目里的说法很难快速查找，因此我们变换坐标系：

1. 把两条边的夹角改成直角：$y\to 2y$
2. 把 $x$ 轴 $y$ 轴顺时针转 $\pi\over 4$ ：$(x,y)\to (x-y,x+y)$

总的来说，把 $(x,y)\to(x-2y,x+2y)$ 。

这样转化之后，就变成了二维偏序问题，用一些简单数据结构就可以快速查找覆盖的点，比如二分+ST表。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=100000,LOG=16,MOD=1e9+7,BA=5782344;

int n,m,lg[maxn+5],ans[maxn+5];LL MAX[maxn+5][LOG+1];
struct data {LL x,y;int id;} p[maxn+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
inline bool cmp(const data &a,const data &b) {return mp(a.x,a.y)<mp(b.x,b.y);}
LL Max(int L,int R) {int k=lg[R-L+1];return max(MAX[L][k],MAX[R-(1<<k)+1][k]);}
int Find(int l,LL x){
    int L=0,R=n-l;
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        Max(l,l+mid)>=x?R=mid-1:L=mid+1;
    return l+L;
}
int main(){
    freopen("M.in","r",stdin);freopen("M.out","w",stdout);
    readi(n);readi(m);
    for (int i=1;i<=n;i++){
        LL x,y;readi(x);readi(y);p[i].id=i;
        p[i].x=x-(y<<1);p[i].y=x+(y<<1);
    }
    sort(p+1,p+1+n,cmp);
    for (int i=1;i<=n;i++) MAX[i][0]=p[i].y;
    for (int j=1;(1<<j)<=n;j++)
        for (int i=1;i+(1<<j)-1<=n;i++)
            MAX[i][j]=max(MAX[i][j-1],MAX[i+(1<<j-1)][j-1]);
    for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    for (int t=1,lst=0;t<=m;t++){
        int a,b;LL X,Y,x,y;readi(a);readi(b);
        X=-1-(lst+a)%MOD;Y=(lst+b)%MOD;x=X-(Y<<1);y=X+(Y<<1);
        int L=1,R=n;
        for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
            p[mid].x>=x?R=mid-1:L=mid+1;
        if (L>n) {printf("%d\n",lst=0);continue;}
        ans[0]=0;for (int nxt=Find(L,y);nxt<=n;nxt=Find(nxt+1,y)) ans[++ans[0]]=p[nxt].id;
        sort(ans+1,ans+1+ans[0]);lst=0;
        for (int i=ans[0];i;i--) lst=((LL)lst*BA+ans[i])%MOD;
        printf("%d\n",lst);
    }
    return 0;
}