#include "garden.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>
#include <map>
typedef long long llong;
const int MAXN = 300000 + 10;
const llong INF = 1e18;
const int INTINF = 2e9;
int n, q;
struct SegmentTree
{
struct Node
{
int min;
int max;
int max2;
int cntMIN;
int cntMAX;
llong sum;
int lazy;
Node()
{
lazy = INTINF;
}
void assign(int val, int len)
{
min = max = val;
max2 = -INTINF;
cntMIN = cntMAX = len;
sum = 1LL * val * len;
}
};
Node tree[4*MAXN];
Node combine(Node left, Node right)
{
if (left.sum == -1)
{
return right;
}
Node res;
res.sum = left.sum + right.sum;
if (left.min == right.min)
{
res.min = left.min;
res.cntMIN = left.cntMIN + right.cntMIN;
} else
{
if (left.min > right.min)
{
std::swap(left, right);
}
res.min = left.min;
res.cntMIN = left.cntMIN;
}
if (left.max == right.max)
{
res.max = left.max;
res.cntMAX = left.cntMAX + right.cntMAX;
res.max2 = std::max(left.max2, right.max2);
} else
{
if (left.max < right.max)
{
std::swap(left, right);
}
res.max = left.max;
res.cntMAX = left.cntMAX;
res.max2 = std::max(left.max2, right.max);
}
return res;
}
void build(int l, int r, int node, int a[])
{
if (l == r)
{
tree[node].assign(a[l], 1);
return;
}
int mid = (l + r) / 2;
build(l, mid, 2*node, a);
build(mid + 1, r, 2*node + 1, a);
tree[node] = combine(tree[2*node], tree[2*node + 1]);
}
void push(int node, int l, int r)
{
if (tree[node].lazy == INTINF)
{
return;
}
if (tree[node].max <= tree[node].lazy)
{
tree[node].lazy = INTINF;
return;
}
if (tree[node].min >= tree[node].lazy)
{
tree[node].assign(tree[node].lazy, r - l + 1);
} else if (tree[node].max2 < tree[node].lazy)
{
tree[node].sum -= 1LL * tree[node].cntMAX * (tree[node].max - tree[node].lazy);
tree[node].max = tree[node].lazy;
}
if (l < r)
{
tree[2*node].lazy = std::min(tree[2*node].lazy, tree[node].lazy);
tree[2*node + 1].lazy = std::min(tree[2*node + 1].lazy, tree[node].lazy);
}
tree[node].lazy = INTINF;
}
llong query(int l, int r, int node, int queryL, int queryR, int k)
{
if (queryR < l || r < queryL)
{
return 0;
}
int mid = (l + r) / 2;
if (!(queryL <= l && r <= queryR))
{
return query(l, mid, 2*node, queryL, queryR, k) + query(mid + 1, r, 2*node + 1, queryL, queryR, k);
}
push(node, l, r);
if (tree[node].max <= k)
{
return 0;
}
if (tree[node].min >= k)
{
return tree[node].sum - 1LL * (r - l + 1) * k;
}
if (tree[node].max2 < k)
{
return 1LL * tree[node].cntMAX * (tree[node].max - k);
}
return query(l, mid, 2*node, queryL, queryR, k) + query(mid + 1, r, 2*node + 1, queryL, queryR, k);
}
void update(int l, int r, int node, int queryL, int queryR, int k)
{
push(node, l, r);
if (queryR < l || r < queryL)
{
return;
}
int mid = (l + r) / 2;
if (!(queryL <= l && r <= queryR))
{
update(l, mid, 2*node, queryL, queryR, k);
update(mid + 1, r, 2*node + 1, queryL, queryR, k);
tree[node] = combine(tree[2*node], tree[2*node + 1]);
return;
}
if (tree[node].max <= k)
{
return;
}
if (tree[node].min >= k || tree[node].max2 < k)
{
tree[node].lazy = k;
} else
{
update(l, mid, 2*node, queryL, queryR, k);
update(mid + 1, r, 2*node + 1, queryL, queryR, k);
tree[node] = combine(tree[2*node], tree[2*node + 1]);
return;
}
push(node, l, r);
}
Node queryNode(int l, int r, int node, int queryL, int queryR)
{
// std::cout << "query Node: " << node << ' ' << l << ' ' << r << ' ' << queryL << ' ' << queryR << '\n';
push(node, l, r);
if(queryL <= l && r <= queryR)
{
return tree[node];
}
Node res; res.sum = -1;
int mid = (l + r) / 2;
if (queryL <= mid) res = combine(res, queryNode(l, mid, 2*node, queryL, queryR));
if (mid + 1 <= queryR) res = combine(res, queryNode(mid + 1, r, 2*node + 1, queryL, queryR));
return res;
}
void pointUpdate(int l, int r, int node, int queryPos, int queryVal)
{
push(node, l, r);
if (queryPos < l || r < queryPos)
{
return;
}
if (l == r)
{
tree[node].assign(queryVal, 1);
return;
}
int mid = (l + r) / 2;
pointUpdate(l, mid, 2*node, queryPos, queryVal);
pointUpdate(mid + 1, r, 2*node + 1, queryPos, queryVal);
tree[node] = combine(tree[2*node], tree[2*node + 1]);
}
void build(int a[])
{
build(1, n, 1, a);
}
llong query(int l, int r, int k)
{
return query(1, n, 1, l, r, k);
}
void update(int l, int r, int k)
{
update(1, n, 1, l, r, k);
}
Node nodeQuery(int l, int r)
{
return queryNode(1, n, 1, l, r);
}
int cntMAX(int l, int r)
{
return queryNode(1, n, 1, l, r).cntMAX;
}
llong sumQuery(int l, int r)
{
return queryNode(1, n, 1, l, r).sum;
}
void pointUpdate(int pos, int val)
{
pointUpdate(1, n, 1, pos, val);
}
};
SegmentTree tree;
void initialise(int N, int Q, int h[])
{
n = N;
q = Q;
tree.build(h);
}
void cut(int l, int r, int k)
{
int valL = -1, valR = tree.nodeQuery(l, r).max + 1, mid;
if (k >= 2)
{
while (valL < valR - 1)
{
mid = (valL + valR) / 2;
if (tree.query(l, r, mid) > k) valL = mid;
else valR = mid;
}
k -= tree.query(l, r, valR);
tree.update(l, r, valR);
} else
{
valR = tree.nodeQuery(l, r).max;
}
if (k > 0 && valR > 0)
{
int posL = l - 1, posR = r;
while (posL < posR - 1)
{
mid = (posL + posR) / 2;
SegmentTree::Node res = tree.nodeQuery(l, mid);
if (res.max < valR || res.cntMAX < k) posL = mid;
else posR = mid;
}
tree.update(l, posR, valR - 1);
}
}
void magic(int i, int x)
{
tree.pointUpdate(i, x);
}
llong inspect(int l, int r)
{
return tree.sumQuery(l, r);
}
Compilation message
weirdtree.cpp:1:10: fatal error: garden.h: No such file or directory
1 | #include "garden.h"
| ^~~~~~~~~~
compilation terminated.
