程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 2528 Mayor&#39;s posters 線段樹離散化+區間更新

POJ 2528 Mayor&#39;s posters 線段樹離散化+區間更新

編輯：C++入門知識

題目就是一張牆上貼海報，先貼的會被後貼的覆蓋，問最後可以看到多少張海報

題目給的數據 1 <= i <= n, 1 <= l_i <= ri <= 10000000，

這樣直接來超時先不說肯定內存都受不了的，離散化處理，映射的時候沒寫好，弄了挺久的，太搓了

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long

#define LL __int64

#define eps 1e-8

#define inf 0xfffffff

//const LL INF = 1LL<<61;

using namespace std;

//vector > G;
//typedef pair P;
//vector > ::iterator iter;
//
//mapmp;
//map::iterator p;

const int N = 20000 + 5;

typedef struct Node {
	int l,r;
	int a;
};

Node tree[N * 4];

int le[N * 2],ri[N * 2];

int vis[N * 2];

int ans;

typedef struct Line {
	int x;//區間端點
	int num;//編號
};

Line line[N * 2];//離散化

void init() {
	memset(vis,0,sizeof(vis));
	ans = 0;
}

bool cmp(Line x,Line y) {
	return x.x < y.x;
}

void build(int l,int r,int id) {
	tree[id].l = l;
	tree[id].r = r;
	tree[id].a = 0;
	if(l == r)return ;
	int mid = (l + r)/2;
	build(l,mid,id<<1);
	build(mid+1,r,id<<1|1);
}

void push_down(int id) {
	if(tree[id].a > 0) {
		tree[id<<1].a = tree[id].a;
		tree[id<<1|1].a = tree[id].a;
		tree[id].a = 0;
	}
}

void update(int l,int r,int id,int w) {
	if(l <= tree[id].l && r >= tree[id].r) {
		tree[id].a = w;return;
	}
	push_down(id);
	int mid = (tree[id].l + tree[id].r)/2;
	if(r <= mid)update(l,r,id<<1,w);
	else if(l > mid)update(l,r,id<<1|1,w);
	else {
		update(l,mid,id<<1,w);
		update(mid+1,r,id<<1|1,w);
	}
}

void query(int id) {
	if(tree[id].a > 0) {
		if(vis[tree[id].a] == 0) {
			ans++;
			vis[tree[id].a] = 1;
		}
		return;
	}
	query(id<<1);
	query(id<<1|1);
}

int main() {
	int t;
	scanf(%d,&t);
	while(t--) {
		init();
		int n;
		scanf(%d,&n);
		for(int i=0;i