当前位置:网站首页>【luogu CF1286E】Fedya the Potter Strikes Back(字符串)(KMP)(势能分析)(线段树)
【luogu CF1286E】Fedya the Potter Strikes Back(字符串)(KMP)(势能分析)(线段树)
2022-08-11 09:38:00 【SSL_TJH】
Fedya the Potter Strikes Back
题目链接:luogu CF1286E
题目大意
一开始有一个空字符串,在线在后面加入字符,并且给出这个位置的权值。
然后当前字符串的分数是它所有 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<map>
#include<cstdio>
#include<iostream>
#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;
}
边栏推荐
- 无代码平台助力中山医院搭建“智慧化管理体系”,实现智慧医疗
- 在软件工程领域,搞科研的这十年!
- Adobe LiveCycle Designer report designer
- How to analyze the neural network diagram, draw the neural network structure diagram
- The mathematical knowledge required for neural networks, the mathematical foundation of neural networks
- [wxGlade learning] wxGlade environment configuration
- Segmentation Learning (loss and Evaluation)
- ES6:数值的扩展
- Continuous Integration/Continuous Deployment (2) Jenkins & SonarQube
- 神经网络图怎么分析,画神经网络结构图
猜你喜欢
神经网络需要的数学知识,神经网络的数学基础
Three handshakes and four waves
期货开户最低的是交易所手续费不加佣金
Lightweight network (1): MobileNet V1, V2, V3 series
Primavera Unifier -AEM 表单设计器要点
Typora和基本的Markdown语法
验证拦截器的执行流程
The no-code platform helps Zhongshan Hospital build an "intelligent management system" to realize smart medical care
网络模型(U-net,U-net++, U-net+++)
盘点四个入门级SSL证书
随机推荐
mysql中查询多个表中的数据量
力扣题解8/10
数据中台方案分析和发展方向
Adobe LiveCycle Designer report designer
nodejs worker_threads的事件监听问题
VideoScribe stuck solution
Contrastive Learning Series (3)-----SimCLR
安装ES7.x集群
联想 U 盘装机后出现 start pxe over ipv4
疫情当前,如何提高远程办公的效率,远程办公工具分享
Primavera Unifier 自定义报表制作及打印分享
收集awr
The no-code platform helps Zhongshan Hospital build an "intelligent management system" to realize smart medical care
Primavera P6 Professional 21.12 Login exception case sharing
仙人掌之歌——大规模高速扩张(1)
无代码平台助力中山医院搭建“智慧化管理体系”,实现智慧医疗
How to use QTableWidget
基于PSO在满足可靠性的基础上实现费用最优MATLAB仿真(含完整matlab代码)
What should I do if the mysql data query causes the cup to be full because the query time span is too large
HDRP shader 获取阴影(Custom Pass)