#include #include #include #include #include using namespace std; typedef long long LL; const int MAXN = 1e6 + 10; const int INF = 0x3f; struct cow{ public: int l, r, id; public: void read(int i){ cin >> l >> r; id = i; } private: void debug(){ printf("l = %d,r = %d,id = %d\n", l, r, id); } }cows[MAXN]; int ans[MAXN]; int n; struct greater_q{ bool operator()(cow a, cow b){ return a.r > b.r; } }; priority_queue<cow, vector, greater_q> q; bool cmp(cow a,cow b){ if(a.l == b.l)return a.r < b.r; return a.l < b.l; } int main() { cin >> n; for(int i = 1;i <= n; i++){ cows[i].read(i); } sort(cows + 1,cows + 1 + n, cmp); int cnt = 0; for(int i = 1;i <= n; i++){ if(q.empty() || q.top().r >= cows[i].l){ cnt++; ans[cows[i].id] = cnt; q.push(cows[i]); } else{ ans[cows[i].id] = ans[q.top().id]; q.pop(); q.push(cows[i]); } } cout << cnt << endl; for(int i = 1;i <= n; i++){ cout << ans[i] << endl; } return 0; }

树状数组好题

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
typedef long long LL;
const int MAXN = 1e6 + 10;
const int INF = 0x3f;
struct ad{
	public:
		void ad_play(){
			cout << "树状数组！\n";
			cout << "我的题解：http://temege.com/p/171/solution\n";
			cout << "欢迎老师来观赏哈哈\n";
			cout << "防抄袭模板..........................\n";
		}
};
struct cow{
	public:
		int l, r, id;
	public:
		void read(int i){
			cin >> l >> r;
			id = i;
		}
	private:
		void debug(){
			printf("l = %d,r = %d,id = %d\n", l, r, id);
		}
}cows[MAXN];
int ans[MAXN];
int n;
struct greater_q{
	bool operator()(cow a, cow b){
		return a.r > b.r;
	}
}; 
priority_queue<cow, vector<cow>, greater_q> q;
bool cmp(cow a,cow b){
	if(a.l == b.l)return a.r < b.r;
	return a.l < b.l;
}
int main()
{
	cin >> n;
	for(int i = 1;i <= n; i++){
		cows[i].read(i);
	}
	sort(cows + 1,cows + 1 + n, cmp);
	int cnt = 0;
	for(int i = 1;i <= n; i++){
		if(q.empty() || q.top().r >= cows[i].l){
			cnt++;
			ans[cows[i].id] = cnt;
			q.push(cows[i]);
		}
		else{
			ans[cows[i].id] = ans[q.top().id];
			q.pop();
			q.push(cows[i]);
		}
	}
	cout << cnt << endl;
	for(int i = 1;i <= n; i++){
		cout << ans[i] << endl;
	}
    return 0;
}