T3

差分没过，删除的时候前缀和没过，但是树状数组过了。事实上应该插入的时候前缀和，然后记录删除下标相减。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import sys
input = sys.stdin.readline
Q = int(input())
N = int(3e5+6)
sums = 0
sz = 0
deled = 0
s = [0] * N
for _ in range(Q):
    tmp = input().split()
    op = int(tmp[0])
    if op == 1:
        l = int(tmp[1])
        sums += l
        sz += 1
        s[sz] = sums
    elif op == 2:
        deled += 1
    else:
        k = int(tmp[1])
        print(s[deled + k - 1] - s[deled])

T4

没想到两边乘4，变成整数。

分类：

  1. 上下左右，这个显而易见是4*(R-1) + 1
  2. 四个区间，也是显而易见的对称，重点是如何求这个区间的。

我感觉二分是不是也能过如果数据弱的话（

使用双指针的思想，x从小到大，y从最大的r-1一直变小，对于x和y的遍历是O(n)的。（很易证，x + y < balabala，小的x大的y不满足，大的x大的y更不满足，y只能更小）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def valid(x, y, r):
    return (2*x+1)**2 + (2*y+1)**2 <= 4*r**2

r = int(input())
ans = 4 * (r - 1) + 1
x = 1
y = r - 1
part2 = 0
while valid(x, 1, r):
    while not valid(x, y, r):
        y -= 1
    part2 += y
    x += 1
ans += 4 * part2
print(ans)

E

 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

import sys 
input = sys.stdin.readline
n, m = map(int, input().split())
p = list(map(int, input().split()))


def check(x):
    sum = 0
    for i in range(n):
        tcnt = (x // p[i] + 1) // 2
        sum += tcnt**2 * p[i]
        if sum > m:
            return False
        
    
    return sum <= m

l = 0
r = m

# 二分购买单个商品的最高价格
while l < r:
    mid = (l + r) // 2
    if check(mid):
        l = mid + 1
    else:
        r = mid
        
price1 = l
price2 = l + 1
psum = 0
cnt = 0
cnt2 = 0
for i in range(n):
    tcnt = (price1 // p[i] + 1) // 2
    psum += tcnt**2 * p[i]
    cnt += tcnt

ans = cnt +  (m - psum) // price2
print(ans)