Fedya the Potter Strikes Back
一上午过去了……
关于当前时刻的所有子串，它的前缀提前算出来的答案可以直接加，所以只考虑在原有的答案上修改最后一个i添加的贡献，发现他是一堆border，只是多加上了它自己。本来打算每加一次就让它跳所有的nxt，每次求区间最小值(线段树单点修改区间查询)，似乎会T。
但其实产生贡献的border也可以从前面继承，之前的border在续上一个字母s[i+1]后依然有效的条件是s[i+1]==s[lenx+1]。除了长度为1和全部的特殊情况，其它的贡献一定全都来自继承，对每一种合法的情况的前后分别删掉最后一个字符，就得到了上一个的某个border。
于是不只有最终答案可以从上一个累加，新的单步答案也可以由上一个单步答案修改得到。
考虑单步答案的修改。特殊情况直接加入，把上一个的border分成两组：对当前位置合法的和不合法的。
不合法的
- 不合法的贡献需要删掉，如果可以知道不合法border的左端点和右端点就可以查到这个区间最小值。为了在i快速找到每个以i-1结尾的不合法border的长度，我们要在i进行预处理为i+1做准备。
- 把每一种字母当成颜色得到26个组，i的所有border可以通过不停地跳nxt找到，找到构成border的前缀部分，按照它的下一项分组。比较不合法的时候找到不合法的下一项，就可以从长到短的找出所有。如果把每一组当成一条链，就只需要连接上一个，结果就是按颜色分开的26棵fail树。
- 假设现在循环到i，已知i的一个border的长度是nxt[i]，循环到i+1时这个border不被删除要求s[i+1]==s[nxt[i]+1]，因为s[i+1]还未知，把这个border分到第s[nxt[i]+1]组里备用。
合法的
- 它会继续贡献，但是它贡献的大小可能改变，新加入的数可能修改区间最小值。记录每一个贡献的大小和它贡献的次数，二分找到比a[i]大的全都修改成a[i]，并且把它的出现次数累记到a[i]的出现次数上。过程大概比较暴力。
- 第一次发现map的自动排序派上用场。
于是我们愉快地得到了单步的答案，但是还有细节。
这个总数会爆long long，可以选择开个高精度，但是也可以开两位long long表示答案。%018lld表示不够18位在左侧补0，取模也很神奇
int operator % (BIG x, int y)
{
return (x.ans1 % y + (x.ans2 % y) * (di % y) % y) % y;
}还有位运算，&((1<<30)-1)表示只有末30位有效，并且只要ans对应是1运算结果就是1，所以它就相当于对(1<<30)取模。
关于fail树 我本来一直以为是一个多么高级的东西……
code是鹤的
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 6e5 + 3;
const ll di = 1e18;
const ll MASK = (1 << 30);//把&变成%
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, nxt[maxn], fail[maxn][26];
ll a[maxn], sum, sta[maxn];
char s[maxn], c[3];
map<ll, int> mp;
struct BIG
{
ll ans1, ans2;
}ans;
BIG operator + (BIG x, ll y)
{
return (BIG){(x.ans1 + y) % di, x.ans2 + (x.ans1 + y)/di};
}
int operator % (BIG x, int y)
{
return (x.ans1 % y + (x.ans2 % y) * (di % y) % y) % y;
}
void write(BIG x)
{
if(x.ans2) printf("%lld%018lld\n", x.ans2, x.ans1);
else printf("%lld\n", x.ans1);
}
inline ll read()
{
ll x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
struct seg
{
struct node
{
ll min;
}t[maxn<<2];
void pushup(int x)
{
t[x].min = min(t[x<<1].min, t[x<<1|1].min);
}
void update(int x, int l, int r, int pos, ll val)
{
if(l == r)
{
t[x].min = val; return;
}
int mid = (l + r) >> 1;
if(pos <= mid) update(x<<1, l, mid, pos, val);
else update(x<<1|1, mid+1, r, pos, val);
pushup(x);
}
ll query(int x, int l, int r, int L, int R)
{
if(L <= l && r <= R) return t[x].min;
int mid = (l + r) >> 1; ll ans = inf;
if(L <= mid) ans = min(ans, query(x<<1, l, mid, L, R));
if(R > mid) ans = min(ans, query(x<<1|1, mid+1, r, L, R));
return ans;
}
}t;
void Insert(ll x)
{
int num = 0; sta[0] = 0;
for(map<ll, int>::iterator it=mp.lower_bound(x); it!=mp.end(); it++)
{
sta[++sta[0]] = (*it).first; num += (*it).second; sum -= (*it).first * (*it).second;
}
while(sta[0]) mp.erase(sta[sta[0]--]);
mp[x] += num; sum += x * num;
}
int main()
{
n = read();
scanf("%s", c); s[1] = c[0];
a[1] = read(); t.update(1, 1, n, 1, a[1]); ans = (BIG){a[1], 0};
write(ans);
for(int i=2,j=0; i<=n; i++)
{
scanf("%s", c); s[i] = c[0];
a[i] = read();
s[i] = (s[i]-97+(ans%26)%26)%26+97; a[i] = a[i]^(ans%MASK);
while(j && s[i] != s[j+1]) aj = nxt[j];
if(s[i] == s[j+1]) j++; nxt[i] = j;
for(int k=0; k<26; k++)
{
if('a'+k == s[nxt[i]+1]) fail[i][k] = nxt[i];
else fail[i][k] = fail[nxt[i]][k];
}
t.update(1, 1, n, i, a[i]); ans = ans + t.query(1, 1, n, 1, i);
if(s[i] == s[1])
{
mp[a[i]]++; sum += a[i];
}
for(int k=0; k<26; k++)
{
if('a'+k != s[i])
{
for(int now=fail[i-1][k]; now; now=fail[now][k])
{
ll val = t.query(1, 1, n, i-1-now+1, i-1);
mp[val]--; sum -= val;
}
}
}
Insert(a[i]);
ans = ans + sum; write(ans);
}
return 0;
}标签：ch,来自,int,BIG,ll,学长,ans1,字符串,border From： https://www.cnblogs.com/Catherine2006/p/16873180.html