题解 P3755 【[CQOI2017]老C的任务】

· · 题解

给大家提供一个分块的做法

众所周知 ，分块算法是一个非常有效的暴力算法，学会分块能在考试想不出正解时拿到较多的分，甚至AC

关于CDQ分治和离线扫描线等等算法其他题解已经讲得很清楚啦，所以我来讲讲分块怎么在这道题中运用，理解难度极低，一定能看懂

预处理

先将所有点的x坐标离散化后分块（即把x坐标排序后以sqrt(n)为大小分组），把每个点放在所在块内，再将每个块内的点按照y坐标排序，处理每块的pi前缀和

查询

对于询问矩形形，先统计正方形中部的答案（即下图黑色箭头部分），再统计正方形左右端点所在块内的答案（粉色）

中部答案统计 枚举每个块在排好序的y坐标数组中二分找到上界和下界，利用前缀和统计答案（复杂度log）

两端答案统计 枚举块内每个点，判断是否在矩形内部，如果在则统计答案

复杂度

预处理 O(nlogn)，一次查询 O(sqrt(n)logn)

注意

  1. i/(块的大小) 可能为0 ，为了方便处理推荐+1
  2. 在查询时应判断左右两断点是否位于同一块内否则只有10分

代码如下

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#define N 100005
#define int long long
#define ONLINE_JUDGE

using namespace std;

struct Node{
    int x,y,z;
    Node(int x,int y,int z){
        this->x = x;
        this->y = y;
        this->z = z;
    }
    Node(){};
}a[1000][1000];

int dx[N],xi[N],yi[N],zi[N];
int num[1000],s[1000][1000],b[1000][1000];

inline bool operator < (const Node &a,const Node &b){
    return a.y < b.y;
}

signed main() {
    #ifndef ONLINE_JUDGE
    freopen("T2.in","r",stdin);
    freopen("T2.out","w",stdout);
    #endif
    int n,m;
    scanf("%lld%lld",&n,&m);
    int rt = sqrt(n); //块大小
    int mx = n/rt + 1; //块个数
    for(int i=1;i<=n;i++){
        scanf("%lld%lld%lld",&xi[i],&yi[i],&zi[i]);
        dx[i] = xi[i];
    }
        //对x离散化
    sort(dx+1,dx+n+1);
    int tx = unique(dx+1,dx+n+1) - dx - 1;
    for(int i=1;i<=n;i++){
        int px = lower_bound(dx+1,dx+tx+1,xi[i]) - dx;
        a[px/rt+1][++num[px/rt+1]] = Node(xi[i],yi[i],zi[i]);
    }
    for(int i=1;i<=mx;i++){
        sort(a[i]+1,a[i]+num[i]+1);
        for(int j=1;j<=num[i];j++){
            s[i][j] = s[i][j-1] + a[i][j].z; //y前缀和
            b[i][j] = a[i][j].y; //y坐标查询数组
        }
    }
    int x,y,x2,y2;
    for(int i=1;i<=m;i++){
        scanf("%lld%lld%lld%lld",&x,&y,&x2,&y2);
        int px1 = lower_bound(dx+1,dx+tx+1,x) - dx;
        int px2 = upper_bound(dx+1,dx+tx+1,x2) - dx;
        int ans = 0;
            //查询中部
        for(int j=px1/rt+1+1;j<=px2/rt+1-1;j++){
            int py1 = lower_bound(b[j]+1,b[j]+num[j]+1,y) - b[j];
            int py2 = upper_bound(b[j]+1,b[j]+num[j]+1,y2) - b[j] - 1;
            ans += s[j][py2] - s[j][py1-1];
        }
            //查询两端
        for(int j=1;j<=num[px1/rt+1];j++){
            if(a[px1/rt+1][j].x>=x&&a[px1/rt+1][j].y>=y&&a[px1/rt+1][j].x<=x2&&a[px1/rt+1][j].y<=y2){
                ans += a[px1/rt+1][j].z;
            }
        }
        if(px1/rt!=px2/rt){
            for(int j=1;j<=num[px2/rt+1];j++){
                if(a[px2/rt+1][j].x>=x&&a[px2/rt+1][j].y>=y&&a[px2/rt+1][j].x<=x2&&a[px2/rt+1][j].y<=y2){
                    ans += a[px2/rt+1][j].z;
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}