记录编号	491075	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]JZPSTR	最终得分	100
用户昵称	Magolor	是否通过	通过
代码语言	C++	运行时间	21.588 s
提交时间	2018-03-14 16:24:37	内存使用	1.94 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;
#define MAXN 1000000
#define ull unsigned long long
#define rint register int
#define gc() getchar()
inline int read(int r=0,int s=0,int c=gc()){for(;c<48||c>57;s=c,c=gc());for(;c>=48&&c<=57;(r*=10)+=c-48,c=gc());return s^'-'?r:-r;}
int c[65536], n, w; inline int bitc(ull x){return c[x&65535]+c[(x>>16)&65535]+c[(x>>32)&65535]+c[(x>>48)&65535];}
struct Bits
{
	ull b[16400]; inline void reset(){memset(b,0,-~w<<3), w = n = 0;} inline int at(int i){return b[i>>6]>>(i&63)&1;}
	inline void set(int i, ull v=1){(b[i>>6] &= ~(1ull<<(i&63))) |= v<<(i&63);} inline void o(){for(rint i = 0; i <= n; putchar(at(i)+'0'), i++); cout << endl;}
	inline void shl(int l, int k){b[w+(k>>6)+1] = 0; for(rint i = w, d = k&63; i > (l>>6); b[i+(k>>6)+1] |= b[i]>>(64-d), b[i+(k>>6)] = b[i]<<d, i--); for(rint i = l|63; i >= l; set(i+k,at(i)), i--);}
	inline void shr(int l, int k){for(rint i = l; i <= (l|63); set(i,at(i+k)), i++); for(rint i = -~(l>>6), d = k&63; i <= w; b[i] = b[i+(k>>6)]>>d, b[i] |= b[i+(k>>6)+1]<<(64-d), i++);}
	inline void copy(Bits& B, int wl, int wr){memcpy(b+wl,B.b+wl,(wr-wl+1)<<3);}
	inline void ande(Bits &B, int wl, int wr){for(rint i = wl; i <= wr; b[i] &= B.b[i], i++);}
	inline void shl1(int wl, int wr){for(rint i = wr; i >= wl; b[i] <<= 1, b[i] |= i&&(b[i-1]>>63)&1, i--);}
	inline int count(int l, int r, int _=0){for(; l&63&&l<=r; _ += at(l++)); for(; (r&63)^63&&l<=r; _ += at(r--)); for(; l <= r; _ += bitc(b[l>>6]), l += 64); return _;}
}B[10], S; string _;
void Delete(int l, int r){if(l>r) return; for(rint j = 0; j < 10; B[j].shr(l,r-l+1), j++); n -= r-l+1, w = n>>6;}
void Insert(int l, string &_){for(rint j = 0, i; j < 10; j++) for(B[j].shl(l,_.length()), i = 0; i < _.length(); B[j].set(l+i,_[i]-'0'==j), i++); n += _.length(), w = n>>6;}
int Query(int l, int r, string &_){if(r-l+1 < _.length()) return 0; S.copy(B[_[0]-'0'],l>>6,r>>6); for(rint i = 1; i < _.length(); S.shl1(l>>6,r>>6), S.ande(B[_[i]-'0'],l>>6,r>>6), i++); return S.count(l+_.length()-1,r);}
void Print(){cerr << n << endl; for(rint i = 0; i < 10; B[i].o(), i++); putchar('\n');}
int main()
{
	freopen("jzpstr.in","r",stdin), freopen("jzpstr.out","w",stdout);
	for(rint i = 1; i < 65536; c[i] = -~c[i-(i&-i)], i++);
	for(rint q = read(), x, y; q--; ) switch(read())
		{case 0: x = read(), cin >> _, Insert(x,_); break; case 1: x = read(), Delete(x,read()-1); break; case 2: x = read(), y = read(), cin >> _, printf("%d\n",Query(x,y-1,_)); break;} return 0;
}