結果

問題 No.2338 Range AtCoder Query
コンテスト
ユーザー 草苺奶昔
提出日時 2024-07-30 02:43:52
言語 Go
(1.23.4)
結果
AC  
実行時間 702 ms / 4,000 ms
コード長 7,402 bytes
コンパイル時間 19,774 ms
コンパイル使用メモリ 240,080 KB
実行使用メモリ 30,800 KB
最終ジャッジ日時 2024-07-30 02:44:32
合計ジャッジ時間 40,178 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 矩形区间修改单点查询(离线)

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func demo() {
	e := func() int32 { return 0 }
	op := func(a, b int32) int32 { return a + b }
	inv := func(a int32) int32 { return -a }
	ps := NewRectangleAddPointSumOffline(e, op, inv, false)
	ps.AddRectangle(0, 2, 0, 2, 1)
	ps.AddRectangle(1, 3, 1, 3, 2)
	ps.AddQuery(1, 1)
	ps.AddQuery(2, 2)
	ps.AddQuery(3, 3)
	res := ps.Calc()
	for _, v := range res {
		fmt.Println(v)
	}
}

func main() {
	yuki2338()
}

// No.2338 Range AtCoder Query
// https://yukicoder.me/problems/no/2338
// 给定长度为n的提交记录，每一项记录形如(pid, status)，表示问题编号和提交状态(AC/WA)。
// 再给定q个查询，每个查询形如(l, r)，表示查询区间[l, r)内的AC数和WA数。
// !AC数：通过的题目数量(每道题最多一次AC)。
// !WA数：第一次AC之前的提交次数。
//
// 对于每一个wa的记录，这个wa对查询[l,r)有贡献的条件为:
// 1. l之前没有ac，r之前有ac。
func yuki2338() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, m, q int32
	fmt.Fscan(in, &n, &m, &q)
	pids := make([]int32, n)
	status := make([]bool, n)
	for i := int32(0); i < n; i++ {
		fmt.Fscan(in, &pids[i])
		pids[i]--
		var tmp string
		fmt.Fscan(in, &tmp)
		status[i] = tmp == "AC"
	}

	groups := make([][]int32, m)
	for i, v := range pids {
		groups[v] = append(groups[v], int32(i))
	}

	e := func() int32 { return 0 }
	op := func(a, b int32) int32 { return a + b }
	inv := func(a int32) int32 { return -a }
	ac := NewRectangleAddPointSumOffline(e, op, inv, true)
	wa := NewRectangleAddPointSumOffline(e, op, inv, true)

	for _, group := range groups {
		len_ := int32(len(group))
		prev := make([]int32, len_) // pre[i]: i之前的第一个AC
		for i := int32(0); i < len_; i++ {
			prev[i] = -1
		}
		for i, v := range group {
			if i > 0 {
				prev[i] = prev[i-1]
			}
			if status[v] {
				prev[i] = v
			}
		}

		nextAc := n
		for i := len_ - 1; i >= 0; i-- {
			index := group[i]
			if status[index] { // AC
				ac.AddRectangle(0, index+1, index+1, nextAc+1, 1)
				nextAc = index
			} else { // WA
				a, b := prev[i], nextAc
				if b == n {
					continue
				}
				wa.AddRectangle(a+1, index+1, b+1, n+1, 1)
			}
		}
	}

	for i := int32(0); i < q; i++ {
		var l, r int32
		fmt.Fscan(in, &l, &r)
		l--
		ac.AddQuery(l, r)
		wa.AddQuery(l, r)
	}

	res1, res2 := ac.Calc(), wa.Calc()
	for i := int32(0); i < q; i++ {
		fmt.Fprintln(out, res1[i], res2[i])
	}
}

const INF32 int32 = 1e9 + 10

type rect[E any] struct {
	y, x1, x2 int32
	w         E
}

type point struct {
	id   int32
	x, y int32
}

type RectangleAddPointSumOffline[E any] struct {
	smallX bool
	rects  []rect[E]
	points []point
	e      func() E
	op     func(e1, e2 E) E
	inv    func(e E) E
}

func NewRectangleAddPointSumOffline[E any](
	e func() E, op func(e1, e2 E) E, inv func(e E) E,
	smallX bool,
) *RectangleAddPointSumOffline[E] {
	return &RectangleAddPointSumOffline[E]{smallX: smallX, e: e, op: op, inv: inv}
}

func (ps *RectangleAddPointSumOffline[E]) AddRectangle(xl, xr, yl, yr int32, w E) {
	ps.rects = append(ps.rects, rect[E]{y: yl, x1: xl, x2: xr, w: w})
	ps.rects = append(ps.rects, rect[E]{y: yr, x1: xr, x2: xl, w: w})
}

func (ps *RectangleAddPointSumOffline[E]) AddQuery(x, y int32) {
	ps.points = append(ps.points, point{id: int32(len(ps.points)), x: x, y: y})
}

