园丁的烦恼-题解

· · 题解

关于本题

由于作者比较蒟蒻，所以做这道题的时候调试了非常之久......然后被卡常了？？？

反正由于常数问题，最后不得不将cin改为快读，才在400ms的时差下惊险通过此题。。。

因为本题题解大部分都看不懂，所以特意写一篇来让大家理解

关于做法

本题因为树的坐标均为给定的， 而查询比较多， 所以考虑使用2维前缀和QAQ， 对于每一个点我们都建立一个S_{i,j}表示以(0,0)为左下坐标，(i,j)为右上坐标的矩阵内部有多少课树。

那么对于每一个查询左下为点(a, b)，右上为点(c, d)的矩阵的查询，可以将之进行拆分。如下图：

则图中的黑色部分为整个大的黑色部分也就是S{c,d}减去旁边两个红色边所（自行想象一下）形成的矩形，也就是 $S{a,d}和 S_{c,b}$ ; 注意到图中灰边矩形被减去了两次，所以还应当被加上上一次，所以有：黑色矩形中的树的数量为下式：

黑色矩形 = S_{c,d} + S_{a-1,b-1} - S_{a-1,d}-S_{c,b-1}

(自行想一想为什么是a - 1和b - 1)

(上面那一串话比较拗口搞不懂的话，其实您可以考虑画一张类似的如上的图，然后根据S_{i,j}的定义来手动模拟一下上式的计算过程)

所以目前的问题就转化成为了求出上述的2维前缀和了。

但由于本题数据范围过大，所以直接使用二维前缀和肯定是会炸的（不仅仅是因为它是2维，还有因为这里的前缀和对应的是题中坐标，而坐标过于广泛），所以考虑先对坐标进行离散化，然后对于所有的坐标（包括询问坐标）按照x轴进行排序，

按照x坐标排序后，我们进行前缀和操作的时候就不需要考虑x坐标了，然后同时将y坐标离散化掉（我是用排序离散化掉y的）

Q1：为什么按x坐标排序后就不需要考虑x坐标了

A1:因为排序后一定有后面来的点的x坐标一定比前面所有的x坐标都大，故当这个点为询问时只需要判断比该点的y坐标小的点有多少个即可。

所以之后对于每一个按照x坐标顺序读入的树点，可以将之分为两类操作：

(1):加入一个树点

(2):询问比该点y坐标要小的点数量

介于上述两个操作，我们可以显然可以使用一个数据结构来操作。（树状数组这么短为什么不用它呢？）

所以，下面给出代码了：（直接抄是肯定不会对的啦。）

#include<bits/stdc++.h>
using namespace std;
const int N = 3000000 + 5;
const int M = 1e7 + 5;
int tree[N], n, m;
struct node
{
    int x, y, id, qs, ut;
}t[N];
int cnt;
int qy[N], ans[N];
//刘氏快读
#define Finline __inline__ __attribute__ ((always_inline))
Finline char get_char()
{
    static char buf[200000001], *p1 = buf, *p2 = buf + fread(buf, 1, 200000000, stdin);
    return p1 == p2 ? EOF : *p1 ++;
}
inline int read(){
    int num = 0;
    char c;
    while((c = get_char()) < 48);
    while(num = num * 10 + c - 48, (c = get_char()) >= 48);
    return num;
}
//以上均为刘氏快读优化 
bool cmp(node r1, node r2)
{
    if(r1.x == r2.x) 
        if(r1.y == r2.y) return r1.qs <= r2.qs;//x,y均相同的情况下优先处理树点而不是询问点
    if(r1.x == r2.x)
        return r1.y < r2.y;//x相同则按y排序
    return r1.x < r2.x ; 
}
int lowbit(int x)//树状数组
{   
    return x&(-x);
}
int find1(int x)// 2分查找找出离散化后的y
{
    int l = 1, r = cnt;
    while(l < r)
    {
        int mid = (l + r) / 2;
        if(qy[mid] < x)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return l;
}//考虑优化find1？？？不知道怎么优化啊QAQ？？？离散化？？？ 
void add(int root, int rx, int ry, int rq)
{
    cnt++;
    t[cnt].x = rx;
    t[cnt].y = ry;
    t[cnt].id = root;
    t[cnt].qs = rq;
    qy[cnt] = ry;
}//加入一个点
void add_tree(int root, int k)//树状数组加入点
{
    for(int i = root; i <= cnt; i += lowbit(i))//从编号开始，每次向上依次传值。。。 
        tree[i] += k;
}
int find(int root)查找比该点y小的点有多少个
{
    int num = 0;
    for(int i = root; i != 0; i -= lowbit(i))
        num += tree[i];//从节点x开始，依次找到下路 
    return num;
}
void q_read()
{
    int p;
    n = read();
    m = read();
    int sx, sy;
    for(int i = 1; i <= n; i++)
    {
        sx = read(); sy = read();
        add(i, sx, sy, 0);//读入 
    }
    int a, b, c, d;
    for(int i = 1; i <= m; i++)
    {
        a = read(); b = read(); c = read(); d = read();
        p = m ;
        add(i, a - 1, b - 1, 1);//0,1表示这个数是否为问题 
        add(i + p, c, d, 1);
        add(i + 2 * p, a - 1, d, 1);
        add(i + 3 * p, c, b - 1, 1);
    }
}
void doit()
{
    sort(t + 1, t + cnt + 1, cmp);//通过关于x的排序离散化掉x
    sort(qy + 1, qy + cnt + 1);//通过关于y的排序离散化掉y
    for(int i = 1; i <= cnt; i++)
    {
        int tof = find1(t[i].y);//查找值为t[i].y的坐标的点在离散化后的y序列中的位置
        if(t[i].qs == 0)//是树点
            add_tree(tof, 1);//加入一个点
        else//是询问
            ans[t[i].id]+=find(tof);//记录答案
    }
}
int qans(int x)
{
    int p = m ;
    return ans[x] + ans[x + p] - ans[x + 2 * p] - ans[x + 3 * p];//之前讲的前缀和，把最后一个1 * p改为3 * p即可A了
}
void write()//输出程序
{
    for(int i = 1; i <= m; i++)
        cout << qans(i) <<endl;
}
//以下是优美的主程序 
int main()
{
    q_read();
    doit();
    write();
    return 1;//防止抄袭
}