萌新珂朵莉树求条qwq
查看原帖
萌新珂朵莉树求条qwq
764676
ycr_sad楼主2024/8/18 16:05

qwq WA了

#include<iostream>
#include<set>
using namespace std;
struct intt
{
	int l,r;
	mutable bool work;
	bool operator < (const intt b) const
	{
		return l<b.l;
	}
	intt(int L,int R=0,bool Work=0)
	{
		l=L;
		r=R;
		work=Work;
	}
};
set<intt> kdl;
int n,q;
auto split(int pos)
{
	auto it=kdl.lower_bound(intt(pos));
	if(it->l==pos)
	  return it;
	it--;
	int L=it->l,R=it->r;
	bool WORK=it->work;
	kdl.insert(intt(L,pos-1,WORK));
	return kdl.insert(intt(pos,R,WORK)).first;
}
void assign(int l,int r,bool b)
{
	auto itr=split(r+1),itl=split(l);
	kdl.erase(itl,itr);
	kdl.insert(intt(l,r,b));
}
int answer()
{
	int sum=0;
	for(auto it=kdl.begin();it!=kdl.end();it++)
	{
	    sum+=(it->r-it->l+1)*it->work;
//	    cout<<it->l<<" "<<it->r<<" "<<it->work<<"\n";
	}
	return sum;
}
int main()
{
	cin>>n>>q;
	kdl.insert(intt(1,n,1));
	kdl.insert(intt(n+1,n+1,0));
	for(int i=1;i<=q;i++)
	{
		int op,l,r;
		cin>>l>>r>>op;
		assign(l,r,op-1);
		cout<<answer()<<"\n";
	}
}
2024/8/18 16:05
加载中...