ABC470G
2026-08-09 08:58:53
发布于：浙江
35阅读
0回复
0点赞
耗时 97min 这一块（（（
考虑扫描右端点 ，求出 。
我们开个桶，定义 为 之前最后出现 的位置。于是 的充要条件就是 。
然后随便整一下式子，发现此时答案为 。
于是就变成了单点改，求全局前缀最大值之和。
这个直接做应该也可以，但是我们又发现一个很好的性质，修改的数一定为 。
所以我们从右往左扫描 ，显然此时修改的值单调递减。每个点取个前缀 就转化成了后缀 ，查询全局和。这个可以线段树二分实现。一个可行的做法是用线段树分别维护区间 ，分类讨论进行二分。有更好的方法踢我。
什么叫我线段树调了 70min？
代码很史，将就着看一下。
namespace cjdst{
const int N = 1200000;
ll tr[N + 5], tr3[N + 5], tr2[N + 5], lazytag[N + 5];
int lst[N + 5], lst2[N + 5], pre[N + 5];
int a[N + 5];
void update(int u, ll l, ll r){
tr2[u] = tr[u] * (r - l + 1);
}
void build(int u, int l, int r){
if(l == r){
tr[u] = tr2[u] = tr3[u] = pre[l];
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
tr[u] = std::max(tr[u << 1], tr[u << 1 | 1]);
tr3[u] = std::min(tr3[u << 1], tr3[u << 1 | 1]);
tr2[u] = tr2[u << 1] + tr2[u << 1 | 1];
}
void push_down(int u, int l, int r, int mid){
if(lazytag[u] == 0x3f3f3f3f3f3f3f3fll) return;
lazytag[u << 1] = lazytag[u];
lazytag[u << 1 | 1] = lazytag[u];
tr[u << 1] = lazytag[u];
tr[u << 1 | 1] = lazytag[u];
tr3[u << 1] = lazytag[u];
tr3[u << 1 | 1] = lazytag[u];
update(u << 1, l, mid);
update(u << 1 | 1, mid + 1, r);
lazytag[u] = 0x3f3f3f3f3f3f3f3fll;
}
void modify(int u, int l, int r, int l2, ll val){
if(tr[u] <= val) return;
if(r < l2) return;
if(l >= l2 && tr3[u] >= val){
tr[u] = tr3[u] = lazytag[u] = val;
update(u, l, r);
return;
}
int mid = (l + r) >> 1;
push_down(u, l, r, mid);
modify(u << 1, l, mid, l2, val);
modify(u << 1 | 1, mid + 1, r, l2, val);
tr[u] = std::max(tr[u << 1], tr[u << 1 | 1]);
tr3[u] = std::min(tr3[u << 1], tr3[u << 1 | 1]);
tr2[u] = tr2[u << 1] + tr2[u << 1 | 1];
}
void solve(){
memset(lazytag, 63, sizeof(lazytag));
int n;
std::cin >> n;
for(int i = 1; i <= n; i++){
std::cin >> a[i];
a[i]++;
lst[i] = lst2[a[i]];
lst2[a[i]] = i;
}
for(int i = 1; i <= n + 1; i++){
pre[i] = lst2[i];
if(i > 1) pre[i] = std::min(pre[i], pre[i - 1]);
}
build(1, 1, n + 1);
ll ans = 0;
for(int i = n; i; i--){
ans += tr2[1];
modify(1, 1, n + 1, a[i], lst[i]);
}
std::cout << ans << '\n';
}
}
时间复杂度：。
有帮助，赞一个