P4623题解

· · 题解

引言：

这道题看题解还没有分块的方法，我就来一发分块吧。

思路：

我们可以存下每个三角形的最大和最小的上下左右端点，然后把在这些端点之间的区间加1，最后直接输出输入的坐标对应的数组（完整块+不完整块）就可以了。

现在介绍一下分块：

分块，是一种可以说是相当暴力的思想。

分块算法的思想是通过适当的划分，预处理一部分信息保存下来，用空间换取时间，达到时空平衡。

基本操作是：将一段序列，分成一定数量的块，每一块有一个长度，表示一段区间。对于区间操作，通过对完整块的整体操作和对不完整块的暴力操作而使复杂度尽可能的低。

Code：

#include<bits/stdc++.h>
using namespace std;
int m,lin,ax,ay,bx,by,cx,cy,lrk[1000005],udk[1000005],n,mu,md,ml,mr,x[1000005],y[1000005];
char l1,l2;
int main(){
    //freopen("burek.in","r",stdin);
    //freopen("burek.out","w",stdout);
    cin>>n;
    for(int j=1;j<=n;j++){
        cin>>ax>>ay>>bx>>by>>cx>>cy;
        md=min(ay,min(by,cy))+1;
        mu=max(ay,max(by,cy));
        ml=min(ax,min(bx,cx))+1;
        mr=max(ax,max(bx,cx));
        for(int i=ml;i<mr;i++){
            while(i%1000==0&&i+1000<mr){
                lrk[i/1000+1]++;
                i+=1000;
            }
            x[i]++;
        }
        for(int i=md;i<mu;i++){
            while(i%1000==0&&i+1000<mu){
                udk[i/1000+1]++;
                i+=1000;
            }
            y[i]++;
        }
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>l1>>l2>>lin;
        if(l1=='x'){
            cout<<x[lin]+lrk[lin/1000+1]<<endl;
        }else{
            cout<<y[lin]+udk[lin/1000+1]<<endl;
        }
    }
}