Created
December 14, 2019 11:41
-
-
Save liyonghelpme/37e8398bc909194a824458b5afd23bb2 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //三种操作: | |
| //构造 线段树 | |
| //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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment