Skip to content

Instantly share code, notes, and snippets.

@liyonghelpme
Created December 14, 2019 11:41
Show Gist options
  • Save liyonghelpme/37e8398bc909194a824458b5afd23bb2 to your computer and use it in GitHub Desktop.
Save liyonghelpme/37e8398bc909194a824458b5afd23bb2 to your computer and use it in GitHub Desktop.
//三种操作:
//构造 线段树
//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