Problem C: substring in the Noip 2019 Training and Testing Competition

subject

You have a string.

You need to support two operations.

1: Insert a character c at the end of the string

2: Ask the number of different substrings in the [l,r] substring of the current string

Mandatory Online

n,m<=50000

thinking

Violence:

Direct SAM is O(N3)

Positive solution:

It is not difficult to find that operation 1 of this problem is the extension process of SAM.

If the length of the string is len after one operation, then the next extension will add all the substrings ending at len bit to the string.

These substrings correspond to the chain from a leaf node to the root on the parents tree of SAM, and that leaf node is the node of your new substring S1 len.

So we consider using LCT to dynamically maintain the parents tree of SAM.

Ah, disgusting, the scene can only be made by the immortals! ____________

Put last in the same splay

We consider how to maintain the number of different substrings in an interval [l,r].
This problem can be simplified to give you n numbers, each time you ask how many different numbers are in an interval [l,r].
So, let's reprimand!!! Subtract the number of non-last occurrences from the total number.

Consider the preprocessing answer, add each number in turn from the beginning to the end, add the number i, that is, add the number i of the first version of the presidential tree to 1. If the number has appeared before, let lst be the last occurrence position, then the j th position of the first version of the presidency tree is minus 1.

So the number of different substrings in the interval can be similarly solved by the chair tree.

So, code code!!!!!

Long, more than 200 lines

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+77;
int n,m,maxlen,rt[N][2];
struct SegmentTree
{
	int ls[N*100],rs[N*100],sz,siz[N*100];
	ll sumv[N*100];
	int cpyNode(int pre)
	{
		int x=++sz;
		ls[x]=ls[pre];
		rs[x]=rs[pre];
		sumv[x]=sumv[pre];
		siz[x]=siz[pre];
		return x;
	}
	void update(int & o,int pre,int l,int r,int ql,int qr,int v)
	{
		o=cpyNode(pre);
		if(ql==l && qr==r) { sumv[o]+=v,siz[o]++; return; }
		int mid=(l+r)>>1;
		if(qr<=mid)
			update(ls[o],ls[pre],l,mid,ql,qr,v);
		else if(ql>mid)
			update(rs[o],rs[pre],mid+1,r,ql,qr,v);
		else
			update(ls[o],ls[pre],l,mid,ql,mid,v),
			update(rs[o],rs[pre],mid+1,r,mid+1,qr,v);
	}
	int querySize(int o,int l,int r,int p)
	{
		if(l==r) return siz[o];
		int mid=(l+r)>>1;
		int Ans=siz[o];
		if(p<=mid) Ans+=querySize(ls[o],l,mid,p);
		else Ans+=querySize(rs[o],mid+1,r,p);
		return Ans;
	}
	ll querySum(int o,int l,int r,int p)
	{
		if(l==r) return sumv[o];
		int mid=(l+r)>>1;
		ll Ans=sumv[o];
		if(p<=mid) Ans+=querySum(ls[o],l,mid,p);
		else Ans+=querySum(rs[o],mid+1,r,p);
		return Ans;
	}
}rap;

