题解 | 可匹配子段计数

t = int(input())

for _ in range(t):
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    a_count = {}
    for i in a[:m]:
        a_count[i] = a_count.get(i, 0) + 1
    b_count = {}
    for i in b:
        b_count[i] = b_count.get(i, 0) + 1
    r = 0
    match_count = 0
    for key, val in b_count.items():
        match_count += min(val, a_count.get(key, 0))
    if match_count >= k:
        r += 1
    for i in range(m, n): 
        rm = a[i-m]
        if rm in b_count and a_count[rm] <= b_count.get(rm, 0):
            match_count -= 1
        a_count[rm] -= 1
        if a_count[rm] == 0:
            del a_count[rm]  
        add = a[i]
        if add in b_count and a_count.get(add, 0) < b_count.get(add, 0):
            match_count += 1
        a_count[add] = a_count.get(add, 0) + 1
        if match_count >= k:
            r += 1
    print(r)