package main
import ( "fmt" "math/rand" "sort" "time")
func getMax(a, b int) int { if a > b { return a } return b}
func getAns1(m int, records [][]int, queries []int) []int { maxT := 0 for _, r := range records { maxT = getMax(maxT, getMax(r[1], r[2])) } for _, t := range queries { maxT = getMax(maxT, t) }
stores := make([][]int, m+1) for i := range stores { stores[i] = make([]int, maxT+1) }
for _, record := range records { s := record[0] l := record[1] r := record[2] - 1 for i := l; i <= r; i++ { stores[s][i]++ } }
k := len(queries) ans := make([]int, k) for i := 0; i < k; i++ { curAns := 0 for j := 1; j <= m; j++ { if stores[j][queries[i]] >= 3 { curAns++ } } ans[i] = curAns }
return ans}
func getAns2(m int, records [][]int, queries []int) []int { n := len(records) k := len(queries) tn := (n << 1) + k times := make([]int, tn+1) ti := 1 for _, record := range records { times[ti] = record[1] ti++ times[ti] = record[2] - 1 ti++ } for _, query := range queries { times[ti] = query ti++ } sort.Ints(times) for _, record := range records { record[1] = rank(times, record[1]) record[2] = rank(times, record[2]-1) } for i := 0; i < k; i++ { queries[i] = rank(times, queries[i]) } sort.Slice(records, func(i, j int) bool { return records[i][0] < records[j][0] }) st := NewSegmentTree(tn) for l := 0; l < n; { r := l for r < n && records[l][0] == records[r][0] { r++ } countRange(records, l, r-1, st) l = r } ans := make([]int, k) for i := 0; i < k; i++ { ans[i] = st.query(queries[i]) } return ans}
// type Record struct {// Garage int// Start int// End int// }
type SegmentTree struct { Tn int Sum []int Lazy []int}
func NewSegmentTree(n int) *SegmentTree { tn := n sum := make([]int, (tn+1)<<2) lazy := make([]int, (tn+1)<<2) return &SegmentTree{Tn: tn, Sum: sum, Lazy: lazy}}
func (st *SegmentTree) pushUp(rt int) { st.Sum[rt] = st.Sum[rt<<1] + st.Sum[rt<<1|1]}
func (st *SegmentTree) pushDown(rt, ln, rn int) { if st.Lazy[rt] != 0 { st.Lazy[rt<<1] += st.Lazy[rt] st.Sum[rt<<1] += st.Lazy[rt] * ln st.Lazy[rt<<1|1] += st.Lazy[rt] st.Sum[rt<<1|1] += st.Lazy[rt] * rn st.Lazy[rt] = 0 }}
func (st *SegmentTree) add(l, r int) { st.add0(l, r, 1, st.Tn, 1)}
func (st *SegmentTree) add0(L, R, l, r, rt int) { if L <= l && r <= R { st.Sum[rt] += r - l + 1 st.Lazy[rt] += 1 return } mid := (l + r) >> 1 st.pushDown(rt, mid-l+1, r-mid) if L <= mid { st.add0(L, R, l, mid, rt<<1) } if R > mid { st.add0(L, R, mid+1, r, rt<<1|1) } st.pushUp(rt)}
func (st *SegmentTree) query(index int) int { return st.query0(index, 1, st.Tn, 1)}
func (st *SegmentTree) query0(index, l, r, rt int) int { if l == r { return st.Sum[rt] } m := (l + r) >> 1 st.pushDown(rt, m-l+1, r-m) if index <= m { return st.query0(index, l, m, rt<<1) } else { return st.query0(index, m+1, r, rt<<1|1) }}
func rank(sorted []int, v int) int { l := 1 r := len(sorted) ans := 0 m := 0 for l <= r { m = (l + r) / 2 // fmt.Println(len(sorted), l, r, m, v) if sorted[m] >= v { ans = m r = m - 1 } else { l = m + 1 } } return ans}
func countRange(records [][]int, l, r int, st *SegmentTree) { n := r - l + 1 help := make([][2]int, n<<1) size := 0 for i := l; i <= r; i++ { if records[i][1] <= records[i][2] { help[size][0] = records[i][1] help[size][1] = 1 size++ help[size][0] = records[i][2] help[size][1] = -1 size++ } } sort.Slice(help[:size], func(i, j int) bool { if help[i][0] != help[j][0] { return help[i][0] < help[j][0] } else { return help[j][1] < help[i][1] } }) count := 0 start := -1 for i := 0; i < size; i++ { point := help[i][0] status := help[i][1] if status == 1 { count++ if count >= 3 { if start == -1 { start = point } } } else { if start != -1 && start <= point { st.add(start, point) } count-- if count >= 3 { start = point + 1 } else { start = -1 } } }}
// 为了测试func randomRecords(n, m, t int) [][]int { records := make([][]int, n) for i := 0; i < n; i++ { records[i] = make([]int, 3) } for i := 0; i < n; i++ { records[i][0] = rand.Intn(m) + 1 a := rand.Intn(t) + 1 b := rand.Intn(t) + 1 records[i][1] = min(a, b) records[i][2] = max(a, b) } return records}
// 为了测试func randomQueries(k, t int) []int { queries := make([]int, k) for i := 0; i < k; i++ { queries[i] = rand.Intn(t) + 1 } return queries}
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}
func same(ans1, ans2 []int) bool { if len(ans1) != len(ans2) { return false } for i := 0; i < len(ans1); i++ { if ans1[i] != ans2[i] { return false } } return true}
func main() { M := 20 N := 300 K := 500 T := 5000 testTimes := 5000 fmt.Println("功能测试开始") rand.Seed(time.Now().UnixNano()) for i := 0; i < testTimes; i++ { m := rand.Intn(M) + 1 n := rand.Intn(N) + 1 k := rand.Intn(K) + 1 t := rand.Intn(T) + 1 records := randomRecords(n, m, t) queries := randomQueries(k, t) ans1 := getAns1(m, records, queries) ans2 := getAns2(m, records, queries) if !same(ans1, ans2) { fmt.Println("出错了!") return } } fmt.Println("功能测试结束")
fmt.Println("性能测试开始") m := 100000 n := 100000 k := 100000 t := 1000000000 records := randomRecords(n, m, t) queries := randomQueries(k, t) fmt.Println("车库规模 : ", m) fmt.Println("记录规模 : ", n) fmt.Println("查询条数 : ", k) fmt.Println("时间范围 : ", t) start := time.Now() getAns2(m, records, queries) end := time.Now() fmt.Println("运行时间 : ", end.Sub(start).Milliseconds(), " 毫秒") fmt.Println("性能测试结束")}
评论