test.ts

//三种操作:
//构造 线段树
//OP1 某个节点+Sum Value 叶子节点加值
//OP2 Range 范围加值 从根节点 如果 Range 完全包含在当前Range之中  若Range 1个点则 直接加在叶子上 否则尽量加载中间节点上
class SegNode {
    left : SegNode = null
    right : SegNode = null
    allChild : SegNode[] = new Array<SegNode>()
    sum : number = 0
    start : number = 0 //[] 闭区间
    end : number = 0
    totalChildNum : number = 0
    nodeValue : number = 0
    parent : SegNode = null
    isLeaf : boolean = false
    sortId : number = 0
    cacheToChild : number = 0 //发送给区间所有孩子 每个Num
    cacheMid : number = 0
    GetMid():number{
        return this.cacheMid
    }
    InitMid() : void {
        this.cacheMid = Math.floor((this.start+this.end)/2)
    }
}
class LinkedNode<T>{
    data : T = null
    pre : LinkedNode<T> = null
    next : LinkedNode<T> = null
}
class StackInfo {
    node : SegNode = null
    childIndex : number = 0
}
class LinkedList<T> {
    head : LinkedNode<T> = null
    tail : LinkedNode<T> = null
    constructor(){
        this.head = new LinkedNode<T>()
        this.tail = this.head
    }
    IsEmpty(): boolean{
        return this.head == this.tail
    }
    PopFirst() : T{
        if(this.IsEmpty()) return null;
        let pop = this.head.next
        this.head.next = pop.next
        if(this.head.next == null) this.tail = this.head
        else this.head.next.pre = this.head
        return pop.data
    }
    First() : T{
        if(this.IsEmpty()) return null
        let pop = this.head.next
        return pop.data
    }
    Last() : T {
        if(this.IsEmpty()) return null
        let pop = this.tail
        return pop.data
    }
    PopLast(): T{
        if(this.IsEmpty()) return null
        let pop = this.tail
        this.tail = this.tail.pre
        this.tail.next = null
        return pop.data
    }
    Push(d : T){
        let n = new LinkedNode<T>()
        n.data = d
        n.pre = this.tail
        n.next = null
        this.tail.next = n
        this.tail = n
    }
}

class CheckInfo {
    startPos : number = 0
    endPos : number = 0
    node : SegNode = null
}
class AddInfo {
    node : SegNode = null
    num : number = 0
    startPos : number = 0
    endPos : number = 0

}
class SegTree {
    n : Number = 0
    leaderShip : number[][] = []
    operation : number[][] = []
    a : SegNode[] = []
    sortedTree : SegNode[] = []
    avaTree : SegNode = null
    avaArr : SegNode[] = []
    ret : number[] = []
    leafNodes : Map<number, SegNode> = new Map
    modV : number = 1e9+7
    InitTree() : void{
        for(let i = 0; i < this.n; i++) {
            var node = new SegNode()
            node.nodeValue = i+1
            this.a.push(node)
        }
        this.leaderShip.forEach(element => {
            let pn = this.a[element[0]-1]
            let cn = this.a[element[1]-1]
            cn.parent = pn
            pn.allChild.push(cn)
        });
        this.PreOrder(this.a[0])
    }

