The two-dimensional partial order problem

relationship of partial order：

Presumably, it is, to satisfy self-reflexivity, anti-symmetry, and transmissibility.
Graphing the strict partial order relation yields a DAG (directed acyclic graph)

The two-dimensional partial order problem is that given\(n\) elements, each of which has\(2\)attributes, defining some sort of partial order relationship, for all\(x_i\) seek\(x_j \prec x_i\) The number of

A basic method of operation is to have one attribute sorted by size and another attribute utilizing a tree array/lineage tree for quantities, summing, etc. This type of processing relies on the premise that the query can be taken offline.

Here's a classic example of a two-dimensional number point problem.

P2163 [SHOI2007] The Gardener's Trouble

Approximate subject matter:

The first line has two integers\(n, m\), denote the number of points and the number of queries, respectively.
accept\(n\) Lines, two integers per line\(x, y\), denotes the existence of a coordinate\((x, y)\) of the points. It is possible that there are points located at the same coordinates.
accept\(m\) Rows, four integers per row\(a, b, c, d\), which indicates that the query starts with\((a, b)\) for the lower left corner.\((c, d)\) is the number of points inside the rectangle (including the border) in the upper right corner.
\(0 \le n \le 5 \times 10^5\)，\(1 \le m \le 5 \times 10^5\)，\(0 \le x, y, a, b, c, d \le 10^7\)，\(a \le c\)，\(b \le d\)。

Initial thoughts: for\(n\) ，\(m\) For smaller cases, a two-dimensional prefix sum can be used.

Can be clever with each point\(x\) The order in which the values are processed, separated by the query rectangle of the\(x\) The impact of the interval. For\(y\) value, use a tree array to query the desired range.

The following practices can be thought of:

For all queries offline. Split each rectangle into\((a-1,b-1)(a-1,d)(c,b-1)(c,d)\) Four points, like a prefix and counts as a contribution.
Processing each point in turn will ask the point in the\(x’\) The previous point.\(y\) values are all added to the tree array in the query\(y'\) Calculate the contribution.

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
inline int read(){
    int f=1,x=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return f*x;
}
int n,m;
int cnt1;
struct node{
    int x,y;
    int id,ff;
    bool operator<(const node& p)const{
        if(x==)return y<;
        else return x<;
    }
}a[N],b[N*4];
int ans[N];
int mp[N*3],len;
int c[N*3];
inline int lowbit(int x){
    return x&-x;
}
inline void upd(int x,int w){
    for(int i=x;i<=len;i+=lowbit(i)){
        c[i]+=w;
    }
}
inline int qur(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i)){
        res+=c[i];
    }
    return res;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        a[i].x=read(),a[i].y=read();
        mp[++len]=a[i].y;
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=m;i++){
        int xa=read(),ya=read(),xb=read(),yb=read();
        b[++cnt1]={xa-1,ya-1,i,1};
        b[++cnt1]={xa-1,yb,i,-1};
        b[++cnt1]={xb,ya-1,i,-1};
        b[++cnt1]={xb,yb,i,1};
        mp[++len]=ya-1,mp[++len]=yb;
    }
    sort(b+1,b+1+cnt1);
    sort(mp+1,mp+1+len);
    len=unique(mp+1,mp+1+len)-mp-1;
    for(int i=1;i<=n;i++){
        a[i].y=lower_bound(mp+1,mp+1+len,a[i].y)-mp;
    }
    for(int i=1;i<=cnt1;i++){
        b[i].y=lower_bound(mp+1,mp+1+len,b[i].y)-mp;
    }
    int now=0;
    for(int i=1;i<=cnt1;i++){
        int x=b[i].x,y=b[i].y;
        int id=b[i].id,ff=b[i].ff;
        while(now+1<=n&&a[now+1].x<=x){
            now++;
            upd(a[now].y,1);
        }
        ans[id]+=qur(y)*ff;
    }
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}