[BZOJ] [P1858] [Scoi 2010] [서열 조작] [문제 풀이] [선분 수]
4510 단어 bzoj
코드 능력 을 단련 하 는 선분 수 누 드 문제
Code:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cctype>
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define L i<<1
#define R i<<1|1
using namespace std;
const int maxn=1e5+5;
int a[maxn];
int n,m;
int getint(){
int res=0;char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))res=res*10+c-'0',c=getchar();
return res;
}
struct tup{
int x,y,z;
tup(int _x=0,int _y=0,int _z=0):x(_x),y(_y),z(_z){}
};
int max5(int a,int b,int c,int d,int e){return max(e,max(max(a,b),max(c,d)));}
struct seg_tree{
struct node{
int lazy,rev,sum0,sum1,ls1,ss1,rs1,ls0,rs0,ss0;
node(){
lazy=-1,rev=0,sum0=0,sum1=0,ls1=0,ss1=0,rs1=0,ls0=0,rs0=0,ss0=0;
}
}t[maxn<<2];
void build(int i,int l,int r){
if(l==r){
t[i].sum0=t[i].ls0=t[i].ss0=t[i].rs0=a[l]==0;
t[i].sum1=t[i].ls1=t[i].ss1=t[i].rs1=a[l]==1;
return;
}int mid=(l+r)>>1;
build(lson);build(rson);
rz(i,l,r);
}
void rz(int i,int l,int r){
int mid=(l+r)>>1;
tup l0,r0,ans;
t[i].sum0=t[L].sum0+t[R].sum0;
t[i].sum1=t[L].sum1+t[R].sum1;
t[i].ls0=t[L].ls0;
t[i].rs0=t[R].rs0;
t[i].ls1=t[L].ls1;
t[i].rs1=t[R].rs1;
if(t[L].ls0==(mid-l+1))t[i].ls0=t[L].ls0+t[R].ls0;
if(t[L].ls1==(mid-l+1))t[i].ls1=t[L].ls1+t[R].ls1;
if(t[R].rs0==(r-mid))t[i].rs0=t[R].rs0+t[L].rs0;
if(t[R].rs1==(r-mid))t[i].rs1=t[R].rs1+t[L].rs1;
t[i].ss0=max5(t[L].ss0,t[R].ss0,t[i].ls0,t[i].rs0,t[L].rs0+t[R].ls0);
t[i].ss1=max5(t[L].ss1,t[R].ss1,t[i].ls1,t[i].rs1,t[L].rs1+t[R].ls1);
}
void pushdown(int i,int l,int r){
int mid=(l+r)>>1;
if(t[i].rev){
swap(t[L].sum0,t[L].sum1);swap(t[L].ls1,t[L].ls0);
swap(t[L].ss1,t[L].ss0);swap(t[L].rs1,t[L].rs0);
swap(t[R].sum0,t[R].sum1);swap(t[R].ls1,t[R].ls0);
swap(t[R].ss1,t[R].ss0);swap(t[R].rs1,t[R].rs0);
t[L].rev^=1;t[R].rev^=1;
if(~t[L].lazy)t[L].lazy^=1;
if(~t[R].lazy)t[R].lazy^=1;
t[i].rev=0;
}
if(t[i].lazy!=-1){
t[L].lazy=t[i].lazy;
t[L].sum0=(mid-l+1)*(t[i].lazy==0);
t[L].sum1=(mid-l+1)*(t[i].lazy==1);
t[L].ls0=t[L].ss0=t[L].rs0=(mid-l+1)*(t[i].lazy==0);
t[L].ls1=t[L].ss1=t[L].rs1=(mid-l+1)*(t[i].lazy==1);
t[R].lazy=t[i].lazy;
t[R].sum0=(r-mid)*(t[i].lazy==0);
t[R].sum1=(r-mid)*(t[i].lazy==1);
t[R].ls0=t[R].ss0=t[R].rs0=(r-mid)*(t[i].lazy==0);
t[R].ls1=t[R].ss1=t[R].rs1=(r-mid)*(t[i].lazy==1);
t[i].lazy=-1;
}
}
void Change(int i,int l,int r,int l0,int r0,int col){
if(l0<=l&&r0>=r){
t[i].lazy=col;
t[i].sum0=(r-l+1)*(t[i].lazy==0);
t[i].sum1=(r-l+1)*(t[i].lazy==1);
t[i].ls0=t[i].ss0=t[i].rs0=(r-l+1)*(t[i].lazy==0);
t[i].ls1=t[i].ss1=t[i].rs1=(r-l+1)*(t[i].lazy==1);
return;
}pushdown(i,l,r);
int mid=(l+r)>>1;
if(l0<=mid)Change(lson,l0,r0,col);
if(r0>mid)Change(rson,l0,r0,col);
rz(i,l,r);
}
void Rev(int i,int l,int r,int l0,int r0){
if(l0<=l&&r0>=r){
t[i].rev^=1;
if(~t[i].lazy)t[i].lazy^=1;
swap(t[i].sum0,t[i].sum1);swap(t[i].ls1,t[i].ls0);
swap(t[i].ss1,t[i].ss0);swap(t[i].rs1,t[i].rs0);
return;
}pushdown(i,l,r);
int mid=(l+r)>>1;
if(l0<=mid)Rev(lson,l0,r0);
if(r0>mid)Rev(rson,l0,r0);
rz(i,l,r);
}
int One(int i,int l,int r,int l0,int r0){
if(l0<=l&&r0>=r)
return t[i].sum1;
pushdown(i,l,r);
int mid=(l+r)>>1,ans=0;
if(l0<=mid)ans+=One(lson,l0,r0);
if(r0>mid)ans+=One(rson,l0,r0);
return ans;
}
tup Sone(int i,int l,int r,int l0,int r0){
if(l0<=l&&r0>=r)
return tup(t[i].ls1,t[i].ss1,t[i].rs1);
pushdown(i,l,r);
int mid=(l+r)>>1;tup ans,lef,rig;
if(l0<=mid)lef=Sone(lson,l0,r0);
if(r0>mid)rig=Sone(rson,l0,r0);
if(l0>mid)return rig;
if(r0<=mid)return lef;
ans.x=lef.x;ans.z=rig.z;
if(lef.x==mid-l+1)ans.x=lef.x+rig.x;
if(rig.z==r-mid)ans.z=rig.z+lef.z;
ans.y=max5(lef.y,rig.y,ans.x,ans.y,lef.z+rig.x);
return ans;
}
}T;
int main(){
n=getint(),m=getint();
for(int i=1;i<=n;i++)a[i]=getint();
T.build(1,1,n);
while(m--){
int op=getint(),l=getint()+1,r=getint()+1;
if(op==0){T.Change(1,1,n,l,r,0);}
if(op==1){T.Change(1,1,n,l,r,1);}
if(op==2){T.Rev(1,1,n,l,r);}
if(op==3){printf("%d
",T.One(1,1,n,l,r));}
if(op==4){printf("%d
",T.Sone(1,1,n,l,r).y);}
}return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
bzoj1010 장난감 포장 [결정 단조성 최적화 dp]하나의 모범 문제라고 할 수 있다.우리는 먼저 소박한 dp방정식을 얻을 수 있다. f[i]=min(f[j]+w(j,i)),j∈[0,i). w(j,i)는 j+1~i를 포장하여 운송하는 비용의 시간 복잡도는 O(n2)라...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.