    PreOrder(n : SegNode){
        this.sortedTree.push(n)
        n.sortId = 0

        let openList = new LinkedList<StackInfo>()
        let si : StackInfo = {
            node : n,
            childIndex : 0
        }
        openList.Push(si)
        while(!openList.IsEmpty()){
            let f = openList.Last()
            if(f.childIndex < f.node.allChild.length){
                let cn = f.node.allChild[f.childIndex]
                cn.sortId = this.sortedTree.length
                this.sortedTree.push(cn)
                f.childIndex++
                let newSi : StackInfo = {
                    node : cn,
                    childIndex : 0,
                }
                openList.Push(newSi)
            }else {
                let last = openList.PopLast()
                last.node.allChild.forEach(ele => {
                    last.node.totalChildNum += ele.totalChildNum+1
                });
            }
        }

        for(let i = 0; i < this.sortedTree.length; i++){
            let node = this.sortedTree[i]
            node.start = i
            node.end = i+node.totalChildNum
        }

        let min = 0
        let max = this.sortedTree.length-1
        let oList = new LinkedList<SegNode>()
        var topNode = new SegNode()
        topNode.start = min
        topNode.end = max
        this.avaTree = topNode
        oList.Push(topNode)
        while(!oList.IsEmpty()) {
            let f = oList.PopFirst()
            f.InitMid()
            this.avaArr.push(f)
            f.GetMid()
            let min = f.start
            let max = f.end
            if(min < max) {
                let mid = Math.floor((min+max)/2)
                //[min, mid]
                //[mid+1, max]
                let leftNode = new SegNode()
                leftNode.start = min
                leftNode.end = mid
                f.left = leftNode
                leftNode.parent = f
                oList.Push(leftNode)

                let rightNode = new SegNode()
                rightNode.start = mid+1
                rightNode.end = max
                f.right = rightNode
                rightNode.parent = f
                oList.Push(rightNode)
            }else {
                f.isLeaf = true
                var nv = this.sortedTree[f.start].nodeValue
                this.leafNodes.set(nv, f)
            }
        }
    }
    Calc() : number[]{
        this.InitTree()
        // console.log(this.sortedTree)
        // console.log(this.avaArr)
        this.DoOp()
        // console.log("ResultIS")
        // console.log(this.avaArr)
        // console.log(this.ret)
        return this.ret
    }
    //向上每个parentRange + sum
    AddCoin(leafId : number, num : number){
        //排序数组中的节点
        let n = this.leafNodes.get(leafId)
        n.sum += num
        n.sum %= this.modV
        // console.log("AddCoin", n.start, n.end, n.sum)

        //平衡二叉树 向上每级+Sum
        var curPar = n.parent
        while(curPar != null){
            curPar.sum += num
            curPar.sum %= this.modV
            // console.log("AddCoin", curPar.start, curPar.end, curPar.sum)
            curPar = curPar.parent
        }
    }
    AddAll(maxNum : number, num : number) : void {
        // console.log("AddAll", maxNum, num)
        if(maxNum < 0) return
        let oldNum = num
        let startPos = 0
        let endPos = maxNum
        let topNode = this.avaTree
        //变为正数
        // num %= this.modV
        // num += this.modV
        // num %= this.modV
        // console.log("AddV", maxNum, num)

        var ai = new AddInfo()
        ai.node = topNode
        ai.num = num
        ai.startPos = 0
        ai.endPos = maxNum

        let openList = new LinkedList<AddInfo>()
        openList.Push(ai)
        while(!openList.IsEmpty()){
            let f = openList.PopFirst()
            let n = f.node
            let mid = n.GetMid()
            let add = (num * (f.endPos-f.startPos+1)) % this.modV
            n.sum += add
            n.sum %= this.modV
            // console.log("NADD", n.start, n.end, n.sum, add, f.startPos, f.endPos, n.cacheToChild)
            // console.log(f.startPos, f.endPos, mid, n.start, n.end)
            //没有重叠区间
            // if(f.endPos < n.start){
            //     continue
            // }
            //结束了
            if(f.endPos == n.end) {
                // if(oldNum < 0){
                n.cacheToChild += num 
                n.cacheToChild %= this.modV
                // }
            }
            else if(f.endPos <= mid) {
                let nai = new AddInfo()
                nai.node = n.left
                nai.startPos = f.startPos
                nai.endPos = f.endPos
                openList.Push(nai)
            }else { //左侧加值 CacheToChild 右侧+sum
                let len = n.left.end-n.left.start+1
                let add = (len * num) % this.modV
                n.left.sum += add
                n.left.sum %= this.modV
                //发送个孩子的 金币数量
                n.left.cacheToChild += num
                n.left.cacheToChild %= this.modV
                // console.log("CacheAdd", n.left.start, n.left.end, n.left.cacheToChild)

                let nai = new AddInfo()
                nai.startPos = mid+1
                nai.endPos = f.endPos
                nai.node = n.right
                openList.Push(nai)
            }
        }
        // console.log(this.avaArr)
    }
    AddRange2(topId : number, num : number) : void {
        let n = this.a[topId-1]
        let startPos = n.sortId
        let endPos = startPos+ n.totalChildNum 
        // console.log("AddRange2", startPos, endPos, num)
        this.AddAll(endPos, num)
        this.AddAll(startPos-1, -num)
    }
    //影响的Range部分值 只处理中间节点吗
    // AddRange(topId : number, num : number) {
    //     let n = this.a[topId-1]
    //     let startPos = n.sortId
    //     let endPos = startPos+ n.totalChildNum
    //     //整棵树增加的值 只向下扩展到刚好Range相等的区间 否则需要处理太多的线段
    //     // let addNum = (n.totalChildNum * num) % (1e9+7)
    //     let topNode = this.avaTree
    //     let openList = new LinkedList<CheckInfo>()
    //     let ci = new CheckInfo()
    //     ci.startPos = startPos
    //     ci.endPos = endPos
    //     ci.node = topNode
    //     openList.Push(ci)
    //     while(!openList.IsEmpty()){
    //         let f = openList.PopFirst()
    //         //Range == f Range
    //         //Range  < f Range  Split Left Right 
    //         //不需要再
    //         let n = f.node
    //         if(f.startPos == f.node.start && f.endPos == f.node.end){
    //             // f.node.sum += num //所有孩子 + num
    //             // if(n.isLeaf){ //最底层孩子节点
    //             //     n.sum += num
    //             //     n.sum %= this.modV
    //             // }else {//中间父亲节点
    //                 n.cacheToChild += num //每个孩子+num 不需要再处理孩子了
    //                 n.cacheToChild %= this.modV

