Scan line, weight segment tree

Two dimensional count

It's not easy to understand , It's rough, isn't it . But when I understand it, I will really sigh

focus：

        Mutual exclusion theory

 

        vx It is stored at various points x coordinate , Later, it is used for discretization

        vector<array<int, 4>> event    Indicates an event , Insert a point , Add , reduce   It's an event of different types

        Use the dynamic idea of scanline , Give priority to y Sort , The second is the type of event and x, Finally, the number of the query . Sorting time , Type of event and x In this topic, the order can be interchanged （ Measured ）, The data stored in the array should be stored according to your requirements for sorting .  array Sorting and pair similar , All of them compare the first , And then the second one ....

        

 

 

// problem :  Mutually exclusive 、 discretization 、 Tree array  

#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> PII;
#define pb push_back
const int N = 2e5 + 5;
int n, q, m, c[N], ans[N];
std::vector<int> vx;
vector<array<int, 4>> event;
void modify(int x, int d) {
    for(; x <= m; x += x & -x)
        c[x] += d;
}
int query(int x) {
    int res = 0;
    for(; x; x -= x & -x) 
        res += c[x];
    return res;
}
int main(){
    scanf("%d %d", &n, &q);
    for(int i = 1; i <= n; ++i) {
        int x, y; scanf("%d %d", &x, &y);
        vx.push_back(x);
        event.push_back({y, 0, x});
    }

    for(int i = 1; i <= q; ++i) {
        int x1, x2, y1, y2;
        scanf("%d %d %d %d", &x1, &x2, &y1, &y2);
        event.push_back({y2, 1, x2, i});   //  Event type   1： Add   2： Subtraction （ interchangeable ）
        event.push_back({y1 - 1, 1, x1 - 1, i});  //  But the insertion must be 0 （ High priority ）
        event.push_back({y2, 2, x1 - 1, i});
        event.push_back({y1 - 1, 2, x2, i});
    }

    sort(vx.begin(), vx.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());
    sort(event.begin(), event.end());

    m = vx.size();   // vx After discretization , Only m A little bit , So the coordinates are [1,m] , The size of the tree array is m

    for(auto evt : event) {
        if(evt[1] == 0) {
            int pos = lower_bound(vx.begin(), vx.end(), evt[2]) - vx.begin() + 1;
            modify(pos, 1);
        } else {
            int pos = upper_bound(vx.begin(), vx.end(), evt[2]) - vx.begin();
            int tmp = query(pos);
            if(evt[1] == 1)ans[evt[3]] += tmp;
            else ans[evt[3]] -= tmp;
        }
    }

    for(int i = 1; i <= q; ++i)
        printf("%d\n", ans[i]);

    return 0;
}