值域线段树!第十六个点
  • 板块CF12D Ball
  • 楼主冰冻罗非鱼
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/10/27 17:03
  • 上次更新2023/10/27 05:36:23
查看原帖
值域线段树!第十六个点
225941
冰冻罗非鱼楼主2022/10/27 17:03
#include<bits/stdc++.h>
#define ll i << 1
#define rr (i << 1) + 1
#define mid (tl + tr) / 2
using namespace std;
const int MAXN = 1e5;
int n;
map<int,int> m;
struct lady{
	int a,b,c;
}stu[MAXN + 5];
bool cmp(lady a,lady b){
	return a.a > b.a;
}
struct node{
	int mn,cnt;
	vector<int> num;
}tree[4 * MAXN + 25];
void build(int i,int tl,int tr){
	if(tl == tr){
		tree[i].mn = MAXN + 5;
		return;
	}
	build(ll,tl,mid);
	build(rr,mid + 1,tr);
	tree[i].mn = MAXN + 5;
}
void push_up(int i){
	tree[i].mn = min(tree[ll].mn,tree[rr].mn);
	tree[i].cnt = tree[ll].cnt + tree[rr].cnt;
}
vector<int> num;
void change(int i,int tl,int tr,int pos,int num1){
	if(tl == tr){ 
		tree[i].mn = min(tree[i].mn,num1);
		tree[i].cnt++;
		tree[i].num.push_back(num1);
		return;
	}
	if(pos <= mid)change(ll,tl,mid,pos,num1);
	else change(rr,mid + 1,tr,pos,num1);
	push_up(i);
}
int query(int i,int tl,int tr,int l,int r,int num2){
	if(tl > r || tr < l)return 0;
	if(tl >= l && tr <= r && tree[i].mn > num2)return tree[i].cnt;
	if(tl == tr){
		int ans = 0;
		if(tree[i].mn > num2)return tree[i].cnt;
		for(int j = 0; j < tree[i].num.size(); i++){
			if(tree[i].num[j] > num2)ans++;
		}
		return ans;;
	}
	int ans = 0;
	ans = query(ll,tl,mid,l,r,num2) + query(rr,mid + 1,tr,l,r,num2);
	return ans;
}
int ans;
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> stu[i].a;
		num.push_back(stu[i].a);
	}
	for(int i = 1; i <= n; i++){
		cin >> stu[i].b;
		num.push_back(stu[i].b);
	}
	for(int i = 1; i <= n; i++){
		cin >> stu[i].c;
		num.push_back(stu[i].c);
	}
	num.erase(unique(num.begin(),num.end()),num.end());
	sort(num.begin(),num.end());
	for(int i = 1; i <= n; i++){
		stu[i].a = lower_bound(num.begin(),num.end(),stu[i].a) - num.begin() + 1;
		stu[i].b = lower_bound(num.begin(),num.end(),stu[i].b) - num.begin() + 1;
		stu[i].c = lower_bound(num.begin(),num.end(),stu[i].c) - num.begin() + 1;
	}
	build(1,1,num.size());
	sort(stu + 1,stu + 1 + n,cmp);
//	for(int i = 1; i <= n; i++){
//		cout << stu[i].a << " " << stu[i].b << " " << stu[i].c << "\n";
//	}
	int st = 1;
	for(int i = 1; i <= n; i++){
		int cnt = query(1,1,num.size(),stu[i].b + 1,num.size(),stu[i].c);
		if(cnt > 0){
			ans++;
		}
		if(stu[i + 1].a < stu[i].a){
			for(int j = st; j <= i; j++){
				change(1,1,num.size(),stu[j].b,stu[j].c);
			}
			st = i + 1;
		}
	}
	cout << ans;
	return 0;
}
2022/10/27 17:03
加载中...