func (ps *RectangleAddPointSumOffline[E]) Calc() []E {
	n, q := int32(len(ps.rects)), int32(len(ps.points))
	if n == 0 || q == 0 {
		res := make([]E, q)
		for i := int32(0); i < q; i++ {
			res[i] = ps.e()
		}
		return res
	}

	rects, points := ps.rects, ps.points
	// compress x
	nx := int32(0)
	if !ps.smallX {
		sort.Slice(points, func(i, j int) bool { return points[i].x < points[j].x })
		keyX := make([]int32, 0, q)
		for i := int32(0); i < q; i++ {
			x := points[i].x
			if len(keyX) == 0 || keyX[len(keyX)-1] != x {
				keyX = append(keyX, x)
			}
			points[i].x = int32(len(keyX) - 1)
		}
		for i := int32(0); i < n; i++ {
			rects[i].x1 = lowerBound32(keyX, rects[i].x1)
			rects[i].x2 = lowerBound32(keyX, rects[i].x2)
		}
		nx = int32(len(keyX))
	} else {
		mx := INF32
		for i := int32(0); i < q; i++ {
			if tmp := points[i].x; tmp < mx {
				mx = tmp
			}
		}
		for i := int32(0); i < q; i++ {
			points[i].x -= mx
			if tmp := points[i].x + 1; tmp > nx {
				nx = tmp
			}
		}
		for i := int32(0); i < n; i++ {
			rects[i].x1 = clamp32(rects[i].x1-mx, 0, nx)
			rects[i].x2 = clamp32(rects[i].x2-mx, 0, nx)
		}
	}

	sort.Slice(points, func(i, j int) bool { return points[i].y < points[j].y })
	sort.Slice(rects, func(i, j int) bool { return rects[i].y < rects[j].y })

	bit := newFenwickTree(ps.e, ps.op, ps.inv)
	bit.Build(nx, func(i int32) E { return ps.e() })
	res := make([]E, q)
	for i := range res {
		res[i] = ps.e()
	}
	j := int32(0)
	for _, point := range points {
		q, x, y := point.id, point.x, point.y
		for j < n && rects[j].y <= y {
			rect := rects[j]
			j++
			bit.Update(rect.x1, rect.w)
			bit.Update(rect.x2, ps.inv(rect.w))
		}
		res[q] = bit.QueryPrefix(x + 1)
	}
	return res
}

type fenwickTree[E any] struct {
	n     int32
	total E
	data  []E
	e     func() E
	op    func(e1, e2 E) E
	inv   func(e E) E
}

func newFenwickTree[E any](e func() E, op func(e1, e2 E) E, inv func(e E) E) *fenwickTree[E] {
	return &fenwickTree[E]{e: e, op: op, inv: inv}
}

func (fw *fenwickTree[E]) Build(n int32, f func(i int32) E) {
	data := make([]E, n)
	for i := int32(0); i < n; i++ {
		data[i] = f(i)
	}
	for i := int32(1); i <= n; i++ {
		if j := i + (i & -i); j <= n {
			data[j-1] = fw.op(data[i-1], data[j-1])
		}
	}
	fw.n = n
	fw.data = data
	fw.total = fw.QueryPrefix(n)
}

func (fw *fenwickTree[E]) QueryAll() E { return fw.total }

// [0, end)
func (fw *fenwickTree[E]) QueryPrefix(end int32) E {
	if end > fw.n {
		end = fw.n
	}
	res := fw.e()
	for ; end > 0; end &= end - 1 {
		res = fw.op(res, fw.data[end-1])
	}
	return res
}

// [start, end)
func (fw *fenwickTree[E]) QueryRange(start, end int32) E {
	if start < 0 {
		start = 0
	}
	if end > fw.n {
		end = fw.n
	}
	if start > end {
		return fw.e()
	}
	if start == 0 {
		return fw.QueryPrefix(end)
	}
	pos, neg := fw.e(), fw.e()
	for end > start {
		pos = fw.op(pos, fw.data[end-1])
		end &= end - 1
	}
	for start > end {
		neg = fw.op(neg, fw.data[start-1])
		start &= start - 1
	}
	return fw.op(pos, fw.inv(neg))
}

// 要求op满足交换律(commute).
func (fw *fenwickTree[E]) Update(i int32, x E) {
	fw.total = fw.op(fw.total, x)
	for i++; i <= fw.n; i += i & -i {
		fw.data[i-1] = fw.op(fw.data[i-1], x)
	}
}

func (fw *fenwickTree[E]) GetAll() []E {
	res := make([]E, fw.n)
	for i := int32(0); i < fw.n; i++ {
		res[i] = fw.QueryRange(i, i+1)
	}
	return res
}

func lowerBound32(nums []int32, x int32) int32 {
	left, right := int32(0), int32(len(nums)-1)
	for left <= right {
		mid := (left + right) >> 1
		if nums[mid] < x {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return left
}

func clamp32(x, l, r int32) int32 {
	if x < l {
		return l
	}
	if x > r {
		return r
	}
	return x
}

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 min32(a, b int32) int32 {
	if a < b {
		return a
	}
	return b
}

func max32(a, b int32) int32 {
	if a > b {
		return a
	}
	return b
}
0