D. Ball-（CDQ分治）

D. Ball

题目大意：

$n$个$(a,b,c)$，类型的对。问有多少个对存在严格大于关系。

思路：

多维偏序先排序降维。
$CDQ$时习惯用左区间更新右区间，故排序按降序排序。
第二维采用归并排序的方法。
题目的特殊地方在于：对单个对只用判断是否存在不需要记录个数
第三维的树状数组可以省去。

思考分治时左区间如何更新右区间。
分治时对二维排序的同时可以对第三维取最值，当取到右区间的值时直接和最值比较即可。

但会有一个很蛋疼的问题，一维不能保证严格大于，只是大于等于。
上述分治策略在两区间存在一维相同情况下，最值会偏大。

在分治时合并区间后一维降序不能保证，但区间与区间之间保证降序。
故右区间一维只可能和左区间最小值相同。
记录两个最值一个包含左区间最小，一个不包含即可。

具体看代码。

Code:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#include 
#define guo312 std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll long long
#define Inf LONG_LONG_MAX
#define inf INT_MAX
#define endl "\n"
#define PI 3.1415926535898
using namespace std;
const int N=5e5+10;

int n;
struct PW{
	int ai,bi,ci,ans;	
}a[N];

bool cmp_ai(PW &s1,PW &s2){
	return s1.ai>s2.ai;
}

bool cmp_bi(PW &s1,PW &s2){
	return s1.bi>s2.bi;
}

int lg[N];
void init(){
	lg[1] = 0, lg[2] = 1;  
    for(int i = 3 ; i < N ; i ++)
    lg[i] = lg[i >> 1] + 1; 
}

int minn[N][20];
void work(){  // ST表
	init();
	for(int j = 0 ; j <= 19 ; j ++){
        for(int i = 1 ; i + (1 << j) - 1 <= n; i ++){
            if(!j) minn[i][j] = a[i].ai;
            else minn[i][j] = min(minn[i][j - 1],minn[i + (1 << j - 1)][j - 1]);
        }
    } 
}

int query(int l ,int r){
    int k = lg[r - l + 1];
    return min(minn[l][k], minn[r + 1 - (1 << k)][k]);
}

void CDQ(int l,int r){
	if(l==r) return;
	int mid=l+r>>1;
	CDQ(l,mid); CDQ(mid+1,r);
	int minn=query(l,mid),maxn1=0,maxn2=0;
	for(int i=mid+1,j=l;i<=r;i++){
		while(j<=mid&&a[j].bi>a[i].bi){  // 保证二维严格大于
			maxn1=max(maxn1,a[j].ci);
			if(a[j].ai!=minn){
				maxn2=max(maxn2,a[j].ci);
			}
			j++;
		}
		if(a[i].ai==minn){
			if(maxn2>a[i].ci){
				a[i].ans=1;
			}
		}
		else if(maxn1>a[i].ci){
			a[i].ans=1;
		}
	}
	sort(a+l,a+r+1,cmp_bi);
}

int main(){
guo312;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].ai;
	}
	for(int i=1;i<=n;i++){
		cin>>a[i].bi;
	}
	for(int i=1;i<=n;i++){
		cin>>a[i].ci;
	}
	sort(a+1,a+1+n,cmp_ai);
	work(); CDQ(1,n); int ans=0;
	for(int i=1;i<=n;i++){
		if(a[i].ans) ans++;
	}
	cout<<ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106