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

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

using namespace std;
#define MAXN 1500000
#define BLK 2048
#define pb push_back
#define c(x,y) t[x].c[y]
#define link(x) t[x].link
#define maxlen(x) t[x].maxlen
#define mx(x) t[x].mx
#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;}
struct Node{int c[10],link,maxlen,mx;}t[(MAXN<<1)+5]; int tr[MAXN+5], book[MAXN+5], o[MAXN+5], cnt, top;
inline int New(int p, int v){static int x; top ? memset(t[x=tr[top--]].c,0,40),0 : x=++cnt; maxlen(x) = p?maxlen(p)+1:0, mx(x) = v, link(x) = 0; return x;}
/*struct Hash
{
	int h1,h2; Hash(){} Hash(int _h1, int _h2){h1=_h1,h2=_h2;}
	inline Hash operator + (Hash b){return Hash((h1+b.h1)%MOD1,(h2+b.h2)%MOD2);}
	inline Hash operator - (Hash b){return Hash((h1+MOD1-b.h1)%MOD1,(h2+MOD2-b.h2)%MOD2);}
	inline Hash operator * (Hash b){return Hash(1ll*h1*b.h1%MOD1,1ll*h2*b.h2%MOD2);}
	inline bool operator ==(Hash b){return h1==b.h1&&h2==b.h2;} inline bool operator !=(Hash b){return h1^b.h1||h2^b.h2;}
}B[MAXN+5];*/
unsigned  B[MAXN+5];
struct Block
{
	string s; int start, last, nex, n; unsigned h[BLK+5]; vector<int> tra; void Free(){for(rint i = 0; i < tra.size(); tr[++top] = tra[i++]); tra.clear();}
	void Append(int x)
	{
		rint p = last, np = last = New(p,1), q, nq; tra.pb(np); for(; p&&!c(p,x); c(p,x) = np, p = link(p));
		if(!p) link(np) = start; else if(maxlen(q=c(p,x))==maxlen(p)+1) link(np) = q; else
		{for(tra.pb(nq=New(p,0)), memcpy(t[nq].c,t[q].c,40); p&&c(p,x)==q; c(p,x) = nq, p = link(p)); link(nq) = link(q), link(q) = link(np) = nq;}
	}
	void Build()
	{
		last = start = New(0,0), n = s.length(); for(rint i = 0; i < n; h[i] = (i?h[i-1]:0)*B[1]+s[i], Append(s[i++]-'0'));
		memset(book,0,-~n<<2); for(rint i = 0; i < tra.size(); ++book[maxlen(tra[i++])]); for(rint i = 1; i <= n; book[i] += book[i-1], i++);
		for(rint i = tra.size(); i; o[book[maxlen(tra[i-1])]--] = tra[i-1], i--); for(rint i = tra.size(); i; mx(link(o[i])) += mx(o[i]), i--);
	}
	int Run(string T, rint p=0){p = start; for(rint i = 0; i < T.length() && (p=c(p,T[i]-'0')); i++); return p?mx(p):0;}
	inline unsigned Pv(int l){return l&&l<=n?h[l-1]:0;} inline unsigned Sv(int l){return l<=n?h[n-1]-(l<n?h[n-l-1]*B[l]:0):0;}
}C[2049]; int trb[MAXN+5], topb, cntb; string _; inline int Newb(){return topb ? trb[topb--] : ++cntb;}
void Print(int len=0)
{
//for(rint p = 0; ~p; len += C[p].s.length(), p = C[p].nex); cout << '(' << len << ')' << "#" << cnt <<endl;
//cout << "$"; for(rint p = 0; ~p; cout << C[p].s << " => ", len += C[p].s.length(), p = C[p].nex); cout << '(' << len << ')' << "#" <<endl;
}
void Split(int b, int p)//position from block b with 0-index
{
	if(p==C[b].n-1) return; static int t; C[t=Newb()].nex = C[b].nex, C[b].nex = t, C[b].Free(), C[t].Free();
	C[t].s = C[b].s.substr(p+1,C[b].n-p-1), C[b].s = C[b].s.substr(0,p+1), C[b].Build(), C[t].Build();
}
int Split(int l)
{static int b; for(b = 0; l >= C[b].n; l -= C[b].n, b = C[b].nex); Split(b,l); return b;}
bool Merge(int b)
{static int t; return ~(b?:b=C[b].nex)&&~(t=C[b].nex)&&C[b].n+C[t].n<=BLK ? C[b].nex = C[t].nex, C[trb[++topb]=t].Free(), C[b].Free(), C[b].s += C[t].s, C[b].Build(), true : false;}
void Insert(int p, string &_)//after insertion _[0] should be at position p
{static int h,t,j,l,o,m; for(m = _.length(), o = C[t=h=Split(--p)].nex, j = 0; j < m; C[t=C[t].nex=Newb()].s = _.substr(j,l=min(BLK,m-j)), C[t].Build(), j += l); C[t].nex = o, Merge(t), Merge(h);}
void Delete(int p, int l)
{static int h,t,j; for(Split(p+l-1), t = C[h=Split(--p)].nex, j = p+1; j <= p+l; C[t].Free(), trb[++topb] = t, j += C[t].n, t = C[t].nex); C[h].nex = t, Merge(h);}
int Query(int p, int l, string &_)
{
	static int h,t,j,o,m,Ans; static unsigned hs; for(Ans = 0, m = _.length(), hs = 0, o = 0; o < m; hs = hs*B[1]+_[o], o++);
	for(Split(p+l-1), t = C[h=Split(--p)].nex, j = p+1; j <= p+l; C[t].n >= m ? Ans += C[t].Run(_) : 0, j += C[t].n, t = C[t].nex) for(; j+C[t].n-1 < p+l && ~C[t].nex && Merge(t); );
	for(t = C[h].nex, j = p+1; j <= p+l; j += C[t].n, t = C[t].nex) for(o = 1; o < m; j+C[t].n-o>=0&&j+C[t].n+m-o-1<=p+l ? Ans += C[t].Sv(o)*B[m-o]+C[C[t].nex].Pv(m-o)==hs : 0, o++);
	Merge(h); return Ans;
}	
int main()
{
	freopen("jzpstr.in","r",stdin), freopen("jzpstr.out","w",stdout);
	B[0] = 1; B[1] = 313; for(rint i = 2; i <= MAXN; B[i] = B[i-1]*B[1], i++); C[0].nex = -1;
	for(rint q = read(), x, y; q--; ) switch(read())
	{
		case 0: x = read(), cin >> _, Insert(x,_); break;
		case 1: x = read(), Delete(x,read()-x); break;
		case 2: x = read(), y = read(), cin >> _, printf("%d\n",Query(x,y-x,_)); break;
	}	return 0;
}