[BZOJ4636]蒟蒻的数列

时间:2022-04-09 03:45:36

[BZOJ4636]蒟蒻的数列

试题描述

蒟蒻DCrusher不仅喜欢玩扑克,还喜欢研究数列
题目描述
DCrusher有一个数列,初始值均为0,他进行N次操作,每次将数列[a,b)这个区间中所有比k小的数改为k,他想知
道N次操作后数列中所有元素的和。他还要玩其他游戏,所以这个问题留给你解决。

输入

第一行一个整数N,然后有N行,每行三个正整数a、b、k。
N<=40000 , a、b、k<=10^9

输出

一个数,数列中所有元素的和

输入示例


输出示例


数据规模及约定

见“输入

题解

题目问的是最后的总和,所以对于每个元素我们只关心它经过所有包含它的操作后的值。每个操作 [a, b) -> k 建一个点 (a, b-1),权值为 k,则对于第 i 个数,找到点 (i, i) 左上方所有点的最大权值即为这个数最终的值。

看到这样的水题,而且数据范围又是 40000,感觉非常像带根号的算法,就忍不住写 kd 树了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std; const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
return x * f;
} #define maxn 40010
#define oo 2147483647
#define LL long long
int n, lc[maxn], rc[maxn], root, Cur;
struct Node {
int x[2], mx[2], mn[2], val, maxv;
bool operator < (const Node& t) const { return x[Cur] != t.x[Cur] ? x[Cur] < t.x[Cur] : x[Cur^1] < t.x[Cur^1]; }
} ns[maxn], x; void maintain(int o) {
int l = lc[o], r = rc[o];
for(int i = 0; i < 2; i++) {
ns[o].mx[i] = max(max(ns[l].mx[i], ns[r].mx[i]), ns[o].x[i]);
ns[o].mn[i] = min(min(ns[l].mn[i], ns[r].mn[i]), ns[o].x[i]);
}
ns[o].maxv = max(max(ns[l].maxv, ns[r].maxv), ns[o].val);
return ;
}
void build(int& o, int L, int R, int cur) {
if(L > R){ o = 0; return ; }
int M = L + R >> 1; o = M;
Cur = cur; nth_element(ns + L, ns + M, ns + R + 1);
build(lc[o], L, M - 1, cur ^ 1); build(rc[o], M + 1, R, cur ^ 1);
maintain(o);
return ;
}
bool all(int o) { return ns[o].mx[0] <= x.x[0] && ns[o].mn[1] >= x.x[1]; }
bool has(int o) { return ns[o].mn[0] <= x.x[0] && ns[o].mx[1] >= x.x[1]; }
int query(int o) {
if(!o) return 0;
int l = lc[o], r = rc[o], ans = 0;
if(ns[o].x[0] <= x.x[0] && ns[o].x[1] >= x.x[1]) ans = ns[o].val;
if(ns[l].maxv > ns[r].maxv) {
if(all(l)) ans = max(ans, ns[l].maxv);
else if(has(l) && ns[l].maxv > ans) ans = max(ans, query(l));
if(all(r)) ans = max(ans, ns[r].maxv);
else if(has(r) && ns[r].maxv > ans) ans = max(ans, query(r));
}
else {
if(all(r)) ans = max(ans, ns[r].maxv);
else if(has(r) && ns[r].maxv > ans) ans = max(ans, query(r));
if(all(l)) ans = max(ans, ns[l].maxv);
else if(has(l) && ns[l].maxv > ans) ans = max(ans, query(l));
}
return ans;
} struct Cmd { int a, b, k; } cs[maxn];
int cnt, num[maxn<<2], tp[maxn<<2];
LL ans;
int main() {
ns[0].mx[0] = ns[0].mx[1] = -oo;
ns[0].mn[0] = ns[0].mn[1] = oo;
ns[0].maxv = -oo;
n = read();
for(int i = 1; i <= n; i++) {
num[++cnt] = cs[i].a = read();
num[++cnt] = cs[i].a + 1;
num[++cnt] = cs[i].b = read() - 1;
num[++cnt] = cs[i].b + 1;
cs[i].k = read();
}
sort(num + 1, num + cnt + 1);
cnt = unique(num + 1, num + cnt + 1) - num;
// for(int i = 1; i <= cnt; i++) printf("%d ", num[i]); putchar('\n');
for(int i = 1; i <= n; i++) {
int x0 = lower_bound(num + 1, num + cnt + 1, cs[i].a) - num,
x1 = lower_bound(num + 1, num + cnt + 1, cs[i].b) - num;
ns[i].x[0] = x0; tp[x0] = 1;
ns[i].x[1] = x1; tp[x1] = 1;
ns[i].maxv = ns[i].val = cs[i].k;
}
for(int i = 1; i <= cnt; i++) if(!tp[i]) tp[i] = num[i+1] - num[i-1] - 1; // for(int i = 1; i <= n; i++) printf("%d: %d %d %d\n", i, ns[i].x[0], ns[i].x[1], ns[i].val);
build(root, 1, n, 0);
// for(int i = 1; i <= n; i++) printf("%d: %d %d %d\n", i, ns[i].x[0], ns[i].x[1], ns[i].val);
for(int i = 1; i <= cnt; i++) {
x.x[0] = x.x[1] = i;
int val = query(root);
// printf("%d: %d %d\n", i, val, tp[i]);
ans += (LL)tp[i] * (LL)val;
} printf("%lld\n", ans); return 0;
}