Lflame

【bzoj1500】 维修数列 SMT

    用SMT试了试,TLE了,用时大概是Splay的好几倍....

    也不知道XMJ怎么过的...

     

    2016/1/14 update    听朴心哥讲了一些优化,然后便将long long改成int,于是就AC了 !

 

#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<ctime>
#include<algorithm>
#ifdef WIN32
#define my_LL "%d"
#else
#define my_LL "%d"
#endif
using namespace std;
typedef int ll ;
const int INF=(1<<30) ;

int n,m ;
int zj,hzj;
int now_i ;

int read(int &x)
{
bool f=0 ; char t=getchar() ; x=0;
while(t<'0'||t>'9'){
  f=0 ;
  if(t=='-') f=1;
  if(t==EOF) return EOF ;
  t=getchar() ;
 }
while(t>='0'&&t<='9'){
  x=(x<<1)+(x<<3)+t-'0' ;
  t=getchar() ;
 }
if(f) x=-x;
return 0;
}

char get_c()
{
char t;
while((t=getchar())!=EOF){
  if(!isspace(t))
   break ;
 }
return t;
}

struct node;
typedef node* tree;
struct node
{
tree lc,rc;
bool rev , mdf_lazy ;
int key ;
int val,size,lazy;
ll sum , m_sum , l_sum , r_sum;
void pushdown() ;
void update() ;
}nd[800005];
tree root,null ;

void node::update()
{
if(this==null) return ;
sum=lc->sum + rc->sum + val;
size=lc->size + rc->size + 1;
m_sum = max(max(lc->m_sum,rc->m_sum),(ll)val) ;
if(lc->r_sum >= 0) m_sum=max(m_sum,lc->r_sum+val+(rc->l_sum>0?rc->l_sum:0)) ;
if(rc->l_sum >= 0) m_sum=max(m_sum,rc->l_sum+val+(lc->r_sum>0?lc->r_sum:0)) ;
l_sum=lc->l_sum , r_sum=rc->r_sum ;
l_sum=max(lc->sum+val+(rc->l_sum>0?rc->l_sum:0),l_sum) ;
r_sum=max(rc->sum+val+(lc->r_sum>0?lc->r_sum:0),r_sum) ;
}

inline void bj_rev(tree s)
{
if(s==null) return ;
s->rev ^= 1 ;
swap(s->lc,s->rc) ;
swap(s->l_sum,s->r_sum) ;
}

inline void bj_mdf(tree s,int t)
{
if(s==null) return ;
s->mdf_lazy=true ;
s->lazy=t;
s->sum = (ll)t*s->size , s->val=t ;
s->m_sum = s->r_sum = s->l_sum = t>0?s->sum:t ;
}

void node::pushdown()  // ´òÁËlazy±ê¼ÇµÄµãÒѾ­´¦Àí
{
if(this==null) return ;
if(rev){   // ÓÅÃÀµÄд·¨ !!!
  bj_rev(lc) ;
  bj_rev(rc) ;
  rev=false ;
 }
if(mdf_lazy){
  bj_mdf(lc,lazy) ;
  bj_mdf(rc,lazy) ;
  mdf_lazy=false ;
 }
}

struct cuts
{
tree x,y ;
cuts(tree _x=null,tree _y=null){
  x=_x , y=_y ;
 }
};

tree tra[800005] ;
int ndnum , tnum ;

inline void ini(const tree &t)
{
t->key=(unsigned)rand()*rand()%INF ;
t->lc=t->rc=null ; 
t->mdf_lazy = t->rev = false ;
t->val=t->sum=t->m_sum=t->l_sum=t->r_sum=0 ;
}

inline void ini(const tree &t,const int &val)
{
t->val=t->sum=val ; t->size=1; 
t->l_sum=t->r_sum=t->m_sum=val ;
}

inline tree news()
{
if(tnum){
  tree ret=tra[tnum] ; // ×¢Òâ´Ë´¦²»ÄܼÓÒýÓà!!!
  tnum -- ;
  if(ret->lc != null) tra[++tnum]=ret->lc ;
  if(ret->rc != null) tra[++tnum]=ret->rc ;
  ini(ret) ;
  return ret;
 }
 ++ ndnum ;
ini(&nd[ndnum]) ;
return &nd[ndnum] ;
}

