关于珂树
查看原帖
关于珂树
798144
SukiYuri楼主2024/11/28 17:49

TLE 30 求优化

还是说这题不能用


#include <bits/stdc++.h>

using namespace std;

struct node {
	int l,r;
	mutable bool v;
	bool operator <(const node o) const {return l<o.l;}
};

set<node> s;
typedef set<node>::iterator it;
inline it spt(int x) {
	it res=--s.upper_bound(node{x,0,0});
	if(res->l==x) return res;
	node tmp=*res;
	s.erase(res);
	s.insert(node{tmp.l,x-1,tmp.v});
	return s.insert(node{x,tmp.r,tmp.v}).first;
}
#define get it R=spt(r+1),L=spt(l);
#define spfor for(it i=L;i!=R;++i)
inline void mrg(int l,int r,int val) {
	get; s.erase(L,R);
	s.insert(node{l,r,val});
}
inline void mod(int l,int r) {
	get; spfor i->v=!i->v;
}
inline int ask1(int l,int r) {
	int res=0;
	get; spfor
		if(i->v) res+=i->r-i->l+1;
	return res;
} 
inline int ask2(int l,int r) {
	int res=0,now=0;
	get; spfor
		if(i->v) now+=i->r-i->l+1;
		else res=max(res,now),now=0;
	return max(res,now);
}
int main() {
//	freopen("out.txt","w",stdout);
	ios::sync_with_stdio(0);
	int n,m; cin>>n>>m;
	int L=0,R=0,pre; cin>>pre;
	for(int i=1;i<n;++i) {
		int now; cin>>now;
		if(now!=pre) {
			s.insert(node{L,R,pre});
			L=++R=i;
			pre=now;
		} else R=i;
	}
	s.insert(node{L,R,pre});
	while(m--) {
//		cout<<m<<"-----x-----\n";
//		for(node i:s) cout<<i.l<<' '<<i.r<<' '<<i.v<<'\n';
		int op,l,r;
		cin>>op>>l>>r;
		if(op==0) mrg(l,r,0);
		if(op==1) mrg(l,r,1);
		if(op==2) mod(l,r);
		if(op==3) cout<<ask1(l,r)<<'\n';
		if(op==4) cout<<ask2(l,r)<<'\n';
	}
	return 0;
}
2024/11/28 17:49
加载中...