P4623题解

· · 题解

题目传送门

解题思路：桶+差分

看到题解好多大奆都用树状数组，扫描线什么的完全不会啊。但这题其实可以用简单的桶数组来解决。代码量小，时间短。

Part 1 暴力

最简单的想法，对于每条直线，找哪些三角形满足条件。时间复杂度 O(nm)。能拿30pts。

Part 2 桶优化

接下来就要思考如何在 O(1) 的时间内得到一条直线穿过多少三角形。桶能够很好地满足这个需求。再看数据范围，0 \le x_1,y_1,x_2,y_2,x_3,y_3 < 10^6，可以说完美适于桶。

设置两个桶 boxx 和 boxy，分别用来存储直线 x=i 和 y=i 穿过的三角形数量。对于每个三角形，求出三个点中最大和最小的 x 坐标和 y 坐标，将 boxx[(x_{min},x_{max})] 和 boxy[(y_{min},y_{max})] 都 +1。对于每条直线，直接输出答案即可。时间复杂度 O(n^2)。

Part 3 差分维护桶

很容易发现，对于每个三角形，总是在一段区间内 +1。所以可以用差分维护。对于每个三角形，将 boxx[x_{min}+1] 和 boxy[y_{min}+1] 都 +1，boxx[x_{max}] 和 boxy[y_{max}] 都 -1。最后再还原即可。时间复杂度 O(n)。（但其实还原差分数组要进行 10^6 次）

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000007;
int n,m,boxx[maxn],boxy[maxn];
int main(){
    scanf("%d",&n);
    int x,y;
    for(int i=1;i<=n;i++){
        int maxx=-1*(1e9+7),maxy=-1*(1e9+7),minx=1e9+7,miny=1e9+7;
        for(int j=1;j<=3;j++){
            scanf("%d%d",&x,&y);
            maxx=max(maxx,x);maxy=max(maxy,y);
            minx=min(minx,x);miny=min(miny,y);
        }
        boxx[minx+1]++;boxy[miny+1]++;
        boxx[maxx]--;boxy[maxy]--;
    }
    for(int i=1;i<=1000000;i++){
        boxx[i]+=boxx[i-1];boxy[i]+=boxy[i-1];//直接用差分数组还原，压缩空间
    }
    scanf("%d",&m);
    char dir,no;int num=0;
    for(int i=1;i<=m;i++){
        scanf(" %c %c %d",&dir,&no,&num);//这个no只是为了读入方便
        if(dir=='x')printf("%d\n",boxx[num]);
        else printf("%d\n",boxy[num]);
    }
}

ps：建议全程用scanf……别问为什么

（做了一点小改动）