大家好，又见面了，我是你们的朋友全栈君。
需要满足题目是随机数据，否则会被卡
P2572 [SCOI2010]序列操作
题意：
使用数据结构完成下列操作： 1.区间赋值为0 2.区间赋值为1 3.区间求和 4.区间取反 5.区间最大连续1数量
code：
因为不是随机数据，所以ODT会超时，只是记录一下模板。
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
const int maxm=1e5 5;
#define type bool
#define It set<Node>::iterator
struct Node{
int l,r;
mutable type x;
Node(int a,int b=0,type c=0){
l=a,r=b,x=c;
}
bool operator<(const Node& a)const {
return l<a.l;
}
};
set<Node>s;
int n,m;
It split(int pos){
auto it=s.lower_bound(Node(pos));//不能用upper_bound,因为要找最左边的一个
if(it!=s.end()&&it->l==pos){
return it;
}
it--;
int l=it->l,r=it->r;
type x=it->x;
s.erase(it);
s.insert(Node(l,pos-1,x));
return s.insert(Node(pos,r,x)).first;
}
void assign(int l,int r,type val){
//区间赋值
auto it2=split(r 1),it1=split(l);//要先找r,再找l
s.erase(it1,it2);
s.insert(Node(l,r,val));
}
void rev(int l,int r){
//区间取反
It it2=split(r 1),it1=split(l);
for(;it1!=it2;it1 ){
it1->x^=1;
}
}
int sum(int l,int r){
//区间求和
int ans=0;
It it2=split(r 1),it1=split(l);
for(;it1!=it2;it1 ){
if(it1->x){
ans =it1->r-it1->l 1;
}
}
return ans;
}
int cal(int l,int r){
//区间最大连续1数量
int ans=0;
int len=0;
It it2=split(r 1),it1=split(l);
for(;it1!=it2;it1 ){
if(it1->x){
len =it1->r-it1->l 1;
}else{
ans=max(ans,len);
len=0;
}
}
if(len){
ans=max(ans,len);
}
return ans;
}
signed main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i ){
int x;scanf("%d",&x);
s.insert(Node(i,i,x));
}
s.insert(Node(n,n,0));
while(m--){
int op,l,r;scanf("%d%d%d",&op,&l,&r);
if(op==0){
//[l,r]修改为0
assign(l,r,0);
}else if(op==1){
//[l,r]修改为1
assign(l,r,1);
}else if(op==2){
//[l,r]取反
rev(l,r);
}else if(op==3){
//[l,r]的和
int ans=sum(l,r);
printf("%dn",ans);
}else if(op==4){
//[l,r]最大连续1数量
int ans=cal(l,r);
printf("%dn",ans);
}
}
return 0;
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
