Atcoder abc127

C
遍历，根据每个线段最左和最右不断“缩小”，最终得到答案
D
在原始牌和新牌中挑出N张最大，重新组成数组
排序后双指针
E
x y分开计算
任取一对点$x_1,x_2$，记d为两个点的x差值，剩下可以随意取k-2个点，每一个组合都在整体的cost中贡献d
取$d$从1…n-1进行统计，每个点对有m*m个取法
$$\therefore cost=\left(\genfrac{}{}{0ex}{}{k-2}{n\ast m-2}\right)\ast m^2\ast \sum _{d=1}^{n-1}(d\ast (n-d))$$
组合数用逆元计算
F
绝对值加法，动态维护中位数
用两个堆
注意在python中a.append(x)会破坏a的堆性质
之后再使用heapq.heappush(a,x)是不会维护前面的数据的
我喜欢维护大堆长度+1>=小堆长度>=大堆长度

# -*- coding: utf-8 -*-
# @time     : 2023/6/2 13:30
# @author   : yhdu@tongwoo.cn
# @desc     :
# @file     : atcoder.py
# @software : PyCharm
import bisect
import copy
import sys
from collections import defaultdict, Counter, deque
from functools import lru_cache, cmp_to_key
import heapq
import math
sys.setrecursionlimit(100010)


def main():
    items = sys.version.split()
    if items[0] == '3.10.6':
        fp = open("in.txt")
    else:
        fp = sys.stdin

    n = int(fp.readline())
    ls, rs = 0, 0
    l, r = [], []
    ans = 0
    for i in range(n):
        items = list(map(int, fp.readline().split()))
        if items[0] == 1:
            a, b = items[1:]
            ans += b
            if len(r) == 0:
                heapq.heappush(l, -a)
                ls += a
            else:
                topl, topr = -l[0], r[0]
                if a < topl:
                    heapq.heappush(l, -a)
                    ls += a
                elif a > topr:
                    heapq.heappush(r, a)
                    rs += a
                else:
                    heapq.heappush(l, -a)
                    ls += a
            if len(l) - len(r) > 1:
                tl = -l[0]
                heapq.heappop(l)
                heapq.heappush(r, tl)
                ls -= tl
                rs += tl
            elif len(r) > len(l):
                tr = r[0]
                heapq.heappop(r)
                heapq.heappush(l, -tr)
                rs -= tr
                ls += tr
        if items[0] == 2:
            if len(l) == 0:
                print(-l[0], ans)
            else:
                print(-l[0], ans + (-l[0]) * len(l) - ls + rs - (-l[0] * len(r)))


if __name__ == "__main__":
    main()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68