===
Index
algorithm
并行二分
给定n个初始为空的数组t1,…tn, 首先执行m次元素插入操作。 每次操作给定 l, r, v，在 t[l..r] 的数组中插入元素v。 最后执行q次查询操作。 每次操作给定 l, r, k, 输出将t[l..r]排序后的第k大数
- 1 <= n <= 1e9
- 1 <= m, q <= 1e5
- 1 <= l, r <= n
- 1 <= v <= 1e9
- 1 <= k <= 查询数组的元素总数
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2563
// Lazy seg
using S = pair<ll, int>;
using F = long long;
S op(S x, S y) {
S s;
s = S{x.first+y.first,x.second+y.second};
return s;
}
S e() {
return S();
};
S tag(F f, S s) { return S{s.first + f * s.second, s.second}; }
F merge(F x, F y) { return x + y; }
F id() { return 0; }
// Discrete
template<typename F, typename G, typename CHK>
vector<int> paral_bs(int n, int q, F &&init, G &&apply,CHK &&check){
vector<vector<int>> a(q);
vector<int> l(n, -1), r(n, q);
bool ok = 1;
while (ok) {
ok = 0;
init();
for (int i = 0; i < n; ++i) if (l[i] + 1 < r[i])
a[(l[i] + r[i]) >> 1].push_back(i);
for (int i = 0; i < q; ++i) {
ok |= !a[i].empty();
apply(i);
for (int j : a[i]) {
if (check(j)) r[j] = i;
else l[j] = i;
}
a[i].clear();
}
}
return r;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<int> a {0,1000000007};
vector<array<int ,3>> op1(m);
vector<array<int ,2>> op2(q);
vector<long long> qs(q);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < 3; ++j) {
cin >> op1[i][j];
}
op1[i][0]--;
a.push_back(op1[i][0]);
a.push_back(op1[i][1]);
}
sort(op1.begin(), op1.end(), [&](auto &x, auto &y){
return x[2] < y[2];
});
for (int i = 0; i < q; ++i) {
cin >> op2[i][0] >> op2[i][1] >> qs[i];
op2[i][0]--;
a.push_back(op2[i][0]);
a.push_back(op2[i][1]);
}
Discrete<int> v(a);
vector<S> vp(v.size() - 1);
for (int i = 0; i < v.size() - 1; ++i) {
vp[i] = S{0, v[i + 1] - v[i]};
}
LazySegTree<S, op, e, F, tag, merge, id> seg(vp.size());
for (int i = 0; i < m; ++i) {
op1[i][0] = v(op1[i][0]);
op1[i][1] = v(op1[i][1]);
}
for (int i = 0; i < q; ++i) {
op2[i][0] = v(op2[i][0]);
op2[i][1] = v(op2[i][1]);
}
auto init = [&](){
for(int i = 0;i < vp.size(); ++i){
seg.set(i, vp[i]);
}
};
auto apply = [&](int i){
seg.apply(op1[i][0], op1[i][1], 1);
};
auto chk = [&](int i){
return seg.get(op2[i][0], op2[i][1]).first >= qs[i];
};
auto ans=paral_bs(q, m, init, apply, chk);
for(int i = 0; i < q; i++)
cout << op1[ans[i]][2] << '\n';
return 0;
}
datastructure
最小绝对值和
函数f(x)，初始时 f(x)=0,q次查询
-
1 a b 更新 f(x) 为 f(x) = f(x) + x - a + b - 2 输出 使f(x)取最小值的x，以及对应的f(x)， 如果有多个，选最小的x。
可以证明，最小的x，总能在x为整数时取到，所以要求输出值为整数
- 1 <= q <= 2e5
- -1e9 <= a, b <= 1e9
template<typename T>
struct AbsSum{
multiset<T> lp, rp;
T s;
AbsSum() : s(0) {}
T insert(T x) {
if (lp.empty()) {
lp.insert(x), rp.insert(x);
return T(0);
}
auto p = interval();
lp.insert(x), rp.insert(x);
if (p.first <= x and x <= p.second) return T(0);
if (*lp.rbegin() > *rp.begin()) {
T a = *lp.rbegin(), b = *rp.begin();
lp.erase(lp.find(a));
rp.erase(rp.find(b));
rp.insert(a), lp.insert(b);
}
T res = min(abs(p.first - x), abs(p.second - x));
s += res;
return res;
}
T erase(T x) {
assert(lp.count(x) + rp.count(x) >= 2);
if (lp.count(x) and rp.count(x)) {
lp.erase(lp.find(x)), rp.erase(rp.find(x));
return T(0);
}
if (lp.count(x)) {
lp.erase(lp.find(x));
lp.erase(lp.find(x));
lp.insert(*rp.begin());
rp.erase(rp.begin());
} else {
rp.erase(rp.find(x));
rp.erase(rp.find(x));
rp.insert(*lp.rbegin());
lp.erase(prev(lp.end()));
}
auto p = interval();
if (p.first <= x and x <= p.second) return T(0);
T res = min(abs(p.first - x), abs(p.second - x));
s -= res;
return res;
}
pair<T, T> interval() {
assert(!lp.empty());
return make_pair(*lp.rbegin(), *rp.begin());
}
T val() {return s;}
};
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int q;
cin >> q;
AbsSum<ll> p;
long long s = 0;
for (int i = 0, t; i < q; ++i) {
cin >> t;
if (t == 1) {
long long x, y;
cin >> x >> y;
p.insert(x);
s += y;
} else {
cout << p.interval().first << " " << s + p.val() << '\n';
}
}
return 0;
}
前k大元素和
给定长度为3*N的数组a，需要从中删除N个元素，剩余2N个元素保持原有顺序不变，求剩余元素前N个元素和减去后N个元素和的最大值。
- 1 <= N <= 1e5
- 1 <= a[i] <= 1e9
PrioritySum
PrioritySum 数据结构维护维护多个元素的前k大(前k小)的元素之和。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <typename T, typename Com = less<T> , typename RCom = greater<T>>
struct PrioritySum {
PrioritySum() : PrioritySum(0) {}
PrioritySum(int k) : _k(k), sum(0){}
T query() const { return sum; }
void push(const T &v) { sum += v; in.push(v); fix();}
void erase(const T &v) {
if (in.size() and v == in.top()) { sum -= v; in.pop(); }
else if (in.size() and _rev_cmp(v, in.top())) { sum -= v; d_in.push(v);}
else d_out.push(v);
fix();
}
int get_k() const { return _k; }
void set_k(int new_k) { _k = new_k, fix(); }
int size() const { return int((in.size() + out.size()) - (d_in.size() + d_out.size())); }
private:
int _k;
T sum;
priority_queue<T, vector<T>, Com> in, d_in;
priority_queue<T, vector<T>, RCom> out, d_out;
void fix() {
while (int(in.size() - d_in.size()) < _k and out.size()) {
T v = move(out.top()); out.pop();
if (d_out.size() and d_out.top() == v) d_out.pop();
else { sum += v; in.push(move(v));}
}
while (int(in.size() - d_in.size()) > _k) {
T v = move(in.top()); in.pop();
if (d_in.size() and d_in.top() == v) d_in.pop();
else { sum -= v; out.push(move(v));}
}
}
};
template <typename T> using MaxSum = PrioritySum<T, greater<T>, less<T>>;
template <typename T> using MinSum = PrioritySum<T, less<T>, greater<T>>;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(3 * n);
for (int &x : a)
cin >> x;
MaxSum<ll> q1(n);
MinSum<ll> q2(n);
vector<long long> f(3 * n), g(3 * n);
for (int i = 0; i < 3 * n; ++i) {
if (i >= n) f[i] = q1.query();
q1.push(a[i]);
}
for (int i = 3 * n - 1; i >= 0; --i) {
q2.push(a[i]);
if (i <= 2 * n) g[i] = q2.query();
}
ll ans = -1e18;
for (int i = n; i <= 2 * n; ++i)
ans = max(ans, f[i] - g[i]);
cout << ans;
return 0;
}
离线矩形加矩形求和
有一个1e9*1e9的矩阵，初始元素全为0，首先进行n次操作接着执行q个查询，每次操作
x1 y1 x2 y2 w 对 [x1,x2]*[y1.y2]矩形内的所有元素执行a[i][j] += w。 每次查询给定
x1 y1 x2 y2 ，求矩形内的元素总和 模 998244353.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// FenwickTree
// Discrete
// mint
namespace internal::tuple_ops {
template <size_t N, typename F, typename ...Args>
tuple<Args...>& update(tuple<Args...>& lhs, F&& fun) {
if constexpr (N == tuple_size_v<tuple<Args...>>) return lhs;
else return fun(get<N>(lhs)), update<N + 1>(lhs, forward<F>(fun));
}
template <size_t N, typename F, typename ...Args>
tuple<Args...>& merge(tuple<Args...>& lhs, const tuple<Args...>& rhs, F&& fun) {
if constexpr (N == tuple_size_v<tuple<Args...>>) return lhs;
else return fun(get<N>(lhs), get<N>(rhs)), merge<N + 1>(lhs, rhs, forward<F>(fun));
}
}
template <typename ...Args>
tuple<Args...>& operator+=(tuple<Args...>& t1, const tuple<Args...>& t2) {
return internal::tuple_ops::merge<0>(t1, t2, [](auto& x, const auto& y) { x += y; });
}
template <typename ...Args>
tuple<Args...>& operator-=(tuple<Args...>& t1, const tuple<Args...>& t2) {
return internal::tuple_ops::merge<0>(t1, t2, [](auto& x, const auto& y) { x -= y; });
}
template <typename ...Args>
tuple<Args...> operator+(tuple<Args...> t1, const tuple<Args...>& t2) { return move(t1 += t2); }
template <typename ...Args>
tuple<Args...> operator-(tuple<Args...> t1, const tuple<Args...>& t2) { return move(t1 -= t2); }
template <typename V, typename ...Args>
tuple<Args...>& operator*=(tuple<Args...>& t1, const V& v) { return internal::tuple_ops::update<0>(t1, [&v](auto& x) { x *= v; }); }
template <typename V, typename ...Args>
tuple<Args...>& operator/=(tuple<Args...>& t1, const V& v) { return internal::tuple_ops::update<0>(t1, [&v](auto& x) { x /= v; }); }
template <typename V, typename ...Args>
tuple<Args...> operator*(const V& v, tuple<Args...> t1) { return move(t1 *= v); }
template <typename V, typename ...Args>
tuple<Args...> operator*(tuple<Args...> t1, const V& v) { return move(t1 *= v); }
template <typename V, typename ...Args>
tuple<Args...> operator/(tuple<Args...> t1, const V& v) { return move(t1 /= v); }
template <typename T>
struct StaticRectSum {
int q;
vector<tuple<int, int, T>> suf_querys;
vector<tuple<int, int, int, bool>> pre_sums;
vector<int> ys;
StaticRectSum() : q(0) {}
StaticRectSum(int n, int q) : q(q) { suf_querys.reserve(4 * n); pre_sums.reserve(4 * q); ys.reserve(2 * n);}
void add_sum(int x1, int y1, int x2, int y2, T val) {
ys.emplace_back(y1); ys.emplace_back(y2);
suf_querys.emplace_back(x1, y1, val), suf_querys.emplace_back(x2, y1, -val);
suf_querys.emplace_back(x1, y2, -val), suf_querys.emplace_back(x2, y2, val);
}
void add_query(int x1, int y1, int x2, int y2, int idx) {
pre_sums.emplace_back(x1, y1, idx, true), pre_sums.emplace_back(x2, y1, idx, false);
pre_sums.emplace_back(x1, y2, idx, false), pre_sums.emplace_back(x2, y2, idx, true);
}
vector<T> get() {
static constexpr auto x_comp = [](const auto& q1, const auto& q2) { return std::get<0>(q1) < std::get<0>(q2); };
sort(suf_querys.begin(), suf_querys.end(), x_comp);
sort(pre_sums.begin(), pre_sums.end(), x_comp);
Discrete<int> vd(ys);
FenwickTree<tuple<T, T, T, T>> ft(vd.size());
vector<T> res(q, T{ 0 });
int n = suf_querys.size(), m = pre_sums.size();
for (int i = 0, j = 0; i < n or j < m;) {
if (j == m or (i < n and x_comp(suf_querys[i], pre_sums[j]))) {
const auto& [l, d, v] = suf_querys[i++];
ft.add(vd(d),{ v, -v * d, -v * l, v * l * d });
} else {
const auto& [x, y, qid, is_add] = pre_sums[j++];
auto [a, b, c, d] = ft.sum(0, vd(y) - 1);
const T sum = a * x * y + b * x + c * y + d;
if (is_add) res[qid] += sum;
else res[qid] -= sum;
}
}
return res;
}
};
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, q;
cin >> n >> q;
StaticRectSum<mint> s(n, q);
for (int i = 0, x1, y1, x2, y2, w; i < n; ++i) {
cin >> x1 >> y1 >> x2 >> y2 >> w;
s.add_sum(x1, y1, x2, y2, w);
}
for (int i = 0, x1, y1, x2, y2; i < q; ++i) {
cin >> x1 >> y1 >> x2 >> y2;
s.add_query(x1, y1, x2, y2, i);
}
auto ans = s.get();
for (int i = 0; i < q; ++i) {
cout << ans[i] << "\n";
}
return 0;
}
带修改子数组不同元素数量和
给定数组a，f(l,r) 表示子数组a[l:r]中包含的不同元素数目，设所有子数组的f(l,r)之和为s，Q次修改，每次修改给定k,x,赋值a[k]=x,
输出每次修改操作后的s的值。
- 1 <= n, q <= 1e5
- 1 <= a[i], x <= 1e9
- 0 <= k < n
template <typename T>
struct DistinctArrSum {
int n;
vector<T> a;
long long ans;
map<T, set<int>> mp;
DistinctArrSum(int n) : n(n), a(n) {init();}
DistinctArrSum(vector<T> &b) {
n = b.size();
a = b;
init();
}
long long count(int x) const {
return 1ll * x * (x + 1) / 2;
}
void init() {
ans = 0;
for (int i = 0; i < n; ++i)
mp[a[i]].insert(i);
for (auto &[k, v] : mp) {
long long s = count(n);
int last = -1;
for (auto &x : v) {
if (last == -1) {
if (x > 0) s -= count(x);
} else s -= count(x - last - 1);
last = x;
}
if (last < n - 1) s -= count(n - 1 - last);
ans += s;
}
}
void del(int k) { // del a[k],0<=k<n
assert(k >= 0 && k < n && mp.count(a[k]));
std::set<int> &s = mp[a[k]];
if (s.size() == 1) {
mp.erase(a[k]);
ans -= count(n);
if (k > 0) ans += count(k);
if (k < n - 1) ans += count(n - 1 - k);
return;
}
auto it = s.lower_bound(k);
if (it == s.begin()) {
if (k > 0) ans += count(k);
int next_val = *next(it);
ans += count(next_val - k - 1) - count(next_val);
} else {
auto nxt = next(it);
int pre_val = *prev(it);
if (nxt == s.end()) {
if (k < n - 1) ans += count(n - 1 - k);
ans += count(k - pre_val - 1) - count(n - 1 - pre_val);
} else {
int next_val = *nxt;
ans += count(k - pre_val - 1) + count(next_val - k - 1) - count(next_val - pre_val - 1);
}
}
s.erase(k);
}
void add(int k, int x) { // mp[x] add index k
if (!mp.count(x)) {
mp[x].insert(k);
ans += count(n);
if (k > 0) ans -= count(k);
if (k < n - 1) ans -= count(n - 1 - k);
return;
}
auto &s = mp[x];
auto it = s.lower_bound(k);
if (it == s.begin()) {
int old_front = *it;
ans += count(old_front) - count(old_front - k - 1);
if (k > 0) ans -= count(k);
} else if (it == s.end()){
int pre_val = *prev(it);
ans += count(n - 1 - pre_val) - count(k - pre_val - 1);
if (k < n - 1) ans -= count(n - 1 - k);
} else {
int pre_val = *prev(it), next_val = *it;
ans += count(next_val - pre_val - 1) - count(k - pre_val - 1) - count(next_val - k - 1);
}
s.insert(k);
}
void upd(int k, T x) { // 0 <= k < n, set a[k] = x;
if (a[k] == x) return;
del(k);
add(k, x);
a[k] = x;
}
long long get() const { // total distinct number sum of all subarray
return ans;
}
};
void solve(int tt) {
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
DistinctArrSum<int> p(a);
cin >> q;
for (int i = 0; i < q; ++i) {
cin >> k >> x;
p.upd(k, x);
cout << p.get() << '\n';
}
}
区间与等差数列和
维护多次操作，每次操作给定 l, r a, d, 将区间[l,r]中的元素与以a为首项，d为公差的等差数列相加。
离线
先执行完所有操作，再查询每个位置对应元素。 可以用差分数组维护，时间复杂度 O(n)
template <typename T>
struct RangeGeoSum {
int n;
vector<T> d1, d2;
RangeGeoSum(int N) : n(N), d1(N), d2(N) {}
RangeGeoSum(vector<T> &A) : RangeGeoSum((int)A.size()) {
for (int i = 0; i < n; ++i) d2[i] = A[i];
}
void add(int l, int r, const T a1, const T &d) { //[l,r) 首项为a1,公差为d的等差数列
d1[l] += d;
d2[l] += a1 - d * l;
if (r < n) {
d1[r] -= d;
d2[r] -= a1 - d * l;
}
}
vector<T> get() {
vector<T> ret(n);
for (int i = 0; i < n; ++i) {
ret[i] = d1[i] * i + d2[i];
if (i < n - 1) {
d1[i + 1] += d1[i];
d2[i + 1] += d2[i];
}
}
return ret;
}
};
使用方法
- 定义数据结构
RangeGeoSum<ll> f(n);
- 对区间[l, r-1]，元素与以a为首项，d为公差的等差数列相加
f.add(l, r, a, d);
- 获取最终操作后的数组
auto d = f.get();
例题
| 给定一个排列p,可以将p进行循环移位， 求 | p1-1 | + | p2-2 | +…+ | pn-n | 的最小值。 |
- 1 <= n <= 1e6
分析
考虑每个数的贡献，其在小于自身的位置 x时，其对结果的贡献为 p[i]-x，否则，在大于自身的位置时，其对结果的贡献为 x-p[i]。 而其位置的变化是从 i逐次增大变为n，再从 1出发不断增大变为 i - 1，即整体除了一点外是连续的变化。每一段都是一个区间与一个等差数列求和的形式。
int main() {
int n;
cin >> n;
vector<int> p(n);
for (int i = 0; i < n; ++i) {
cin >> p[i];
p[i]--;
}
RangeGeoSum<ll> f(n);
for (int i = 0; i < n; ++i) {
if (p[i] > i) {
f.add(0, p[i] - i + 1, p[i] - i, -1);
int r = min(n, p[i] - i + n - p[i]);
if (p[i] - i + 1 < r) {
f.add(p[i] - i + 1, r, 1, 1);
}
if (r < n) {
f.add(r, n, p[i], -1);
}
} else {
f.add(0, n - i, i - p[i], 1);
int r = min(n - i + p[i] + 1, n);
if (n - i < r) {
f.add(n - i, r, p[i], -1);
}
if (r < n) {
f.add(r, n, 1, 1);
}
}
}
long long mn = 1e18;
int id = -1;
auto d = f.get();
for (int i = 0; i < n; ++i) {
if (d[i] < mn) {
mn = d[i];
id = i;
}
}
cout << mn << ' ' << id << '\n';
return 0;
}
在线
边操作，边访问某个下标处的元素，这是可以使用树状数组 rangeAddTree 维护区间加和，可以 log(n) 时间内访问下标处的元素。
string
runenumerate
长度为n的字符串s，输出字符串s的所有runs, 输出 [t, l, r]的数组。 表示s的子串[l,..r-1] 是最大的以t为最小长度的周期串，且 len(s) >= 2t, 例如 abcabca 是以abc为周期的串。
- 1 <= s <= 2e5
// z_function
struct Run {
int period;
int l, r;
Run() = default;
Run(int period, int l, int r) : period(period), l(l), r(r) {}
friend bool operator<(const Run& r1, const Run& r2) {
return r1.period != r2.period ? r1.period < r2.period : r1.l != r2.l ? r1.l < r2.l : r1.r < r2.r;
}
friend bool operator>(const Run& r1, const Run& r2) { return r2 < r1; }
friend bool operator<=(const Run& r1, const Run& r2) { return not (r2 < r1); }
friend bool operator>=(const Run& r1, const Run& r2) { return not (r1 < r2); }
friend bool operator==(const Run& r1, const Run& r2) { return r1.period == r2.period and r1.l == r2.l and r1.r == r2.r; }
friend bool operator!=(const Run& r1, const Run& r2) { return not (r1 == r2); }
};
template <typename Container, typename = void_t<typename Container::value_type>>
vector<Run> run_enum(Container& s, typename Container::value_type sentinel = numeric_limits<typename Container::value_type>::min()) {
for (auto& e : s) assert(e != sentinel);
using T = typename Container::value_type;
vector<Run> glob_result;
auto div_conq = [&](auto div_conq, int l, int r) -> vector<Run> {
if (r - l <= 1) return {};
const int m = (l + r) >> 1;
vector<Run> run_l = div_conq(div_conq, l, m), run_r = div_conq(div_conq, m, r);
string rl;
copy(begin(s) + m, begin(s) + r, back_inserter(rl));
rl.push_back(sentinel);
copy(begin(s) + l, begin(s) + m, back_inserter(rl));
vector<int> z_rl = z_function(rl);
reverse(begin(rl), end(rl));
vector<int> z_rl_rev = z_function(rl);
const int siz = rl.size();
vector<Run> result;
auto add_ans = [&](Run&& run) { (run.l == l or run.r == r ? result : glob_result).emplace_back(move(run)); };
const int len_l = m - l, len_r = r - m;
vector<Run> run_m(len_r / 2 + 1);
for (auto& run : run_r) {
if (run.l != m) {
add_ans(move(run));
continue;
}
run_m[run.period] = move(run);
}
for (auto& run : run_l) {
if (run.r != m) {
add_ans(move(run));
continue;
}
const int period = run.period;
if (z_rl[siz - period] == period) {
if (run_m[period].period) {
run.r = run_m[period].r;
run_m[period] = Run{};
add_ans(move(run));
} else {
run.r = m + period + z_rl[period];
add_ans(move(run));
}
} else {
run.r = m + z_rl[siz - period];
add_ans(move(run));
}
}
for (auto& run : run_m) if (run.period) {
const int period = run.period;
if (z_rl[siz - period] == period) {
if (2 * period <= len_l and z_rl[siz - 2 * period] >= period) continue;
run.l = m - period - z_rl_rev[period];
add_ans(move(run));
} else {
run.l = m - z_rl_rev[siz - period];
add_ans(move(run));
}
}
for (int period = 1; period <= len_l; ++period) {
bool skip_r = 2 * period <= len_r and z_rl[period] >= period;
bool skip_l = 2 * period <= len_l and z_rl[siz - 2 * period] >= period;
if (z_rl[siz - period] == period) {
if (skip_l or skip_r) continue;
const int beg_pos = m - period - z_rl_rev[period];
const int end_pos = m + period + z_rl[period];
add_ans(Run{ period, beg_pos, end_pos });
} else {
if (not skip_r) {
const int beg_pos = m - z_rl_rev[siz - period];
const int end_pos = m + period + z_rl[period];
if (end_pos - beg_pos >= 2 * period) {
add_ans(Run{ period, beg_pos, end_pos });
}
}
if (not skip_l) {
const int beg_pos = m - period - z_rl_rev[period];
const int end_pos = m + z_rl[siz - period];
if (end_pos - beg_pos >= 2 * period) {
add_ans(Run{ period, beg_pos, end_pos });
}
}
}
}
return result;
};
const int n = s.size();
vector<tuple<int, int, int>> runs;
for (Run& run : div_conq(div_conq, 0, n)) {
runs.emplace_back(run.l, run.r, run.period);
}
for (Run& run : glob_result) {
runs.emplace_back(run.l, run.r, run.period);
}
sort(begin(runs), end(runs));
runs.erase(
unique(
begin(runs), end(runs),
[](auto& r1, auto& r2) {
return get<0>(r1) == get<0>(r2) and get<1>(r1) == get<1>(r2);
}
), end(runs)
);
vector<Run> res;
for (auto& [l, r, t] : runs) res.emplace_back(t, l, r);
return res;
}
