CF1286E Fedya the Potter Strikes Back

, ,

Description

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

Solution

陈年老题。

平常因为我们只需要最大的 border，所以根本不用管删除那些小的 border。而这道题目要求我们在线维护出当前的 border 集合。也就是要求每次找出要删除的 border 集合。

观察到 border 构成一棵树，令 $f[i][j]$ 表示从 $i$ 开始，他的祖先 border 中最近的且下一个字符为 $j$。这可以从他的父亲转移过来。

这样我们可以做到每次快速找到要删除的 border。

权值的大小用单调栈+二分解决，集合用 map 维护值和值的个数。

复杂度 $O(n\log n)$。记得开 int128。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
#define int long long
#define LL __int128
#define ull unsigned long long
#define maxn 600005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
#define fi first
#define se second
#define mk make_pair
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
void print(LL ans) {
	if (ans>=10) print(ans/10);
	putchar(ans%10+'0');
}
int n;
int nex[maxn],s[maxn],w[maxn];
const int inf=1e15;
const LL MASK=(1<<30)-1;
int stac[maxn],tot,fa[maxn][27];
int query(int x) {
	return w[*lower_bound(stac+1,stac+1+tot,x)];
}
int Min;
LL ans,sum;
map<int,int>mp;
void add(int x,int y) {
	mp[x]+=y;
	sum+=x*y;
}
signed main(void){
	int i,id=0,j,now;char ch;
	read(n);
	cin>>ch>>w[1];ans=w[1];s[1]=ch-'a'+1;Min=w[1];
	print(ans);put();
	stac[tot=1]=1;
	for (i=2;i<=n;i++) {
		ch=getchar();while (ch<'a'||ch>'z') ch=getchar();read(w[i]);
		ch= 'a'+(ch-'a'+ans)%26;
		w[i]=w[i]^(ans&MASK);
		s[i]=ch-'a'+1;
		while (id&&s[i]!=s[id+1]) id=nex[id];
		if (s[i]==s[id+1]) id++;
		nex[i]=id;
		for (j=1;j<=26;j++) fa[i][j]=fa[nex[i]][j];
		fa[i][s[nex[i]+1]]=nex[i];
		
		for (j=1;j<=26;j++) {
			if (j==s[i]) continue;
			for (now=fa[i-1][j];now;now=fa[now][j]) {
				add(query(i-now),-1);
			} 
		}
		while (tot&&w[stac[tot]]>w[i]) tot--;
		stac[++tot]=i; 
		
		if (s[1]==s[i]) add(w[i],1);
		while (mp.begin()!=mp.end()&&(*--mp.end()).fi>w[i]) {
			auto it=--mp.end();
			auto tmp=*it;
			add(w[i],tmp.se);
			add(tmp.fi,-tmp.se);
			mp.erase(it);
		} 
		Min=min(Min,w[i]);
		ans+=Min+sum;
		print(ans);put();
 	}
    return 0;
}