社区讨论
大佬求调!线段树只AC前仨点,后面全TLE??
P2572[SCOI2010] 序列操作参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lxeq7655
- 此快照首次捕获于
- 2024/06/14 21:29 2 年前
- 此快照最后确认于
- 2024/06/15 09:34 2 年前
CPP
#include <bits/stdc++.h>
using namespace std;
int n,m;
struct Node {
int lazy; // -1: 乱的 0:全是0 1: 全是1
int l,r,sum; // sum: 1的个数
int ls1,rs1,s1; // ls1: 左边连续1的个数 s1: 连续1的个数
int is_leaf;
}t[400010];
int a[100010];
void pushup (int i)
{
if (t[i].is_leaf) return ;
if (t[i<<1].lazy==t[i<<1|1].lazy) t[i].lazy=t[i<<1].lazy;
else t[i].lazy=-1;
t[i].sum=t[i<<1].sum+t[i<<1|1].sum;
if (t[i<<1].lazy==1) t[i].ls1=t[i<<1].r-t[i<<1].l+1+t[i<<1|1].ls1;
else t[i].ls1=t[i<<1].ls1;
if (t[i<<1|1].lazy==1) t[i].rs1=t[i<<1|1].r-t[i<<1|1].l+1+t[i<<1].rs1;
else t[i].rs1=t[i<<1|1].rs1;
t[i].s1=max(max(t[i<<1].s1,t[i<<1|1].s1),t[i<<1].rs1+t[i<<1|1].ls1);
}
void pushdown (int i)
{
if (t[i].lazy==1) {
t[i<<1].lazy=t[i<<1|1].lazy=1;
t[i<<1].sum=t[i<<1].ls1=t[i<<1].rs1=t[i<<1].s1=t[i<<1].r-t[i<<1].l+1;
t[i<<1|1].sum=t[i<<1|1].ls1=t[i<<1|1].rs1=t[i<<1|1].s1=t[i<<1|1].r-t[i<<1|1].l+1;
}
if (t[i].lazy==0) {
t[i<<1].lazy=t[i<<1|1].lazy=0;
t[i<<1].sum=t[i<<1].ls1=t[i<<1].rs1=0;
t[i<<1|1].sum=t[i<<1|1].ls1=t[i<<1|1].rs1=t[i<<1|1].s1=0;
}
}
void build (int i,int l,int r)
{
t[i].l=l; t[i].r=r;
if (l==r) {
t[i].lazy=t[i].ls1=t[i].rs1=t[i].s1=t[i].sum=(a[l]==1);
t[i].is_leaf=1;
return ;
}
int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
pushup(i);
return ;
}
void change (int i,int l,int r,int L,int R,int opt)
{
if (L<=l && r<=R) {
t[i].lazy=opt;
if (opt==1) t[i].ls1=t[i].rs1=t[i].s1=t[i].sum=r-l+1;
else t[i].ls1=t[i].rs1=t[i].s1=t[i].sum=0;
pushdown(i);
return ;
}
pushdown(i);
int mid=(l+r)>>1;
if (mid>=L) change(i<<1,l,mid,L,R,opt);
if (mid<R) change(i<<1|1,mid+1,r,L,R,opt);
pushup(i);
return ;
}
void Negate (int i,int l,int r,int L,int R)
{
if (L<=l && r<=R && t[i].lazy!=-1) {
t[i].lazy^=1;
if (t[i].lazy==1) t[i].ls1=t[i].rs1=t[i].s1=t[i].sum=r-l+1;
else t[i].ls1=t[i].rs1=t[i].s1=t[i].sum=0;
pushdown(i);
return ;
}
pushdown(i);
int mid=(l+r)>>1;
if (mid>=L) Negate(i<<1,l,mid,L,R);
if (mid<R) Negate(i<<1|1,mid+1,r,L,R);
pushup(i);
return ;
}
int ask_sum (int i,int l,int r,int L,int R)
{
if (L<=l && r<=R) return t[i].sum;
pushdown(i);
int mid=(l+r)>>1,ans=0;
if (mid>=L) ans+=ask_sum(i<<1,l,mid,L,R);
if (mid<R) ans+=ask_sum(i<<1|1,mid+1,r,L,R);
pushup(i);
return ans;
}
int ask_con (int i,int l,int r,int L,int R)
{
if (L<=l && r<=R) return t[i].s1;
pushdown(i);
int mid=(l+r)>>1,ans=0;
if (mid>=L) ans=max(ans,ask_con(i<<1,l,mid,L,R));
if (mid<R) ans=max(ans,ask_con(i<<1|1,mid+1,r,L,R));
if (mid>=L && mid<R) ans=max(ans,min(t[i<<1].rs1,mid-L+1)+min(t[i<<1|1].ls1,R-mid));
pushup(i);
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n>>m;
for (int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
// for (int i=1;i<=n*2;i++) {
// cout<<t[i].lazy<<" "<<t[i].sum<<" "<<t[i].s1<<" "<<t[i].ls1<<" "<<t[i].rs1<<endl;
// }
// cout<<endl;
while (m--) {
int opt,l,r;
cin>>opt>>l>>r;
l++; r++;
if (opt<=1) change(1,1,n,l,r,opt);
if (opt==2) Negate(1,1,n,l,r);
if (opt==3) cout<<ask_sum(1,1,n,l,r)<<endl;
if (opt==4) cout<<ask_con(1,1,n,l,r)<<endl;
// for (int i=1;i<=n*2;i++) {
// cout<<t[i].lazy<<" "<<t[i].sum<<" "<<t[i].s1<<" "<<t[i].ls1<<" "<<t[i].rs1<<endl;
// }
// cout<<endl;
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...