CF1286E-Fedya the Potter Strikes Back[KMP,RMQ]

Topics

Title link: https://www.luogu.com.cn/problem/CF1286E

Topic Essentials

Define a string s s The weight of s is for each s L ∼ R = s 1 ∼ R − L + 1 s_{L\sim R}=s_{1\sim R-L+1} sL_R = the interval of s1_R_L+1, which results in min ⁡ i = L R w i \min_{i=L}^Rw_i Mini=contribution from LR wi.

Now at the beginning s s s is an empty string, n n n times s s Add a character after s and go to w w w Sequence adds a number and finds the contribution of the string.

Force Online

1 ≤ n ≤ 6 × 1 0 5 , 1 ≤ w i < 2 30 1\leq n\leq 6\times 10^5,1\leq w_i<2^{30} 1≤n≤6×105,1≤wi​<230

Solving problems

We consider the contribution of all suffixes after each character addition, and then consider the change in contribution by adding a character suffix.

One idea is for the original suffix [ n − l e n , n − 1 ] [n-len,n-1] [n_len,n_1], if s l e n + 1 = s n s_{len+1}=s_n slen+1 = sn, then the new suffix [ n − l e n , n ] [n-len,n] [n_len,n] contributes, otherwise it does not. In addition to these, if s 1 = s n s_1=s_n s1 = sn then suffix [ n , n ] [n,n] [n,n] also contributes.

That is to say, adding at most one suffix contribution at a time, so let's consider how to maintain other previous suffixes.

Simple in terms of weight, [ n − l e n , n − 1 ] [n-len,n-1] Contributions from [n_len,n_1] go to [ n − l e n , n ] [n-len,n] The contribution of [n_len,n] is nothing more than to w i w_i wi fetch min ⁡ \min min, that is, we need a support to join delete all fetches m i n min The data structure of min. Actually it's okay to maintain violence, we use map records to record contributions for k k How many suffixes do k have, and then each violence will be greater than w i w_i You can modify all of the wi's so that the potential can be analyzed and you know it's right.

Now the second question is how we know which suffixes to delete each time. We build KMP's f a i l fail fail tree, then the contributing suffixes must all be n − 1 n-1 On the path from n_1 to the root node, we maintain a l a s i , c las_{i,c} lasi,c means node i i i First encountered on my way to my ancestors x x x Satisfaction s x + 1 = c s_{x+1}=c sx+1 =c's x x x, and then we can go up and find the suffix to delete.

use R M Q RMQ RMQ maintains the contribution of the suffix.

Time Complexity: O ( n log ⁡ n ) O(n\log n) O(nlogn)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define ll long long
using namespace std;
const ll N=6e5+10,mod=1e18;
ll n,lg[N],nxt[N],las[N][26],ans;
char s[N];map<ll,ll> mp;int f[N][20];
pair<ll,ll> sum;
pair<ll,ll> operator+(const pair<ll,ll> &x,const ll &y)
{return make_pair((x.first+y)%mod,x.second+(x.first+y)/mod);}
ll operator%(const pair<ll,ll> &x,const ll &p)
{return (x.first%p+(x.second%p)*(mod%p)%p)%p;}
void print(pair<ll,ll> x)
{
    if(x.second) printf("%lld%018lld\n",x.second,x.first);
    else printf("%lld\n",x.first);
}
ll Ask(ll l,ll r){
	ll z=lg[r-l+1];
	return min(f[r][z],f[l+(1<<z)-1][z]);
}
signed main()
{
	scanf("%lld",&n);
	for(ll i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
	ll mask=(1ll<<30),z=0;
	char op[2];ll w=0;
	scanf("%s%lld",op,&w);
	mp[w]++;ans=sum.first=w;
	s[1]=op[0];f[1][0]=w;
	printf("%lld\n",ans);
	for(ll p=2;p<=n;p++){
		scanf("%s%lld",op,&w);
		char c=op[0];
		c=(c-97+sum%26)%26+97;s[p]=c;
		w=w^(sum%mask);f[p][0]=w;
		for(ll i=1;(1<<i)<=p;i++)
			f[p][i]=min(f[p][i-1],f[p-(1<<i-1)][i-1]);
		while(z&&s[z+1]!=s[p])z=nxt[z];
		nxt[p]=(z+=(s[z+1]==s[p]));
		for(ll j=0;j<26;j++)las[p][j]=las[nxt[p]][j];
		las[p][s[nxt[p]+1]-'a']=nxt[p];
		for(ll j=0;j<26;j++){
			if(j+'a'==c)continue;
			for(ll x=las[p-1][j];x;x=las[x][j]){
				ll val=Ask(p-x,p-1);
				mp[val]--;ans=ans+(-val);
			}
		}
		while(mp.size()){
			map<ll,ll>::iterator it=mp.end();it--;
			pair<ll,ll> x=*it;
			if(x.first>w){
				ans=ans+(-(x.first-w)*x.second);
				mp[w]+=x.second;mp.erase(it);
			}
			else break;
		}
		if(s[p]==s[1])mp[w]++,ans=ans+w;
		sum=sum+ans;print(sum);
	}
	return 0;
}

Tags: string CodeForces KMP RMQ

Posted by stukov on Thu, 11 Aug 2022 21:26:50 +0300