一开始有一个空字符串,在线在后面加入字符,并且给出这个位置的权值。
然后当前字符串的分数是它所有 Border 的后缀部分的位置的权值最小值的和。
要你维护分数。
那不难看到每次只需要加入贡献在最后位置的贡献即可。
考虑有哪些可以的左端点,考虑之前的左端点,哪些可以留着,哪些要去掉(不难看到基本上都是前面的来的)
不难想象新多至多一个长度为
1
1
1 的。
那每次删除不会被加入,所以这个次数是
O
(
n
)
O(n)
O(n) 的。
然后考虑维护答案,因为新加入一个之前的位置的贡献可能会变。
考虑怎么改,那这个时候顺序也就无所谓了(如果你要删你可以直接线段树或者 ST 表,找到对应的位置删)
那考虑用 set 维护每个数出现多少次,那每次修改就把大的暴力找改成它。
考虑复杂度,势能分析,因为每次修改至少不会增加不同数的个数(甚至减少),而且复杂度是取决于不同数的个数的,所以复杂度是对的。
鹅不难看出会爆 long long 答案大概是两个 long long 乘起来所以弄两个 long long 维护即可,然后前面补 0 是 %018lld
鹅一个注意事项是你把答案分成两个 long long 是不可以直接用小的 long long 来取模的(显然,但是我忘了)
#include
#include
#include
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N = 6e5 + 100;
const ll di = 1e18;
const ll MASK = (1 << 30);
int n, nxt[N], fail[N][26]; ll a[N], sum, sta[N];
char s[N];
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);
}
struct XD_tree {
ll minn[N << 2];
void up(int now) {minn[now] = min(minn[now << 1], minn[now << 1 | 1]);}
void change(int now, int l, int r, int pl, ll val) {
if (l == r) {
minn[now] = val; return ;
}
int mid = (l + r) >> 1;
if (pl <= mid) change(now << 1, l, mid, pl, val);
else change(now << 1 | 1, mid + 1, r, pl, val);
up(now);
}
ll query(int now, int l, int r, int L, int R) {
if (L <= l && r <= R) return minn[now];
int mid = (l + r) >> 1; ll re = INF;
if (L <= mid) re = min(re, query(now << 1, l, mid, L, R));
if (mid < R) re = min(re, query(now << 1 | 1, mid + 1, r, L, R));
return re;
}
}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() {
scanf("%d", &n);
s[1] = getchar(); while (s[1] < 'a' || s[1] > 'z') s[1] = getchar();
scanf("%lld", &a[1]); T.change(1, 1, n, 1, a[1]); ans = (BIG){a[1], 0}; write(ans);
for (int i = 2, j = 0; i <= n; i++) {
s[i] = getchar(); while (s[i] < 'a' || s[i] > 'z') s[i] = getchar();
scanf("%lld", &a[i]);
s[i] = (s[i] - 97 + (ans % 26)) % 26 + 97; a[i] = a[i] ^ (ans % MASK);
while (j && s[i] != s[j + 1]) j = 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.change(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;
}