ODT死循环求助
查看原帖
ODT死循环求助
661595
a2lyaXNhbWUgbWFyaXNh楼主2022/10/19 14:52
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define inf 0x7ffffff
#define IT set<node>::iterator
#define int long long
typedef long long TYPE;
struct node{
	unsigned int l,r;
	mutable TYPE v;
	node(unsigned int left,unsigned int right=0,TYPE value=0);
};
bool operator<(node a,node b){
	return a.l<b.l;
}
node::node(unsigned int left,unsigned int right,TYPE value){
	l=left;
	r=right;
	v=value;
}
int sum,n,q;
set<node>odt; 
inline IT split(unsigned int p){
	IT it=odt.lower_bound(node(p));
	if(it!=odt.end()&&it->l==p)
		return it;
	--it;
	unsigned r=it->r,l=it->l;
	TYPE v=it->v;
	odt.erase(it);
	odt.insert(node(l,p-1,v));
	return odt.insert(node(p,r,v)).first;	
}
inline void assign(int l, int r, int v) {
	int cnt=0;
	IT itr=split(r+1),itl=split(l);
	for(IT it=itl;it!=itr;++it)
		if(it->v!=v)
			cnt+=it->r-it->l+1;
	sum+=(v==1?-cnt:cnt);
	odt.erase(itl, itr);
	odt.insert(node(l, r, v));
}
namespace IO{
	char ibuf[(1<<20)+1],*iS,*iT;
	#if ONLINE_JUDGE
		#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
 	#else
		#define gh() getchar()
	#endif
	inline long long read(){
		reg char ch=gh();
		reg long long x=0;
		reg char t=0;
		while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
		while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=gh();
		return t?-x:x;
	}
	inline void write(long long x) {
		if(x<0)
			putchar('-'), x = -x;
		if(x>9)
			write(x/10);
		putchar(x%10+'0');
	}
	inline void writeln(long long x){
		write(x);
		putchar('\n');
	}
}using namespace IO;

signed main(){
	n=read();
	q=read();
	sum=n;
	odt.insert(node(1,n,2));
	odt.insert(node(n+1,n+1,-1));
	for(reg int i=1;i<=q;++i){
		int v,l,r;
		v=read(),l=read(),r=read();
		assign(l,r,v);
		writeln(sum);
	}
	return 0;
}
2022/10/19 14:52
加载中...