luoguT21778 过年

差分一下上线段树
#include <iostream>

#include <cstdio>

#include <vector>

using namespace std;

int n, m, uu, vv, ww;

vector<int> d[100005];

struct SGT{

	int cnt[400005], pos[400005];

	void pushUp(int o){

		int lson=o<<1;

		int rson=lson|1;

		if(cnt[lson]>=cnt[rson]){

			cnt[o] = cnt[lson];

			pos[o] = pos[lson];

		}

		else{

			cnt[o] = cnt[rson];

			pos[o] = pos[rson];

		}

	}

	void update(int o, int l, int r, int x, int k){

		if(l==r){

			cnt[o] += k;

			pos[o] = l;

		}

		else{

			int mid=(l+r)>>1;

			int lson=o<<1;

			int rson=lson|1;

			if(x<=mid)	update(lson, l, mid, x, k);

			if(mid<x)	update(rson, mid+1, r, x, k);

			pushUp(o);

		}

	}

}sgt;

int main(){

	cin>>n>>m;

	for(int i=1; i<=m; i++){

		scanf("%d %d %d", &uu, &vv, &ww);

		d[uu].push_back(ww);

		d[vv+1].push_back(-ww);

	}

	for(int i=1; i<=n; i++){

		for(int j=0; j<d[i].size(); j++)

			if(d[i][j]>0)	sgt.update(1, 1, 100000, d[i][j], 1);

			else	sgt.update(1, 1, 100000, -d[i][j], -1);

		if(sgt.cnt[1])	printf("%d\n", sgt.pos[1]);

		else	printf("-1\n");

	}

	return 0;

}
巴特西

luoguT21778 过年

最新文章

热门文章
