UVa-11402 (RTE)

/*
* Omar
* UVa-11402
*/

#include <stdio.h>
#include <string.h>

typedef enum mode {NORM,INV,ONE,ZERO} mode;

char str[1024100], *end=str;
int seg[1024010*5];
mode lazy[1024010*5];

void dup(char *tmp, int n){int i,j;
  for(i=0 ; i<n ; i++)
    for(j=0 ; tmp[j] ; j++)
      *end=tmp[j]-'0', end++;
}
int build(int p, int L, int R){
  if(L==R) return seg[p]=str[L];

  int a = build(p<<1, L, (L+R)/2);
  int b = build((p<<1)+1, (L+R)/2+1, R);

  return seg[p]=a+b;
}
void change_mode(int p, mode m){
  if(m==NORM)       return;
  else if(m==ONE)   lazy[p]=ONE;
  else if(m==ZERO)  lazy[p]=ZERO;
  else if(m==INV){
    if(lazy[p]==NORM)       lazy[p]=INV;
    else if(lazy[p]==INV)   lazy[p]=NORM;
    else if(lazy[p]==ONE)   lazy[p]=ZERO;
    else if(lazy[p]==ZERO)  lazy[p]=ONE;
  }
}
void Lazy_UPD(int p, int len, mode m){
  if(m==NORM) return;
  else if(m==ONE) seg[p]=len;
  else if(m==ZERO) seg[p]=0;
  else if(m==INV) seg[p]=len-seg[p];
}
int RcntQ(int p, int L, int R, int i, int j){
  if(i>R || j<L) return 0;

  Lazy_UPD(p, R-L+1, lazy[p]);
  if(L!=R){
    change_mode( p<<1   , lazy[p]);
    change_mode((p<<1)+1, lazy[p]);
  }
  lazy[p]=NORM;

  if(L>=i && R<=j) return seg[p];

  int a = RcntQ(p<<1, L, (L+R)/2, i, j);
  int b = RcntQ((p<<1)+1, (L+R)/2+1, R, i, j);

  return a+b;
}
int UPD(int p, int L, int R, int i, int j, mode m){
  if(i>R || j<L) return 0;

  Lazy_UPD(p, R-L+1, lazy[p]); /*Resolve any pending Update.*/
  int before = seg[p];  /*Store value before performing the target Update*/
  if(L!=R){
    change_mode( p<<1   , lazy[p]);
    change_mode((p<<1)+1, lazy[p]);
  }
  lazy[p]=NORM;

  if(L>=i && R<=j)
  {
    Lazy_UPD(p, R-L+1, m);
    if(L!=R){
      change_mode( p<<1   , m);
      change_mode((p<<1)+1, m);
    }
    return seg[p]-before;
  }

  int a = UPD(p<<1, L, (L+R)/2, i, j, m);
  int b = UPD((p<<1)+1, (L+R)/2+1, R, i, j, m);

  seg[p]+= a+b; /*Update node*/
  return seg[p]-before;
}

int main(){
  int T,M,i,j,q;
  scanf("%i", &T);
  for(i=1 ;i<=T;i++)
  {
    memset(lazy, 0, sizeof(lazy));
    end=str;
    printf("Case %i:\n", i);
    for(scanf("%i",&M);M--;)
    {
      int n;
      char tmp[111];
      scanf("%i%s",&n,tmp);
      dup(tmp,n);
    }
    *end='\0';
    build(1, 0, (end-str-1));
    scanf("%i",&M);
    for(j=1, q=1;j<=M; j++)
    {
      char ch[10];
      int l,r;
      scanf("%s%i%i", ch, &l,&r);
      if(ch[0]=='S') printf("Q%i: %i\n", q++, RcntQ(1, 0, (end-str-1), l, r));
      else {
        mode m = ch[0]=='F'?ONE:ch[0]=='E'?ZERO:INV;
        UPD(1, 0, (end-str-1), l, r, m);
      }
    }
  }
}