社区讨论

新人妹子刚学OI,求解珂朵莉树0.0

P2572[SCOI2010] 序列操作参与者 4已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@mi7vzvjv
此快照首次捕获于
2025/11/21 04:31
4 个月前
此快照最后确认于
2025/11/21 04:31
4 个月前
查看原帖
以为拿ODT很容易过啊orz
判断连续一那个函数改用题解里的还是全WA。。。用了讨论版里的数据生成器对拍好长时间都么得结果QAQ
我跪了,有没有大爷救救孩子orz
CPP
#include<bits/stdc++.h>
#include<set>
#define IT set<node>::iterator
using namespace std;
int n,m;
struct node{
	int ll,rr;
	mutable int val;
	node(int l,int r=-1,int v=0):ll(l),rr(r),val(v) {} 
	bool operator < (const node &orz)const{
		return ll<orz.ll;
	} 
}; 
set<node> s;
IT split(int pos){
	IT it=s.lower_bound(node(pos));
	if(it!=s.end() && it->ll==pos) return it;
	--it;
	int ll=it->ll,rr=it->rr,val=it->val;
	s.erase(it);
	s.insert(node(ll,pos-1,val));
	return s.insert(node(pos,rr,val)).first;
}
void assign(int ll,int rr,int val){
    IT itr=split(rr+1),itl=split(ll);
    s.erase(itl,itr);
    s.insert(node(ll,rr,val));
} 
int qsum(int ll,int rr){
    int res=0;
    IT itr=split(rr+1),itl=split(ll);
    for(;itl!=itr;++itl) res+=(itl->rr-itl->ll+1)*itl->val;
    return res;
}
void rev(int ll,int rr)
{
    IT itr=split(rr+1),itl=split(ll);
    for(;itl!=itr; ++itl)
        (itl->val) ^= 1;
} 
int  cnt(int ll,int rr){
	IT itr=split(rr+1),itl=split(ll);
	int t,ans=0;
    for(;itl!=itr; ++itl){
    	if(itl->val==false){
			ans=max(ans,t);	
			t=0;
		}
		else {
			t+=(itl->rr-itl->ll+1);
		}
	}
	return max(ans,t);
} 
int main(){
	//freopen("data.txt","r",stdin);
	//freopen("my.txt","w",stdout);
	cin>>n>>m;
	int v;
	for(int i=0;i<n;i++){
		scanf("%d",&v);
		s.insert(node(i,i,v));
	}
	s.insert(node(n,n,0));
	while(m--){
		int opt,a,b;
		scanf("%d %d %d",&opt,&a,&b);
		if(opt==0){
			assign(a,b,0);
		}
		if(opt==1){
			assign(a,b,1);
		}
		if(opt==2){
			rev(a,b);
		} 
		if(opt==3){
			cout<<qsum(a,b)<<endl;
		}
		if(opt==4){
			cout<<cnt(a,b)<<endl;
		}
	}
	
	return 0;
}

回复

5 条回复,欢迎继续交流。

正在加载回复...