ABC216G

标签：return int ABC216G ll long define

将区间按照右端点排序，贪心的往最右边填 \(1\)，不难发现这样一定是正确的。感性理解一下就是越往右的位置对于后面的区间贡献越大。

而且每个点最多只会被放置一个 \(1\)，所以我们可以暴力的找到下一个可以填的位置，并填入 \(1\)，可以使用线段树维护，复杂度是 \(\mathcal{O}(n \log n)\) 的。

#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define pb(x) push_back(x)
#define lowbit(x) x&-x
using namespace std;
const int N=2e5+10;
struct node{
	int l,r,w;
}a[N];
ll ans;
int n,m,T,sum[N<<2],tl[N<<2],tr[N<<2];
inline int read(){
	int s=0,f=0;
	char ch=getchar();
	while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
	while(ch<='9'&&ch>='0') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return f?-s:s;
}
inline void pushup(int i){
	sum[i]=sum[i<<1]+sum[i<<1|1];
}
inline void build(int i,int l,int r){
	tl[i]=l,tr[i]=r;
	if(l<r){
		int mid=(l+r)>>1;
		build(i<<1,l,mid);
		build(i<<1|1,mid+1,r);
	}
}
inline void modify(int i,int k){
	if(tl[i]==tr[i]){
		sum[i]=1;
		return ;
	}
	int mid=(tl[i]+tr[i])>>1;
	if(k<=mid) modify(i<<1,k);
	else modify(i<<1|1,k);
	pushup(i);
}
inline int query(int i,int l,int r){
	if(tl[i]==l&&tr[i]==r) return sum[i];
	int mid=(tl[i]+tr[i])>>1;
	if(r<=mid) return query(i<<1,l,r);
	else if(l>mid) return query(i<<1|1,l,r);
	else return query(i<<1,l,mid)+query(i<<1|1,mid+1,r);
}
inline int fnd(int i,int l,int r){
	int mid=(tl[i]+tr[i])>>1;
	if(tl[i]==l&&tr[i]==r){
//		cout<<i<<" "<<l<<" "<<r<<" "<<sum[i<<1]<<" "<<sum[i<<1|1]<<endl;
		if(tl[i]==tr[i]) return (!sum[i]?l:-1);
		if(sum[i<<1|1]!=r-mid) return fnd(i<<1|1,mid+1,r);
		else if(sum[i<<1]!=mid-l+1) return fnd(i<<1,l,mid);
		else return -1;
	}else{
		if(r<=mid) return fnd(i<<1,l,r);
		else if(l>mid) return fnd(i<<1|1,l,r);
		else{
//			cout<<i<<" "<<tl[i]<<" "<<tr[i]<<"->"<<mid+1<<" "<<tr[i]<<endl;
			int s=fnd(i<<1|1,mid+1,r);
			if(s!=-1) return s;
			return fnd(i<<1,l,mid);
		}
	}
}
int main(){
	n=read(),m=read();
	for(register int i=1;i<=m;++i) a[i]=(node){read(),read(),read()};
	sort(a+1,a+m+1,[](node a,node b){return a.r==b.r?a.l<b.l:a.r<b.r;});
	build(1,1,n);
	for(register int i=1;i<=m;++i){
		int s=query(1,a[i].l,a[i].r);
		for(register int j=1;j<=a[i].w-s;++j){
			int k=fnd(1,a[i].l,a[i].r);
//			cout<<k<<endl;
			modify(1,k);
		}
	}
	for(register int i=1;i<=n;++i) printf("%d ",query(1,i,i));
	return 0;
}

标签：return,int,ABC216G,ll,long,define
From： https://www.cnblogs.com/Nasturity/p/17306637.html