求助,想用离散化+差分来做,找不出来bug在哪,求助求助
查看原帖
求助,想用离散化+差分来做,找不出来bug在哪,求助求助
762458
ln2____楼主2023/8/6 10:00
#include <bits/stdc++.h>
using namespace std;
#define LEN bj.size()

const int N = 4e4 + 10;
typedef pair<int, int> pii;
vector<int> alls;	// 放所有数据 
vector<pii> bj;	// 放左右端点 
int a[N];	// sum
int b[N];	// ini_data

int g_n(int x)
{
	int l = 0, r = alls.size() - 1;
	while (l < r)
	{
		int mid = l + r >> 1;
		if (alls[mid] >= x)
		{
			r = mid;
		}
		else
		{
			l = mid + 1;
		}
	}
	
	return l + 1;
}

void add(int l, int r, int c)
{
	b[l] += c;
	b[r + 1] -= c;
	
	//cout << "Yes" << endl;
}

int main()
{
	int i, n;
	cin >> n;
	for (i = 0; i < n; i++)
	{
		int l, r;
		cin >> l >> r;
		//r--;
		pii x(l, r);
		bj.push_back(x);
		alls.push_back(l);
		alls.push_back(r);
	}
	
	sort(alls.begin(), alls.end());
	alls.erase(unique(alls.begin(), alls.end()), alls.end());
	
	
	
	
	
	
	
	
	
	for (i = 0; i < n; i++)
	{
		int l, r;
		l = g_n(bj[i].first);
		r = g_n(bj[i].second);
		
		
		
//		int c = bj[i].second - bj[i].first;
//		cnt += alls[r] - alls[l];
		
		add(l, r, 1);
		
	}
	

//	for (i = 0; i < n; i++)
//	{
//		cout << bj[i].first << " " << bj[i].second << endl;	
//	} 
	
//	for (i = 0; i <= 2 * n; i++)
//	{
//		cout << b[i] << " ";
//	}
//	
//	cout << endl;
	
//	for (i = 0; i <= 2 * n; i++)
//	{
//		cout << a[i] << " ";
//	}
	
	
	for (i = 1; i <= 2 * n; i++)
	{
		a[i] = a[i - 1] + b[i];
		//cnt += a[i];
	}
	
	
//	for (i = 1; i <= n; i++)
//	{
//		cout << a[i] << " ";
//	}
	
	
	
	int cnt = 0;
	for (i = 1; i <= LEN; i++)
	{
		int l, r;
		if (a[i - 1] == 0 && a[i] != 0)
		{
			l = i - 1;
		}
		if (a[i] != 0 && a[i + 1] == 0)
		{
			r = i;
			cnt += alls[r] - alls[l];
		}
	}

	cout << cnt << endl;
	
	
	
	
	
//	for (i = 0; i < alls.size(); i++)
//	{
//		//cout << alls[i] << " ";
//	}
	
	system("pause");
	
	return 0;
}
2023/8/6 10:00
加载中...