mydcwfy's Blog

P3755

Posted on
Symbols count in article: 904 Reading time ≈ 2 mins.

同步发表于 P3755 题解。

0. 前置知识 & 废话

本蒟蒻最近学习 CDQ 分治，看到该题，虽然想起了扫描线等方法，但为了训练 CDQ 分治，还是自然写一篇题解。

本文是使用的三维偏序，如果不懂的话，可以A 这道题，想更多了解 CDQ 分治的，一波广告 我的 Blog。

1. 关于 CDQ 分治

CDQ 分治是一个离线分治算法，用于解决三维的问题。

它是在解决二维的基础上，再套一个树状数组来维护时间的先后顺序，复杂度比同类的二维问题多 $\log n$。

相信你 A 了模板题，会对这算法有更深的理解。

2. 关于本题

  1. 有 $n$ 个先给出的点，每一个点有一个权值，在给出 $m$ 个矩形边框，给出两个点 $(x_1,y_1),(x_2,y_2)$，求围住的点的总权值。
  2. $n\leq 10^5,m\leq 10^5,-2^{31}\leq x_1,x_2,y_1,y_2\leq 2^{31}$。

虽然近乎于一道模板题，直接扫描线，但是我们还是可以使用一下 CDQ 分治。

CDQ 分治的关键就在于构造一个三维偏序问题。

注意，有的题解使用的是二维偏序问题，我这里为了更加与模板吻合，构造了第三维，使用标准的三维偏序。

首先，我们可以将其转化为一个二维前缀和的问题，即 $ans=\operatorname{sum}(x_2,y_2)-\operatorname{sum}(x_1-1,y_2)-\operatorname{sum}(x_2,y_1-1)+\operatorname {sum}(x_1-1,y_1-1)$（就是一个容斥原理）。

于是，问题就是求

第一和第二维很简单，直接是 $x$ 和 $y$。

怎样求第三维呢？

可以发现，我们要构造为 $z<z_t$，又因为 CDQ 分治是离线，询问和答案在一起。

于是，我们可以用一个 $z$ 来标记是询问还是原来的点。

我们要加答案的是原来的点，而不是询问，所以我们将原来的点记为 0，询问记为 1。

那么，我们现在求的是：

于是就是一个标准的偏序问题了！

3. 关于 Code

  1. 我们需要使用 long long，因为很可能炸 int。
  2. 实际使用 $z$ 的时候，我们其实不需完全使用原来的三维偏序，其实可以将 $z=0$ 时加入总和即可。

然后就是愉快的上代码时间了！

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N=5e5+10;

struct Node{
    int a,b,c,id,f,p;
    ll sum;
    const bool operator <(const Node &t){
        if (a!=t.a) return a<t.a;
        if (b!=t.b) return b<t.b;
        return c<t.c;
    }
}k[N],tmp[N];

int n,m;
ll ans[N];

void merge_sort(int l,int r)
{
    if (l==r) return;
    int mid=l+r>>1;
    merge_sort(l,mid);merge_sort(mid+1,r);
    int j=l,i=mid+1,h=0;
    ll sum=0;
    while (j<=mid&&i<=r)//k[j].c 为 0 时就加上
        if (k[j].b<=k[i].b) sum+=(!k[j].c)*k[j].p,tmp[h++]=k[j++];
        else k[i].sum+=sum,tmp[h++]=k[i++];
    while (j<=mid) tmp[h++]=k[j++];
    while (i<=r) k[i].sum+=sum,tmp[h++]=k[i++];
    for (int i=l,t=0;t<h;++t,++i) k[i]=tmp[t];
}

int main()
{
    scanf("%d %d",&n,&m);
    for (int i=0,a,b,c;i<n;++i)
    {
        scanf("%d %d %d",&a,&b,&c);
        k[i]=(Node){a,b,0,0,0,c,0};
    }
    int tot=n;
    for (int i=0,a,b,c,d;i<m;++i)
    {
        scanf("%d %d %d %d",&a,&b,&c,&d);
        k[tot++]=(Node){a-1,b-1,1,i,1,0,0};
        k[tot++]=(Node){a-1,d,1,i,-1,0,0};
        k[tot++]=(Node){c,d,1,i,1,0,0};
        k[tot++]=(Node){c,b-1,1,i,-1,0,0};
    }

    sort(k,k+tot);
    merge_sort(0,tot-1);

    for (int i=0;i<tot;++i)
        if (k[i].c) ans[k[i].id]+=k[i].sum*k[i].f;
    for (int i=0;i<m;++i) printf("%lld\n",ans[i]);
    return 0;
}