[壓位 手寫bitset] BZOJ 2628 JZPSTR

Hillan說 怎麼暴力怎麼寫

然後我們就每個數位用個bitset存一下就好了

因為bitset太難操作 自己手寫一個

詳見代碼

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;

inline char nc(){
  static char buf[],*p1=buf,*p2=buf;
  return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){
  char c=nc(),b=;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-;
  for (x=;c>='0' && c<='9';x=x*+c-'0',c=nc()); x*=b;
}
inline int read(char *s){
  char c=nc(); int len=;
  for (;!(c>='0' && c<='9');c=nc());
  for (;c>='0' && c<='9';s[++len]=c,c=nc()); return len;
}

const int N=;
const int B=;
ull ans[N/B];

struct Bitset{
  ull s[N/B]; int len;
  void set0(int x) { s[x>>]&=~(lu<<x); }
  void set1(int x) { s[x>>]|=lu<<x; }
  bool val(int x) { return s[x>>]>>x&; }
  void cpy(int x,int y) { if (val(y)) set1(x); else set0(x); }
  void insert(int x,int y){
    len+=y;
    int r=(len-)>>,l=(x+y)>>;
    int a=y>>,b=y&,c=-b;
    if (b)
      for (;r>l;r--) s[r]=s[r-a-]>>c|s[r-a]<<b;
    else
      for (;r>l;r--) s[r]=s[r-a];
    int p=((r+)<<)-;
    for (;p>=x+y;p--) cpy(p,p-y);
  }
  void erase(int x,int y){
    len-=y;
    for (;x<len && (x&);x++) cpy(x,x+y);
    if (x>=len) {
      for (x=len;x&;x++) set0(x);
      for (int i=(x>>);s[i];i++) s[i]=;
      return;
    }
    int l=x>>,r=(len-)>>;
    int a=y>>,b=y&,c=-b;
    if (b)
      for (;l<=r;l++) s[l]=s[l+a]>>b|s[l+a+]<<c;
    else
      for (;l<=r;l++) s[l]=s[l+a];
    for (;s[l];l++) s[l]=;
  }
  void extra(int x,int y){
    int r=(y-)>>;
    int a=x>>,b=x&,c=-b;
    if (b)
      for (int i=;i<=r;++i) ans[i]&=s[a+i]>>b|s[a+i+]<<c;
    else
      for (int i=;i<=r;++i) ans[i]&=s[a+i];
  }
  void print(){
    for (int i=;i<((len-)>>);i++)
      printf("%llu\n",s[i]);
  }
}bit[];

char s[N];

int cnt[];

inline void Pre(){
  for (int i=;i<;i++)
    cnt[i]=cnt[i>>]+(i&);
}
inline int count(ull x){
  return cnt[x&]+cnt[(x>>)&]+cnt[(x>>)&]+cnt[(x>>)&];
}

int main(){
  int ncnt=;
  int Q,order,x,y,len;
  freopen("Enchanters.in","r",stdin);
  freopen("Enchanters.out","w",stdout);
  read(Q); Pre();
  while (Q--){
    read(order); read(x);
    if (order==){
      len=read(s); y=len;
      for (int t=;t<;t++){
    bit[t].insert(x,y);
    for (int i=;i<=len;i++)
      if (s[i]==t+'0')
        bit[t].set1(x+i-);
      else
        bit[t].set0(x+i-);
      }
    }else if (order==){
      read(y); y-=x;
      for (int t=;t<;t++)
    bit[t].erase(x,y);
    }else{
      if ((++ncnt)==)
    ncnt=;
      read(y); y-=x;
      len=read(s);
      if (y<len){ printf("0\n"); continue; }
      int length=y-len+,p=(length-)>>,Ans=;
      for (int i=;i<=p;i++) ans[i]=-;
      for (int i=;i<=len;i++)
    bit[s[i]-'0'].extra(x+i-,length);
      for (int i=;i<p;i++)
    Ans+=count(ans[i]);
      if (length&)
    Ans+=count(ans[p]&((lu<<(length&))-));
      else
    Ans+=count(ans[p]);
      printf("%d\n",Ans);
    }   
  }
  return ;
}