20pts TLE求助 码风清晰
查看原帖
20pts TLE求助 码风清晰
411141
alpharchmage楼主2023/11/25 15:59

RT

#include<bits/stdc++.h>
#define mod 998244353
#define int long long
using namespace std;
array<int , 200001> num;
int T = 0 , ans = 0;
struct Scanner{
	int maxy;
	int miny;
	int x;
	int flag;
};
array<Scanner , 200001> scanner;
struct Tree{
	int l;
	int r;
	int sum;
	int cnt;
};
array<Tree , 8000000> tree;
void pushup(int k)
{
//	if(k == 1)
//	{
//		cout << tree.at(k << 1).sum << ' ' << tree.at(k << 1 | 1).sum << endl;
//		cout << tree.at(k << 1).l << ' ' << tree.at(k << 1).r << ' ' << tree.at(k << 1).sum << endl;
//		cout << tree.at(k << 1 | 1).l << ' ' << tree.at(k << 1 | 1).r << ' ' << tree.at(k << 1 | 1).sum << endl;
//	}
	if(tree.at(k).cnt)
	{
		tree.at(k).sum = num.at(tree.at(k).r) - num.at(tree.at(k).l);
		return;
	}
	tree.at(k).sum = tree.at(k << 1).sum + tree.at(k << 1 | 1).sum;
	return; 
}
void build(int l , int r , int k)
{
	tree.at(k).l = l;
	tree.at(k).r = r;
	tree.at(k).sum = tree.at(k).cnt = 0;
	if(l + 1 == r)
	{
		return;
	}
	int mid = l + (r - l) / 2;
	build(l , mid , k << 1);
	build(mid , r , k << 1 | 1);
	pushup(k);
	return;
}
void update(int l , int r , int k , int v)
{
	if(l <= tree.at(k).l && tree.at(k).r <= r)
	{
		tree.at(k).cnt += v;
//		cout << k << ' ' << tree.at(k).l << ' ' << tree.at(k).r << ' ' << tree.at(k).sum << endl;
		pushup(k);
		return;
	}
	update(l , r , k << 1 , v);
	update(l , r , k << 1 | 1 , v);
	pushup(k);
	return;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> T;
	for(int i = 1;i <= T;++ i)
	{
		int a1 = 0,b1 = 0,a2 = 0,b2 = 0;
		cin >> a1 >> b1 >> a2 >> b2;
		scanner.at(i).maxy = scanner.at(i + T).maxy = b2;  
		scanner.at(i).miny = scanner.at(i + T).miny = b1; 
		scanner.at(i).flag = 1 , scanner.at(i + T).flag = -1;
		scanner.at(i).x = a1 , scanner.at(i + T).x = a2;
		num.at(i) = b1 , num.at(i + T) = b2;
	}
	sort(num.data() + 1 , num.data() + T * 2 + 1 , [&](int x , int y){return x < y;});
	sort(scanner.data() + 1 , scanner.data() + T * 2 + 1 , [&](Scanner a , Scanner b){return a.x < b.x;});
	int tot = unique(num.data() + 1 , num .data() + T * 2 + 1) - num.data() - 1;
//	for(int i = 1;i <= tot;++ i)
//	{
//		cout << num.at(i) << ' ';
//	}
//	cout << endl;
//	for(int i = 1;i <= T * 2;++ i)
//	{
//		cout << scanner.at(i).miny << ' ' << scanner.at(i).maxy << ' ' << scanner.at(i).x << ' ' << scanner.at(i).flag << endl;
//	}
	for(int i = 1;i <= T * 2;++ i)
	{
		scanner.at(i).maxy = lower_bound(num.data() + 1 , num.data() + T * 2 + 1 , scanner.at(i).maxy) - num.data();
		scanner.at(i).miny = lower_bound(num.data() + 1 , num.data() + T * 2 + 1 , scanner.at(i).miny) - num.data();
	}
//	for(int i = 1;i <= T * 2;++ i)
//	{
//		cout << scanner.at(i).miny << ' ' << scanner.at(i).maxy << ' ' << scanner.at(i).x << ' ' << scanner.at(i).flag << endl;
//	}
	build(1 , tot , 1);
	for(int i = 1;i < T * 2;++ i)
	{
		update(scanner.at(i).miny , scanner.at(i).maxy , 1 , scanner.at(i).flag);
//		cout << (scanner.at(i + 1).x - scanner.at(i).x) << ' ' << tree.at(1).sum << endl;
		ans = (ans + tree.at(1).sum * (scanner.at(i + 1).x - scanner.at(i).x)); 
	}
	cout << ans << endl;
	return 0;
} 
2023/11/25 15:59
加载中...