cuts splits(tree s,int t)
{
if(t==0) return cuts(null,s) ;
if(s==null) return cuts(null,null) ;
s->pushdown() ;
if(t<=s->lc->size){
  cuts tmp=splits(s->lc,t) ;
  s->lc=tmp.y ; s->update() ;
  return cuts(tmp.x,s) ;
 }
else{
  cuts tmp=splits(s->rc,t - s->lc->size - 1) ;
  s->rc=tmp.x ; s->update() ;
  return cuts(s,tmp.y) ;
 }
}

tree merges(cuts s)
{
if(s.x==null) return s.y;
if(s.y==null) return s.x;
s.y->pushdown() ; s.x->pushdown() ;
if(s.x->key < s.y->key){
  tree tmp=merges(cuts(s.x->rc,s.y)) ;
  s.x->rc=tmp ; s.x->update() ;
  return s.x;
 }
else{
  tree tmp=merges(cuts(s.x,s.y->lc)) ;
  s.y->lc=tmp ; s.y->update() ;
  return s.y;
 }
}

void my_ins()
{
tree tmp=null ;
int pos , tot ;
read(pos) ; read(tot) ;
zj += tot ;
hzj = max(zj,hzj) ;
for(int i=1;i<=tot;++i){
  int a; read(a) ;
  tree t=news() ; ini(t,a) ; 
  tmp = merges(cuts(tmp,t)) ;
 }
if(pos>root->size) pos=root->size ;
cuts ttt=splits(root,pos) ;
tmp=merges(cuts(ttt.x,tmp)) ;
root=merges(cuts(tmp,ttt.y)) ;
}

void my_del(){
int pos , tot ;
read(pos) ; read(tot) ;
zj -= tot ;
cuts tmp1=splits(root,pos-1) ;
cuts tmp2=splits(tmp1.y,tot) ;
tra[++tnum]=tmp2.x ;
root=merges(cuts(tmp1.x,tmp2.y)) ;  
}

void my_rev()
{
int pos,tot ;
read(pos) ; read(tot) ;
cuts tmp1=splits(root,pos-1) ;
cuts tmp2=splits(tmp1.y,tot) ;
bj_rev(tmp2.x) ;
tree tmp=merges(tmp2) ;
root=merges(cuts(tmp1.x,tmp)) ;
}

void my_sum()
{
int pos,tot ;
read(pos) ; read(tot) ;
cuts tmp1=splits(root,pos-1) ;
cuts tmp2=splits(tmp1.y,tot) ;
printf(my_LL"\n",tmp2.x->sum) ;
tree tmp=merges(tmp2) ;
root=merges(cuts(tmp1.x,tmp)) ;
}

void my_mdf()
{
int pos,tot,c ;
read(pos) ; read(tot) ; read(c) ;
cuts tmp1=splits(root,pos-1) ;
cuts tmp2=splits(tmp1.y,tot) ;
bj_mdf(tmp2.x,c) ;
tree tmp=merges(tmp2) ;
root=merges(cuts(tmp1.x,tmp)) ;
}

inline void clr(const int &num)
{
for(int i=1;i<=num;++i){
  get_c() ;
 }
}

int main()
{
null=&nd[++ndnum] ; null->lc=null->rc=null ; 
null->sum=null->val=null->size=0 ;
null->l_sum=null->r_sum=null->m_sum=-INF;
root=null ;
srand(990306) ;
read(n) ; read(m) ;
zj=n ;
for(int i=1;i<=n;++i){
  int a;
  read(a) ;
  tree t ; t=news() ; 
  ini(t,a) ;
  root=merges(cuts(root,t)) ;
 }
for(int i=1;i<=m;++i){
  now_i=i+2 ;
  char t=get_c() ;
  if(t=='I'){
   my_ins() ;
  }
  if(t=='D'){
   my_del() ;
  }
  if(t=='R'){
   my_rev() ;
  }
  if(t=='G'){
   my_sum() ;
  }
  if(t=='M'){
   t=get_c() ;
   t=get_c() ;
   if(t=='K'){
    my_mdf() ;
   }
   if(t=='X'){
    clr(4) ;
    printf(my_LL"\n",(root!=null)?root->m_sum:0) ;
   }
  }
 }
return 0;
}

 

评论