原题链接

AtCoder题目以思维难度高而著名，据说大多数难题都没用到什么高级算法。代码量不大，难点在分析性质上，有的题想一天都想不到怎么做。问题描述言简意赅，有些题目的解法创意令人赞叹，能够锻炼思维，学到不少东西。可以尝试一些该网站上的进阶题目。

题目大意

给定$N$个内角要么90度要么270度的简单多边形（任意两条不相邻的边不能相交），多边形之间可以重叠

第$i$个多边形描述为按边连接的某个方向（顺逆时针）顺序给出$M_{i}$个顶点坐标（保证在第一象限和$x$/$y$正半轴），第一个点与最后一个点相连

每一个多边形的点符合以下要求

  • 所有的第$j$（奇数）个的点的横坐标$x_{j}$与其下一个点$x_{j+1}$相同

  • 所有的第$j$（偶数）个的点的纵坐标$y_{j}$与其下一个点$y_{j+1}$相同

随后有$Q$次询问，每次给出一个坐标$(x, y)$，求出点$(x+0.5,y+0.5)$上有多少个多边形

题解

当时想了几种方法都行不通，凭感觉认为应该把区间修改查询（树状数组或者线段树）作为核心，但此题情景不知道该怎么用，因此也不确定是不是正解。

此题先给出所有信息再做出询问，中途不会对信息做修改，因而可以离线处理

关键点：由于题目中多边形较为特殊，每一条边都会区分多边形内外，而边只可能平行于$x$轴或$y$轴，可以很方便的只按一个方向考虑多边形覆盖情况，这里以一条与$y$轴平行的直线为例，该直线的上下一对顶点可以作为 “之后就是这个多边形的外界” 或是 “之后就是这个多边形的内部” 的标志。

接下来考虑如何确定直线的标志类别

只考虑与$y$轴平行直线的情况下，不难发现外界和内部标志是交替进行的，而多边形最靠左的边必然是内部开始标志

结合前面的离线处理可以想到将点按横坐标$x$离散存储，再按$x$轴正方向扫描式更新平行于$y$轴的直线上的多边形覆盖区间情况，同时处理这条直线上询问过的点，将答案存于数组最后统一输出。

这里选用树状数组作为区间修改查询工具，区间修改的操作也要按横坐标$x$离散存储以便扫描时有序执行。巧合的是，按照点的顺序，树状数组区间修改对应的单点修改值的正负也是交替的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fi first
#define se second
typedef pair<int,int> PII;
const int N=1e6+10;

int n,m,k;
int bit[N],ans[N];
PII a[N];
vector<PII> c[N],d[N];

void update(int x,int k){
    for(int i=x;i<=1e5+10;i+=i&-i) bit[i]+=k;
}

int query(int x){
    int sum=0;
    for(int i=x;i;i-=i&-i) sum+=bit[i];
    return sum;
}

int main(){
    fastIO
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>k;
        int p=0;
        int x,y;
        for(int j=0;j<k;j++){
            cin>>x>>y;
            x++,y++; // 由于树状数组的数学特性, 下标从1开始才有效
            a[j]={x,y};
            if(a[j]<a[p]) p=j; // 找到x,y最小(左下角)的点的下标 (pair默认比较规则)
        }
        int f=1;
        for(int j=0;j<k;j++){ // 从左下角的顶点开始遍历，se是单点修改坐标，f是单点修改值
            c[a[(p+j)%k].fi].push_back({a[(p+j)%k].se,f});
            f*=-1; // f从+1开始不断变号正好能适应点顺/逆时针方向的区间修改需求
        }
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        x++,y++;
        d[x].push_back({y,i});
    }

    for(int i=1;i<=1e5+10;i++){ // 沿x轴正方向扫描式离线处理询问
        for(auto t:c[i]){
            int l=t.fi,x=t.se;
            update(l,x);
        }
        for(auto t:d[i]){
            int y=t.fi,x=t.se;
            ans[x]=query(y);
        }
    }

    for(int i=1;i<=m;i++) cout<<ans[i]<<endl;

    return 0;
}