namespace LCT
{
	static const int SIZE=2e5+77;
	int ch[SIZE][2],fa[SIZE];
	int pos[SIZE],len[SIZE];
	bool isrt(int x) { return !fa[x] || (ch[fa[x]][0] != x && ch[fa[x]][1] != x); }
	bool c(int x) { return ch[fa[x]][1]==x; }
	void rotate(int x)
	{
		int f=fa[x],p=fa[f],d=c(x);
		if(!isrt(f)) ch[p][c(f)]=x;
		fa[x]=p;
		ch[f][d]=ch[x][d^1]; fa[ch[f][d]]=f;
		ch[x][d^1]=f; fa[f]=x;
	}
	int findrt(int x) { return !isrt(x) ? findrt(fa[x]) : x; }
	void splay(int x)
	{
		swap(pos[findrt(x)],pos[x]);
		while(!isrt(x))
		{
			int f=fa[x];
			if(!isrt(f))
			{
				if(c(f)==c(x)) rotate(f);
				else rotate(x);
			}
			rotate(x);
		}
	}
	void access(int x,int i)
	{
		rt[i][0]=rt[i-1][0];
		rt[i][1]=rt[i-1][1];
		for(int v=0; x; v=x,x=fa[x])
		{
			splay(x);
			if(len[x] && pos[x])
			{
				int pl=pos[x]-len[x]+1,pr=pos[x]-len[fa[x]];
				if(pl>1) rap.update(rt[i][0],rt[i][0],1,maxlen,1,pl-1,pr-pl+1);
				rap.update(rt[i][1],rt[i][1],1,maxlen,pl,pr,pr);
			}
			if(ch[x][1]) pos[ch[x][1]]=pos[x];
			ch[x][1]=v;
			pos[v]=0;
			pos[x]=i;
		}
	}
	void cut(int x)
	{
		splay(x);
		pos[ch[x][0]]=pos[x];
		fa[ch[x][0]]=fa[x];
		ch[x][0]=0;
	}
	void link(int x,int y)
	{
		splay(x);
		fa[x]=y;
	}
}


struct SAM
{
	static const int SIZE=2e5+77;
	int nxt[SIZE][26],fa[SIZE],sz,pos[SIZE],len[SIZE],rt,last;
	SAM() { init(); }

	int newnode(int l,int id)
	{
		memset(nxt[sz],0,sizeof(nxt[sz]));
		pos[sz]=id;
		fa[sz]=0;
		len[sz]=l;
		return sz++;
	}

	void init()
	{
		sz=1;
		rt=newnode(0,0);
		last=rt;
	}

	void add(char x,int i)
	{
		int c=x-'a';
		int now=newnode(len[last]+1,i);
		LCT::len[now]=len[now];
		int p=last;
		while(p && !nxt[p][c])
		{
			nxt[p][c]=now;
			p=fa[p];
		}
		if(!p) LCT::link(now,fa[now]=rt);
		else
		{
			int q=nxt[p][c];
			if(len[p]+1==len[q])
				LCT::link(now,fa[now]=q);
			else
			{
				int u=newnode(len[p]+1,pos[q]);
				LCT::len[u]=len[u];
				for(int i=0; i<26; i++) nxt[u][i]=nxt[q][i];
				LCT::cut(q);
				LCT::pos[u]=LCT::pos[q];
				LCT::link(u,fa[u]=fa[q]);
				LCT::link(now,fa[now]=u);
				LCT::link(q,fa[q]=u);
				while(nxt[p][c]==q)
				{
					nxt[p][c]=u;
					p=fa[p];
				}
			}
		}
		LCT::access(now,i);
		
		last=now;
	}
}cxk;

char str[N];
int type;
int main()
{
	scanf("%d",&type);
	scanf("%s %d",str+1,&m);
	n=strlen(str+1);
	maxlen=n+m;
	for(int i=1; i<=n; i++)
		cxk.add(str[i],i);
	ll lastans=0;
	for(int i=1; i<=m; i++)
	{
		int opt;
		scanf("%d",&opt);
		if(opt==1)
		{
			char ch[5];
			scanf("%s",ch);
			str[++n]=(ch[0]-'a'+type*lastans)%26+'a';
			cxk.add(str[n],n);
		}
		else
		{
			int l,r;
			scanf("%d%d",&l,&r);
			l=(l-1+lastans*type)%n+1;
			r=(r-1+lastans*type)%n+1;
			ll val1=rap.querySum(rt[r][0],1,maxlen,l);
			ll val2=rap.querySum(rt[r][1],1,maxlen,l);
			ll val3=rap.querySize(rt[r][1],1,maxlen,l);
			lastans=1ll*(r-l+1)*(r-l+2)/2ll;
			lastans-=val1;
			lastans-=val2-1ll*(l-1)*val3;
			printf("%lld\n",lastans);
		}
	}
}

Posted on Thu, 29 Aug 2019 05:51:49 -0700 by keyurjbhatt