【BZOJ】5294:[Bjoi 2018]バイナリ-ダイナミックDP&線分ツリー

転送ゲート:bzoj 5294

問題解

1つのバイナリ数は3の倍数であり、偶数の1つまたは3つ以上の1と2つ以上の0がある場合のみである.
非合法な区間は、1個1または奇数個1&0/1個0の場合である.
線分の木はメンテナンスすればいいので、マークをつけるのはちょっと面倒です.の

コード#コード#

#include
#define lc k<<1
#define rc k<<1|1
#define mem(f) memset((f),0,sizeof((f)))
using namespace std;
const int N=1e5+10;
typedef long long ll;

int n,m,ini[N],pr;

char cp;
inline void rd(int &x)
{
    cp=getchar();x=0;
    for(;!isdigit(cp);cp=getchar());
    for(;isdigit(cp);cp=getchar()) x=(x<<3)+(x<<1)+(cp^48);
}

struct Ag{
    
   struct node{
   	  ll a[4][2][2],b[4][2];
   }t[N<<2],rep;
   
   inline node merge(node l,node r)
   {
   	    node k;int i,j,ii,jj,v,vv;
   	    for(i=0;i<2;++i){
   	    	for(j=0;j<2;++j){
   	    		k.a[0][i][j]=l.a[0][i][j]+r.a[0][i][j]+l.a[2][i][j]+r.a[1][i][j];
   	    	    k.a[1][i][j]=l.a[1][i][j]+l.a[3][i][j];
   	    	    k.a[2][i][j]=r.a[2][i][j]+r.a[3][i][j];
   	    	    k.a[3][i][j]=0LL;
            }
   	    	k.b[0][i]=l.b[0][i]+r.b[0][i]+l.b[2][i]+r.b[1][i];
   	    	k.b[1][i]=l.b[1][i]+l.b[3][i];
   	    	k.b[2][i]=r.b[2][i]+r.b[3][i];
   	    	k.b[3][i]=0LL;
   	    }
   	    for(i=0;i<2;++i)
   	     for(j=0;i+j<2;++j){
   	     	v=i+j;
   	     	for(ii=0;ii<2;++ii)
   	     	 for(jj=0;jj<2;++jj){
   	     	 	 vv=(ii+jj)&1;
   	     	 	 k.a[0][vv][v]+=l.a[2][ii][i]*r.a[1][jj][j];
   	     	     k.a[1][vv][v]+=l.a[3][ii][i]*r.a[1][jj][j];
   	     	     k.a[2][vv][v]+=l.a[2][ii][i]*r.a[3][jj][j];
   	     	     k.a[3][vv][v]+=l.a[3][ii][i]*r.a[3][jj][j];
            }
   	     	k.b[0][v]+=l.b[2][i]*r.b[1][j];
   	     	k.b[1][v]+=l.b[3][i]*r.b[1][j];
   	        k.b[2][v]+=l.b[2][i]*r.b[3][j];
   	     	k.b[3][v]+=l.b[3][i]*r.b[3][j];
   	     }
   	    return k;
   }
   
   void build(int k,int l,int r)
   {
   	   if(l==r) {
           t[k].a[3][ini[l]][ini[l]^1]=1LL;
           t[k].b[3][ini[l]]=1LL;
           return;
       }
   	   int mid=(l+r)>>1;
   	   build(lc,l,mid);build(rc,mid+1,r);
   	   t[k]=merge(t[lc],t[rc]);
   }
   
   void change(int k,int l,int r,int pos)
   {
   	   if(l==r){
   	   	  mem(t[k].a[3]);mem(t[k].b[3]);
          t[k].a[3][ini[l]][ini[l]^1]=1LL;
          t[k].b[3][ini[l]]=1LL;
          return;
       } 
       int mid=(l+r)>>1;
       if(pos<=mid) change(lc,l,mid,pos);
       else change(rc,mid+1,r,pos);
       t[k]=merge(t[lc],t[rc]);
   }
   
   node query(int k,int l,int r,int L,int R)
   {
   	   if(L<=l && r<=R) return t[k];
   	   int mid=(l+r)>>1;
   	   if(R<=mid) return query(lc,l,mid,L,R);
   	   if(L>mid) return query(rc,mid+1,r,L,R);
   	   return merge(query(lc,l,mid,L,R),query(rc,mid+1,r,L,R));
   } 
   
   inline ll gt(int x,int y)
   {
      rep=query(1,1,n,x,y);
      ll re=0;int i,j;
      for(i=0;i<4;++i){
      	for(j=0;j<2;++j) re+=rep.a[i][1][j];
        re+=rep.b[i][1];
      }
      return re;
   } 
}sg;

struct bit{
    ll tre[2][N];
    
    void ad(int id,int x,int v)
    {for(;x<=n;x+=(x&(-x))) tre[id][x]+=v;}
    
    inline ll query(int id,int x)
    {
        ll re=0;
        for(;x;x-=(x&(-x))) re+=tre[id][x];
        return re;
    } 
    
    inline ll gt(int x,int y)
    {return query(1,y)-query(1,x)+query(0,y)-query(0,x-1);}
    
}bit;

int main(){
    int op,x,y,z,i;
    rd(n);
    for(i=1;i<=n;++i){
       rd(ini[i]);
       if(ini[i]) bit.ad(0,i,1);
       if(i>1 && (ini[i-1]^ini[i])) bit.ad(1,i,1);
    }
    sg.build(1,1,n);int TK=0;
    for(rd(m);m;--m){
        ++TK;
        rd(op);rd(x);
        if(op==1){
            ini[x]^=1;
            sg.change(1,1,n,x);
            bit.ad(0,x,ini[x]?1:(-1));
            if(x>1)
              bit.ad(1,x,(ini[x]==ini[x-1])?(-1):1);
            if(x