結果
| 問題 | No.1216 灯籠流し/Lanterns |
| ユーザー |
 草苺奶昔
|
| 提出日時 | 2023-03-25 02:34:46 |
| 言語 | Go (1.22.1) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 22,160 bytes |
| コンパイル時間 | 12,881 ms |
| コンパイル使用メモリ | 220,700 KB |
| 実行使用メモリ | 41,728 KB |
| 最終ジャッジ日時 | 2023-10-18 21:55:04 |
| 合計ジャッジ時間 | 31,894 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,348 KB |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | AC | 98 ms
18,644 KB |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | AC | 137 ms
33,076 KB |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
| testcase_40 | WA | - |
| testcase_41 | WA | - |
| testcase_42 | WA | - |
| testcase_43 | WA | - |
| testcase_44 | WA | - |
| testcase_45 | WA | - |
| testcase_46 | WA | - |
| testcase_47 | WA | - |
| testcase_48 | WA | - |
| testcase_49 | WA | - |
ソースコード
package main
import (
"bufio"
"fmt"
"math/bits"
"os"
"sort"
)
// void solve() {
// LL(N, Q);
// Graph<ll, 0> G(N);
// G.read_tree(1);
// Tree<decltype(G)> tree(G);
// vi dat(N - 1);
// FOR(i, N - 1) dat[i] = G.edges[i].cost;
// Static_Tree_Monoid<decltype(tree), Monoid_Add<ll>, 1> TM(tree, dat);
// auto& dist = tree.depth_weighted;
// /*
// ・頂点 v に、根に着くのが時刻 t であるようなものを追加
// ・（消す）はじめて消えて到達するのが w であるとき、w に -1 個追加
// euler tour をとって
// */
// using T = tuple<int, int, ll>;
// vc<T> query;
// auto& LID = tree.LID;
// vi X, Y;
// iota(all(X), 0);
// FOR(Q) {
// LL(tp, v, t, l);
// --v;
// if (tp == 0) {
// // 追加クエリ
// // 消えないで到達できる最大の頂点
// auto check = [&](auto e) -> bool { return e <= l; };
// auto to = TM.max_path(check, v, 0);
// int w = tree.parent[to];
// query.eb(1, LID[v], t + dist[v]);
// X.eb(LID[v]);
// Y.eb(t + dist[v]);
// if (w != -1) {
// X.eb(LID[w]);
// Y.eb(t + dist[v]);
// query.eb(-1, LID[w], t + dist[v]);
// }
// }
// if (tp == 1) { query.eb(0, v, t); }
// }
// FenwickTree_2D<Monoid_Add<int>, ll, true> bit(X, Y);
// for (auto&& [tp, x, t]: query) {
// if (tp == 0) {
// int v = x;
// int l = tree.LID[v], r = tree.RID[v];
// t += dist[v];
// ll ANS = bit.sum(l, r, 0, t + 1);
// print(ANS);
// }
// if (tp == 1) { bit.add(x, t, 1); }
// if (tp == -1) { bit.add(x, t, -1); }
// }
// }
func main() {
// 放花灯
// https://yukicoder.me/problems/no/1216
// Paken River 拥有 n 个“检查点”，每个检查点被编号为 1 到 n。
// 检查点 i 和检查点 j 直接连接，灯笼将沿着河流从 i 到 j，用时间 t 流动。
// 河流具有树形结构，其节点是检查点，其根是出口。
// 检查点 1 是 Paken River 的出口，河流从这里流入。
// 灯笼被流动到某个检查点后，它将沿着河流顺流而下，一段时间后将关闭。
// 回答以下 q 个查询。
// !0:添加查询：在时间 t 将灯笼从检查点 i 流到河流上。灯笼在 alive 秒后消失。
// !1:回答查询：在检查点 i，输出在时刻 t 之前亮起并可见的灯笼的总数(子树里灯笼树)。 包括在时刻 t 正好可见、刚开始流动、刚好在到达时关闭的灯笼。
// n<=5e4,q<=1e5
// 1<=i<=n,0<=t<=1e12,0<=alive<=1e12
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n, q int
fmt.Fscan(in, &n, &q)
tree := NewTree(n)
for i := 0; i < n-1; i++ {
var a, b, c int
fmt.Fscan(in, &a, &b, &c)
a--
b--
tree.AddEdge(a, b, c)
}
tree.Build(0)
edgeW := make([]int, n-1)
for i := 0; i < n-1; i++ {
edgeW[i] = tree.edges[i][2] // weight
}
S := NewStaticTreeMonoid(tree, edgeW, false)
dist := tree.DepthWeighted
lid := tree.LID
query := make([][3]int, 0, q)
for i := 0; i < q; i++ {
var op int
fmt.Fscan(in, &op)
if op == 0 {
var pos, startTime, alive int
fmt.Fscan(in, &pos, &startTime, &alive)
pos--
check := func(e int) bool { return e <= alive } // 不消失可以达到的最远点
to := S.MaxPath(check, pos, 0)
p := tree.Parent[to]
query = append(query, [3]int{1, lid[pos], startTime + dist[pos]}) // 灯笼开始流动
if p != -1 { // 还没进入河流就消失了,在p处减一个灯笼
query = append(query, [3]int{-1, lid[p], startTime + dist[pos]})
}
} else {
var pos, endTime, null int
fmt.Fscan(in, &pos, &endTime, &null)
pos--
query = append(query, [3]int{0, pos, endTime}) // 查询在pos处,<=endTime前可以看到的灯笼
}
}
R := NewStaticPointAddRectangleSum(q, q)
// fmt.Fprintln(out, query)
for _, q := range query {
op, pos, time := q[0], q[1], q[2]
if op == 0 {
l, r := lid[pos], tree.RID[pos]
time += dist[pos]
// fmt.Fprintln(out, op, pos, time, l, r, time+1)
R.AddQuery(l, r, 0, time+1)
} else if op == 1 {
R.AddPoint(pos, time, 1)
} else {
R.AddPoint(pos, time, -1)
}
}
res := R.Work()
for _, v := range res {
fmt.Fprintln(out, v)
}
}
const INF int = 1e18
type E = int
const IS_COMMUTATIVE = true // 幺半群是否满足交换律
func e() E { return 0 }
func op(e1, e2 E) E { return e1 + e2 }
type StaticTreeMonoid struct {
tree *Tree
n int
unit E
isVertex bool
seg *DisjointSparseTable
segR *DisjointSparseTable
}
// data: 顶点的值, 或者边的值.(边的编号为两个定点中较深的那个点的编号)
// isVertex: data是否为顶点的值以及查询的时候是否是顶点权值.
func NewStaticTreeMonoid(tree *Tree, data []E, isVertex bool) *StaticTreeMonoid {
n := len(tree.Tree)
res := &StaticTreeMonoid{tree: tree, n: n, unit: e(), isVertex: isVertex}
leaves := make([]E, n)
if isVertex {
for v := range leaves {
leaves[tree.LID[v]] = data[v]
}
} else {
for i := range leaves {
leaves[i] = res.unit
}
for e := 0; e < n-1; e++ {
v := tree.EidtoV(e)
leaves[tree.LID[v]] = data[e]
}
}
res.seg = NewDisjointSparse(leaves, e, op)
if !IS_COMMUTATIVE {
res.segR = NewDisjointSparse(leaves, e, func(e1, e2 E) E { return op(e2, e1) }) // opRev
}
return res
}
// 查询 start 到 target 的路径上的值.(点权/边权 由 isVertex 决定)
func (st *StaticTreeMonoid) QueryPath(start, target int) E {
path := st.tree.GetPathDecomposition(start, target, st.isVertex)
val := st.unit
for _, ab := range path {
a, b := ab[0], ab[1]
var x E
if a <= b {
x = st.seg.Query(a, b+1)
} else if IS_COMMUTATIVE {
x = st.seg.Query(b, a+1)
} else {
x = st.segR.Query(b, a+1)
}
val = op(val, x)
}
return val
}
// 找到路径上最后一个 x 使得 QueryPath(start,x) 满足check函数.不存在返回-1.
func (st *StaticTreeMonoid) MaxPath(check func(E) bool, start, target int) int {
if !st.isVertex {
return st._maxPathEdge(check, start, target)
}
if !check(st.QueryPath(start, start)) {
return -1
}
path := st.tree.GetPathDecomposition(start, target, st.isVertex)
val := st.unit
for _, ab := range path {
a, b := ab[0], ab[1]
var x E
if a <= b {
x = st.seg.Query(a, b+1)
} else if IS_COMMUTATIVE {
x = st.seg.Query(b, a+1)
} else {
x = st.segR.Query(b, a+1)
}
if tmp := op(val, x); check(tmp) {
val = tmp
start = st.tree.idToNode[b]
continue
}
checkTmp := func(x E) bool {
return check(op(val, x))
}
if a <= b {
i := st.seg.MaxRight(a, checkTmp)
if i == a {
return start
}
return st.tree.idToNode[i-1]
} else {
var i E
if IS_COMMUTATIVE {
i = st.seg.MinLeft(a+1, checkTmp)
} else {
i = st.segR.MinLeft(a+1, checkTmp)
}
if i == a+1 {
return start
}
if st.isVertex {
return st.tree.idToNode[i]
}
return st.tree.Parent[st.tree.idToNode[i]]
}
}
return target
}
func (st *StaticTreeMonoid) QuerySubtree(root int) E {
l, r := st.tree.LID[root], st.tree.RID[root]
offset := 1
if st.isVertex {
offset = 0
}
return st.seg.Query(l+offset, r)
}
func (st *StaticTreeMonoid) _maxPathEdge(check func(E) bool, u, v int) int {
lca := st.tree.LCA(u, v)
path := st.tree.GetPathDecomposition(u, lca, st.isVertex)
val := st.unit
// climb
for _, ab := range path {
a, b := ab[0], ab[1]
var x E
if IS_COMMUTATIVE {
x = st.seg.Query(b, a+1)
} else {
x = st.segR.Query(b, a+1)
}
if tmp := op(val, x); check(tmp) {
val = tmp
u = st.tree.Parent[st.tree.idToNode[b]]
continue
}
checkTmp := func(x E) bool {
return check(op(val, x))
}
var i E
if IS_COMMUTATIVE {
i = st.seg.MinLeft(a+1, checkTmp)
} else {
i = st.segR.MinLeft(a+1, checkTmp)
}
if i == a+1 {
return u
}
return st.tree.Parent[st.tree.idToNode[i]]
}
// down
path = st.tree.GetPathDecomposition(lca, v, st.isVertex)
for _, ab := range path {
a, b := ab[0], ab[1]
x := st.seg.Query(a, b+1)
if tmp := op(val, x); check(tmp) {
val = tmp
u = st.tree.idToNode[b]
continue
}
checkTmp := func(x E) bool {
return check(op(val, x))
}
i := st.seg.MaxRight(a, checkTmp)
if i == a {
return u
}
return st.tree.idToNode[i-1]
}
return v
}
type Tree struct {
Tree [][][2]int // (next, weight)
Depth, DepthWeighted []int
Parent []int
LID, RID []int // 欧拉序[in,out)
idToNode []int
top, heavySon []int
edges [][3]int
timer int
}
func NewTree(n int) *Tree {
tree := make([][][2]int, n)
lid := make([]int, n)
rid := make([]int, n)
idToNode := make([]int, n)
top := make([]int, n) // 所处轻/重链的顶点（深度最小），轻链的顶点为自身
depth := make([]int, n) // 深度
depthWeighted := make([]int, n)
parent := make([]int, n) // 父结点
heavySon := make([]int, n) // 重儿子
edges := make([][3]int, 0, n-1)
for i := range parent {
parent[i] = -1
}
return &Tree{
Tree: tree,
Depth: depth,
DepthWeighted: depthWeighted,
Parent: parent,
LID: lid,
RID: rid,
idToNode: idToNode,
top: top,
heavySon: heavySon,
edges: edges,
}
}
// 添加无向边 u-v, 边权为w.
func (tree *Tree) AddEdge(u, v, w int) {
tree.Tree[u] = append(tree.Tree[u], [2]int{v, w})
tree.Tree[v] = append(tree.Tree[v], [2]int{u, w})
tree.edges = append(tree.edges, [3]int{u, v, w})
}
// 添加有向边 u->v, 边权为w.
func (tree *Tree) AddDirectedEdge(u, v, w int) {
tree.Tree[u] = append(tree.Tree[u], [2]int{v, w})
tree.edges = append(tree.edges, [3]int{u, v, w})
}
// root:0-based
// 当root设为-1时，会从0开始遍历未访问过的连通分量
func (tree *Tree) Build(root int) {
if root != -1 {
tree.build(root, -1, 0, 0)
tree.markTop(root, root)
} else {
for i := 0; i < len(tree.Tree); i++ {
if tree.Parent[i] == -1 {
tree.build(i, -1, 0, 0)
tree.markTop(i, i)
}
}
}
}
// 返回 root 的欧拉序区间, 左闭右开, 0-indexed.
func (tree *Tree) Id(root int) (int, int) {
return tree.LID[root], tree.RID[root]
}
// 返回边 u-v 对应的 欧拉序起点编号, 0-indexed.
func (tree *Tree) Eid(u, v int) int {
if tree.LID[u] > tree.LID[v] {
return tree.LID[u]
}
return tree.LID[v]
}
// 较深的那个点作为边的编号.
func (tree *Tree) EidtoV(eid int) int {
e := tree.edges[eid]
from, to := e[0], e[1]
if tree.Parent[from] == to {
return from
}
return to
}
func (tree *Tree) LCA(u, v int) int {
for {
if tree.LID[u] > tree.LID[v] {
u, v = v, u
}
if tree.top[u] == tree.top[v] {
return u
}
v = tree.Parent[tree.top[v]]
}
}
func (tree *Tree) Dist(u, v int, weighted bool) int {
if weighted {
return tree.DepthWeighted[u] + tree.DepthWeighted[v] - 2*tree.DepthWeighted[tree.LCA(u, v)]
}
return tree.Depth[u] + tree.Depth[v] - 2*tree.Depth[tree.LCA(u, v)]
}
// k: 0-based
// 如果不存在第k个祖先，返回-1
func (tree *Tree) KthAncestor(root, k int) int {
if k > tree.Depth[root] {
return -1
}
for {
u := tree.top[root]
if tree.LID[root]-k >= tree.LID[u] {
return tree.idToNode[tree.LID[root]-k]
}
k -= tree.LID[root] - tree.LID[u] + 1
root = tree.Parent[u]
}
}
// 从 from 节点跳向 to 节点,跳过 step 个节点(0-indexed)
// 返回跳到的节点,如果不存在这样的节点,返回-1
func (tree *Tree) Jump(from, to, step int) int {
if step == 1 {
if from == to {
return -1
}
if tree.IsInSubtree(to, from) {
return tree.KthAncestor(to, tree.Depth[to]-tree.Depth[from]-1)
}
return tree.Parent[from]
}
c := tree.LCA(from, to)
dac := tree.Depth[from] - tree.Depth[c]
dbc := tree.Depth[to] - tree.Depth[c]
if step > dac+dbc {
return -1
}
if step <= dac {
return tree.KthAncestor(from, step)
}
return tree.KthAncestor(to, dac+dbc-step)
}
func (tree *Tree) CollectChild(root int) []int {
res := []int{}
for _, e := range tree.Tree[root] {
next := e[0]
if next != tree.Parent[root] {
res = append(res, next)
}
}
return res
}
// 返回沿着`路径顺序`的 [起点,终点] 的 欧拉序 `左闭右闭` 数组.
// !eg:[[2 0] [4 4]] 沿着路径顺序但不一定沿着欧拉序.
func (tree *Tree) GetPathDecomposition(u, v int, vertex bool) [][2]int {
up, down := [][2]int{}, [][2]int{}
for {
if tree.top[u] == tree.top[v] {
break
}
if tree.LID[u] < tree.LID[v] {
down = append(down, [2]int{tree.LID[tree.top[v]], tree.LID[v]})
v = tree.Parent[tree.top[v]]
} else {
up = append(up, [2]int{tree.LID[u], tree.LID[tree.top[u]]})
u = tree.Parent[tree.top[u]]
}
}
edgeInt := 1
if vertex {
edgeInt = 0
}
if tree.LID[u] < tree.LID[v] {
down = append(down, [2]int{tree.LID[u] + edgeInt, tree.LID[v]})
} else if tree.LID[v]+edgeInt <= tree.LID[u] {
up = append(up, [2]int{tree.LID[u], tree.LID[v] + edgeInt})
}
for i := 0; i < len(down)/2; i++ {
down[i], down[len(down)-1-i] = down[len(down)-1-i], down[i]
}
return append(up, down...)
}
func (tree *Tree) GetPath(u, v int) []int {
res := []int{}
composition := tree.GetPathDecomposition(u, v, true)
for _, e := range composition {
a, b := e[0], e[1]
if a <= b {
for i := a; i <= b; i++ {
res = append(res, tree.idToNode[i])
}
} else {
for i := a; i >= b; i-- {
res = append(res, tree.idToNode[i])
}
}
}
return res
}
func (tree *Tree) SubtreeSize(u int) int {
return tree.RID[u] - tree.LID[u]
}
// child 是否在 root 的子树中 (child和root不能相等)
func (tree *Tree) IsInSubtree(child, root int) bool {
return tree.LID[root] <= tree.LID[child] && tree.LID[child] < tree.RID[root]
}
func (tree *Tree) ELID(u int) int {
return 2*tree.LID[u] - tree.Depth[u]
}
func (tree *Tree) ERID(u int) int {
return 2*tree.RID[u] - tree.Depth[u] - 1
}
func (tree *Tree) build(cur, pre, dep, dist int) int {
subSize, heavySize, heavySon := 1, 0, -1
for _, e := range tree.Tree[cur] {
next, weight := e[0], e[1]
if next != pre {
nextSize := tree.build(next, cur, dep+1, dist+weight)
subSize += nextSize
if nextSize > heavySize {
heavySize, heavySon = nextSize, next
}
}
}
tree.Depth[cur] = dep
tree.DepthWeighted[cur] = dist
tree.heavySon[cur] = heavySon
tree.Parent[cur] = pre
return subSize
}
func (tree *Tree) markTop(cur, top int) {
tree.top[cur] = top
tree.LID[cur] = tree.timer
tree.idToNode[tree.timer] = cur
tree.timer++
if tree.heavySon[cur] != -1 {
tree.markTop(tree.heavySon[cur], top)
for _, e := range tree.Tree[cur] {
next := e[0]
if next != tree.heavySon[cur] && next != tree.Parent[cur] {
tree.markTop(next, next)
}
}
}
tree.RID[cur] = tree.timer
}
//
//
type DisjointSparseTable struct {
n, log int
data [][]E
unit E
op func(E, E) E
}
// DisjointSparseTable 支持幺半群的区间静态查询.
// eg: 区间乘积取模/区间仿射变换...
func NewDisjointSparse(leaves []E, e func() E, op func(E, E) E) *DisjointSparseTable {
res := &DisjointSparseTable{}
n := len(leaves)
log := 1
for (1 << log) < n {
log++
}
data := make([][]E, log)
data[0] = append(data[0], leaves...)
for i := 1; i < log; i++ {
data[i] = append(data[i], data[0]...)
v := data[i]
b := 1 << i
for m := b; m <= n; m += 2 * b {
l, r := m-b, min(m+b, n)
for j := m - 1; j >= l+1; j-- {
v[j-1] = op(v[j-1], v[j])
}
for j := m; j < r-1; j++ {
v[j+1] = op(v[j], v[j+1])
}
}
}
res.n = n
res.log = log
res.data = data
res.unit = e()
res.op = op
return res
}
func (ds *DisjointSparseTable) Query(start, end int) E {
if start == end {
return ds.unit
}
end--
if start == end {
return ds.data[0][start]
}
k := 31 - bits.LeadingZeros32(uint32(start^end))
return ds.op(ds.data[k][start], ds.data[k][end])
}
// 返回最大的 right 使得 [left,right) 内的值满足 check.
func (ds *DisjointSparseTable) MaxRight(left int, check func(e E) bool) int {
if left == ds.n {
return ds.n
}
ok, ng := left, ds.n+1
for ok+1 < ng {
mid := (ok + ng) >> 1
if check(ds.Query(left, mid)) {
ok = mid
} else {
ng = mid
}
}
return ok
}
// 返回最小的 left 使得 [left,right) 内的值满足 check.
func (ds *DisjointSparseTable) MinLeft(right int, check func(e E) bool) int {
if right == 0 {
return 0
}
ok, ng := right, -1
for ng+1 < ok {
mid := (ok + ng) >> 1
if check(ds.Query(mid, right)) {
ok = mid
} else {
ng = mid
}
}
return ok
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
type Point struct{ x, y, w int }
type Query struct{ l, d, r, u int }
type DynamicPointAddRectangleSum struct {
queries []interface{} // Point or Query
}
// 根据总点数初始化容量.
func NewPointAddRectangleSum(n int) *DynamicPointAddRectangleSum {
return &DynamicPointAddRectangleSum{queries: make([]interface{}, 0, n)}
}
// 在(x,y)点上添加w权重.
func (dpars *DynamicPointAddRectangleSum) AddPoint(x, y, w int) {
dpars.queries = append(dpars.queries, Point{x, y, w})
}
// 添加查询为区间 [x1, x2) * [y1, y2) 的权重和.
func (dpars *DynamicPointAddRectangleSum) AddQuery(x1, x2, y1, y2 int) {
dpars.queries = append(dpars.queries, Query{x1, y1, x2, y2})
}
// 按照添加顺序返回所有查询结果..
func (dpars *DynamicPointAddRectangleSum) Work() []int {
q := len(dpars.queries)
rev := make([]int, q)
sz := 0
for i := 0; i < q; i++ {
if _, ok := dpars.queries[i].(Query); ok { // holds_alternative
rev[i] = sz
sz++
}
}
res := make([]int, sz)
rangeQ := [][]int{{0, q}}
for len(rangeQ) > 0 {
l, r := rangeQ[0][0], rangeQ[0][1]
rangeQ = rangeQ[1:]
m := (l + r) >> 1
solver := NewStaticPointAddRectangleSum(0, 0)
for k := l; k < m; k++ {
if p, ok := dpars.queries[k].(Point); ok {
solver.AddPoint(p.x, p.y, p.w)
}
}
for k := m; k < r; k++ {
if q, ok := dpars.queries[k].(Query); ok {
solver.AddQuery(q.l, q.r, q.d, q.u)
}
}
sub := solver.Work()
for k, t := m, 0; k < r; k++ {
if _, ok := dpars.queries[k].(Query); ok {
res[rev[k]] += sub[t]
t++
}
}
if l+1 < m {
rangeQ = append(rangeQ, []int{l, m})
}
if m+1 < r {
rangeQ = append(rangeQ, []int{m, r})
}
}
return res
}
type StaticPointAddRectangleSum struct {
points []Point
queries []Query
}
// 指定点集和查询个数初始化容量.
func NewStaticPointAddRectangleSum(n, q int) *StaticPointAddRectangleSum {
return &StaticPointAddRectangleSum{
points: make([]Point, 0, n),
queries: make([]Query, 0, q),
}
}
// 在(x,y)点上添加w权重.
func (sp *StaticPointAddRectangleSum) AddPoint(x, y, w int) {
sp.points = append(sp.points, Point{x: x, y: y, w: w})
}
// 添加查询为区间 [x1, x2) * [y1, y2) 的权重和.
func (sp *StaticPointAddRectangleSum) AddQuery(x1, x2, y1, y2 int) {
sp.queries = append(sp.queries, Query{l: x1, r: x2, d: y1, u: y2})
}
// 按照添加顺序返回所有查询结果..
func (sp *StaticPointAddRectangleSum) Work() []int {
n := len(sp.points)
q := len(sp.queries)
res := make([]int, q)
if n == 0 || q == 0 {
return res
}
sort.Slice(sp.points, func(i, j int) bool { return sp.points[i].y < sp.points[j].y })
ys := make([]int, 0, n)
for i := range sp.points {
if len(ys) == 0 || ys[len(ys)-1] != sp.points[i].y {
ys = append(ys, sp.points[i].y)
}
sp.points[i].y = len(ys) - 1
}
type Q struct {
x int
d, u int
t bool
idx int
}
qs := make([]Q, 0, q+q)
for i := 0; i < q; i++ {
query := sp.queries[i]
d := sort.SearchInts(ys, query.d)
u := sort.SearchInts(ys, query.u)
qs = append(qs, Q{x: query.l, d: d, u: u, t: false, idx: i}, Q{x: query.r, d: d, u: u, t: true, idx: i})
}
sort.Slice(sp.points, func(i, j int) bool { return sp.points[i].x < sp.points[j].x })
sort.Slice(qs, func(i, j int) bool { return qs[i].x < qs[j].x })
j := 0
bit := newBinaryIndexedTree(len(ys))
for i := range qs {
for j < n && sp.points[j].x < qs[i].x {
bit.Apply(sp.points[j].y, sp.points[j].w)
j++
}
if qs[i].t {
res[qs[i].idx] += bit.ProdRange(qs[i].d, qs[i].u)
} else {
res[qs[i].idx] -= bit.ProdRange(qs[i].d, qs[i].u)
}
}
return res
}
type binaryIndexedTree struct {
n int
log int
data []int
}
// 長さ n の 0で初期化された配列で構築する.
func newBinaryIndexedTree(n int) *binaryIndexedTree {
return &binaryIndexedTree{n: n, log: bits.Len(uint(n)), data: make([]int, n+1)}
}
// 配列で構築する.
func newBinaryIndexedTreeFrom(arr []int) *binaryIndexedTree {
res := newBinaryIndexedTree(len(arr))
res.build(arr)
return res
}
// 要素 i に値 v を加える.
func (b *binaryIndexedTree) Apply(i int, v int) {
for i++; i <= b.n; i += i & -i {
b.data[i] += v
}
}
// [0, r) の要素の総和を求める.
func (b *binaryIndexedTree) Prod(r int) int {
res := int(0)
for ; r > 0; r -= r & -r {
res += b.data[r]
}
return res
}
// [l, r) の要素の総和を求める.
func (b *binaryIndexedTree) ProdRange(l, r int) int {
return b.Prod(r) - b.Prod(l)
}
// 区間[0,k]の総和がx以上となる最小のkを求める.数列が単調増加であることを要求する.
func (b *binaryIndexedTree) LowerBound(x int) int {
i := 0
for k := 1 << b.log; k > 0; k >>= 1 {
if i+k <= b.n && b.data[i+k] < x {
x -= b.data[i+k]
i += k
}
}
return i
}
// 区間[0,k]の総和がxを上回る最小のkを求める.数列が単調増加であることを要求する.
func (b *binaryIndexedTree) UpperBound(x int) int {
i := 0
for k := 1 << b.log; k > 0; k >>= 1 {
if i+k <= b.n && b.data[i+k] <= x {
x -= b.data[i+k]
i += k
}
}
return i
}
func (b *binaryIndexedTree) build(arr []int) {
if b.n != len(arr) {
panic("len of arr is not equal to n")
}
for i := 1; i <= b.n; i++ {
b.data[i] = arr[i-1]
}
for i := 1; i <= b.n; i++ {
j := i + (i & -i)
if j <= b.n {
b.data[j] += b.data[i]
}
}
}