    //                 let len = f.endPos-f.startPos+1
    //                 let add = (len * num) % this.modV
    //                 n.sum += add
    //                 n.sum %= this.modV
    //             // }
    //             //自身没有加num 属性
    //             //查询孩子的时候需要加上
    //         }else {
    //             let len = f.endPos-f.startPos+1
    //             let add = (len * num) % this.modV
    //             f.node.sum += add //这个Range所有的和
    //             f.node.sum %= this.modV
                
    //             let mid = Math.floor((n.start+n.end)/2)
    //             //[start, mid] [mid+1, end]
    //             if(f.startPos <= mid){
    //                 let newCi = new CheckInfo()
    //                 newCi.startPos = f.startPos
    //                 newCi.endPos = mid
    //                 newCi.node = n.left
    //                 openList.Push(newCi)
    //             }
    //             if(f.endPos >= (mid+1)){
    //                 let newCi = new CheckInfo()
    //                 newCi.startPos = mid+1
    //                 newCi.endPos = f.endPos
    //                 newCi.node = n.right
    //                 openList.Push(newCi)
    //             }
    //         }
    //     }
    // }
    //[0, xxx] 总和 求差值
    QueryPre(endNum : number) : number {
        // console.log("QueryPre", endNum)
        if(endNum < 0) return 0
        let topNode = this.avaTree
        let startPos = topNode.start
        let endPos = topNode.end
        // let mid = Math.floor((startPos+endPos)/2)
        let sum = 0
        let openList = new LinkedList<CheckInfo>()
        let ci = new CheckInfo()
        ci.startPos = 0
        ci.endPos = endNum
        ci.node = topNode
        openList.Push(ci)
        while(!openList.IsEmpty()) {
            let f = openList.PopFirst()
            let n = f.node
            let mid = n.GetMid()
            // if(f.endPos < n.start){
            //     continue
            // }
            // console.log("Pre", f.startPos, f.endPos, n.start, n.end, sum, n.sum, n.cacheToChild)
            if(f.endPos == n.end) {
                sum += n.sum
                sum %= this.modV
            }else if(f.endPos <= mid){//左侧中存储和
                let add = (n.cacheToChild * (f.endPos-f.startPos+1)) % this.modV
                sum += add
                sum %= this.modV
                let nci = new CheckInfo()
                nci.startPos = f.startPos
                nci.endPos = f.endPos
                nci.node = n.left
                openList.Push(nci)
            }else { //拆分两部分 左侧满和 右侧
                let add = (n.cacheToChild * (f.endPos-f.startPos+1)) % this.modV
                sum += add
                sum %= this.modV
                sum += n.left.sum
                sum %= this.modV

                let nci = new CheckInfo()
                nci.startPos = mid+1
                nci.endPos = f.endPos
                nci.node = n.right
                openList.Push(nci)
            }
        }
        // console.log("QueRet", endNum, sum)
        return sum
    }
    QueryAll(topId : number) : number {
        let n = this.a[topId-1]
        let startPos = n.sortId
        let endPos = startPos+ n.totalChildNum 
        // console.log("QueryAll", startPos, endPos)
        let num1 = this.QueryPre(endPos)
        let num2 = this.QueryPre(startPos-1)
        // console.log(num1, num2)
        let v = (num1 - num2 + this.modV) % this.modV
        this.ret.push(v)
        return v
    }
    // //查询范围 总和
    // Query(topId : number) {
    //     let n = this.a[topId-1]
    //     let startPos = n.sortId
    //     let endPos = startPos+ n.totalChildNum
    //     let openList = new LinkedList<CheckInfo>()
    //     let ci = new CheckInfo()
    //     ci.startPos = startPos
    //     ci.endPos = endPos
    //     ci.node = this.avaTree
    //     let sum = 0
    //     while(!openList.IsEmpty()) {
    //         let f = openList.First()
    //         let node = f.node
    //         if(f.startPos == node.start && f.endPos == node.end) {
    //             sum += node.sum //包含给孩子的了 但是自己父亲的没有
    //             sum %= this.modV
    //         }else {
    //             //该节点给自己所有孩子的公共和
    //             let len = node.end-node.start+1
    //             let add = (len * node.cacheToChild) % this.modV
    //             sum += add
    //             sum %= this.modV
    //             //拆分线段 寻找两部分和
    //             let mid = (node.start+node.end)/2
    //             if(f.startPos <= mid) {
    //                 var newCi = new CheckInfo()
    //                 newCi.startPos = f.startPos
    //                 newCi.endPos = f.endPos
    //                 newCi.node = node.left
    //                 openList.Push(newCi)
    //             }
    //             if(f.endPos >= (mid+1)){
    //                 var newCi = new CheckInfo()
    //                 newCi.startPos = mid+1
    //                 newCi.endPos = f.endPos
    //                 newCi.node = node.right
    //                 openList.Push(newCi)
    //             }
    //         }
    //     }
    //     this.ret.push(sum)
    // }
    DoOp():void{
        for(var i = 0; i < this.operation.length; i++){
            let element = this.operation[i]
            // if(i >= 11) {
            switch(element[0]){
                case 1:{
                    this.AddCoin(element[1], element[2])
                    break                    
                }
                case 2: {
                    this.AddRange2(element[1], element[2])
                    break
                }
                case 3: {
                    this.QueryAll(element[1])
                    break
                }
            }
            // }
            // console.log(i, this.ret, element)
            // if(i >= 34) return
        }
    }
}

var n = 6
var leadership = [[1, 2], [1, 6], [2, 3], [2, 5], [1, 4]]
var operations = [[1, 1, 500], [2, 2, 50], [3, 1], [2, 6, 15], [3, 1]]

import * as fs from 'fs'
import * as readLine from "readline"
import {performance} from "perf_hooks"

// var contents = fs.readFileSync("inputData.txt", "utf8")
// var lines = contents.split("\n")

var contents = fs.readFileSync("input3.txt", "utf8")
var lines = contents.split("\n")

var n = Number(lines[0])
var leadership = JSON.parse(lines[1]) as number[][]
var operations = JSON.parse(lines[2]) as number[][]

console.log("Num", n, leadership.length, operations.length)
let st = new SegTree()
st.n = n
st.leaderShip = leadership
st.operation = operations
st.Calc()

console.log(st.ret)