在线求助!!!
查看原帖
在线求助!!!
987758
CaoSheng_zzz楼主2024/8/14 16:31

不乐意离散化,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 , \板子三维偏序
*/
2024/8/14 16:31
加载中...