不乐意离散化,T了一个点,求大佬帮忙卡一下时间
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <queue>
#include <map>
#include <set>
#define prt printf
#define ll long long
//#define int long long
#define spc putchar(' ')
#define ent putchar('\n')
#define pr_ prt("---")
#define prx prt("***")
#define prtn (putchar('N') , putchar('o'))
#define prty (putchar('Y') , putchar('e') , putchar('s'))
using namespace std;
int read(){
int f = 1 , k = 0;
char c = getchar();
while(c < '0' || c > '9'){
// if(c == '-') f = -1;
c = getchar() ;
}
while(c >= '0' && c <= '9'){
k = (k << 3) + (k << 1) + (c ^ 48);
c = getchar() ;
}
// return (f == 1 ? k : -k);
return k;
}
void output(int now){
// if(now < 0){
// putchar('-');
// output(- now);
// }
// else{
if(now > 9) output(now / 10);
putchar((now % 10) ^ 48);
// }
}
const int maxn = 5e5 + 1 , maxk = 1e7 + 1;
int n , m , ans[maxn];
struct Dot{
int a , b , c , d , val , sp ;
}f[maxn << 1];
//struct BiT{
int C[maxk + 1] ;
int lowbit(int x) { return x & (-x) ;}
void Add(int x , int val){
while(x <= maxk){
C[x] += val ;
x += lowbit(x) ;
}
}
int Ask(int x){
int res = 0;
while(x){
res += C[x] ;
x -= lowbit(x) ;
}
return res ;
}
//} BiT;
bool CMP(const Dot &a , const Dot &b) { return a.b == b.b ? a.c == b.c ? a.d < b.d : a.c > b.c : a.b < b.b ;}
bool cmp(const Dot &a , const Dot &b) { return a.a == b.a ? a.b == b.b ? a.c == b.c ? a.d < b.d : a.c > b.c : a.b < b.b : a.a > b.a ;}
void solve(int l , int r){
// output(l) , spc , output(r) , ent ;
if(l >= r) return ;
int mid = (l + r) >> 1 ; solve(l , mid) , solve(mid + 1 , r) ;
sort(f + l , f + mid + 1 , CMP) , sort(f + mid + 1 , f + r + 1 , CMP) ;
int i = l , j = mid;
while(++ j <= r){
while((f[i].b <= f[j].b) & (i <= mid)) { /*output(i) , spc , output(j) , ent ;*/ Add(f[i].c , f[i].val) , ++ i ;}
ans[f[j].sp] += Ask(f[j].d) - Ask(f[j].c - 1);
}
for( ; l<i ; l++) { Add(f[l].c , -f[l].val) ;}
}
signed main(){
n = read() , m = read() ;
for(int i=1 ; i<=n ; i++) { f[i].b = f[i].a = read() + 1 , f[i].c = read() + 1 , f[i].val = 1 ;}
for(int i=n+1 ; i<=n+m ; i++) { f[i].a = read() + 1, f[i].c = read() + 1 , f[i].b = read() + 1 , f[i].d = read() + 1 ; f[i].sp = i - n ;}
sort(f + 1 , f + n + m + 1 , cmp) ;
solve(1 , n + m) ; for(int i=1 ; i<=m ; i++) output(ans[i]) , ent ;
return 0;
}
/*
给出 [(a,b) , (c,d)] a <= x <= n , c <= y <= d , (x,y) = 1 , \to ai <= aj , bi >= bj , ci <= cj <= di , \板子三维偏序
*/