Ann and Books (Codeforces 877F)
Tags: Others, flows

In Ann's favorite book shop are as many as n books on math and economics. Books are numbered from 1 to n. Each of them contains non-negative number of problems.Today there is a sale: any subsegment of a segment from l to r can be bought at a fixed price. Ann decided that she wants to buy such non-empty subsegment that the sale operates on it and the number of math problems is greater than the number of economics problems exactly by k. Note that k may be positive, negative or zero.Unfortunately, Ann is not sure on which segment the sale operates, but she has q assumptions. For each of them she wants to know the number of options to buy a subsegment satisfying the condition (because the time she spends on choosing depends on that).Currently Ann is too busy solving other problems, she asks you for help. For each her assumption determine the number of subsegments of the given segment such that the number of math problems is greaten than the number of economics problems on that subsegment exactly by k.

Input: The first line contains two integers n and k (1 ≤ n ≤ 100 000,  - 109 ≤ k ≤ 109) — the number of books and the needed difference between the number of math problems and the number of economics problems.The second line contains n integers t1, t2, ..., tn (1 ≤ ti ≤ 2), where ti is 1 if the i-th book is on math or 2 if the i-th is on economics.The third line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 109), where ai is the number of problems in the i-th book.The fourth line contains a single integer q (1 ≤ q ≤ 100 000) — the number of assumptions.Each of the next q lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n) describing the i-th Ann's assumption.

Output: Print q lines, in the i-th of them print the number of subsegments for the i-th Ann's assumption.

Note: In the first sample Ann can buy subsegments [1;1], [2;2], [3;3], [2;4] if they fall into the sales segment, because the number of math problems is greater by 1 on them that the number of economics problems. So we should count for each assumption the number of these subsegments that are subsegments of the given segment.Segments [1;1] and [2;2] are subsegments of [1;2].Segments [1;1], [2;2] and [3;3] are subsegments of [1;3].Segments [1;1], [2;2], [3;3], [2;4] are subsegments of [1;4].Segment [3;3] is subsegment of [3;4].

Sample Inputs:
4 1
1 1 1 2
1 1 1 1
4
1 2
1 3
1 4
3 4

4 0
1 2 1 2
0 0 0 0
1
1 4

Sample Outputs:
2
3
4
1

10

Solution (Python):
import os, sys
from io import BytesIO, IOBase
BUFSIZ = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'n' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZ))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZ))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda sett: self.buffer.write(sett.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
if sys.version_info[0] < 3:
    (sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
''
''
from math import ceil

def prod(a, mod=10 ** 9 + 7):
    ans = 1
    for each in a:
        ans = ans * each % mod
    return ans

def gcd(x, y):
    while y:
        (x, y) = (y, x % y)
    return x

def lcm(a, b):
    return a * b // gcd(a, b)

def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if not True else 1):
    (n, k) = map(int, input().split())
    t = list(map(int, input().split()))
    a = list(map(int, input().split()))
    for i in range(n):
        if t[i] == 2:
            a[i] *= -1
    count = [0] * (n + 1)
    pre = [0]
    for i in a:
        pre += [pre[-1] + i]
    index = {}
    cc = list(set(pre))
    for i in range(len(cc)):
        index[cc[i]] = i
    minusK = [-1] * (n + 1)
    plusK = [-1] * (n + 1)
    zero = [-1] * (n + 1)
    for i in range(n + 1):
        if pre[i] - k in index:
            minusK[i] = index[pre[i] - k]
        if pre[i] + k in index:
            plusK[i] = index[pre[i] + k]
        zero[i] = index[pre[i]]
    BLOCK_SIZE = 320
    blocks = [[] for i in range(BLOCK_SIZE)]
    q = int(input())
    ans = [0] * q
    for i in range(q):
        (l, r) = map(int, input().split())
        blocks[l // BLOCK_SIZE] += [[l - 1, r, i]]
    for i in range(len(blocks)):
        if not blocks[i]:
            continue
        blocks[i] = sorted(blocks[i], key=lambda x: x[1])
        left = right = BLOCK_SIZE * i
        res = 0
        count[zero[left]] += 1
        for (l, r, ind) in blocks[i]:
            while right < r:
                right += 1
                if minusK[right] != -1:
                    res += count[minusK[right]]
                count[zero[right]] += 1
            while left < l:
                count[zero[left]] -= 1
                if plusK[left] != -1:
                    res -= count[plusK[left]]
                left += 1
            while left > l:
                left -= 1
                if plusK[left] != -1:
                    res += count[plusK[left]]
                count[zero[left]] += 1
            ans[ind] = res
        while left <= right:
            count[zero[left]] -= 1
            if plusK[left] != -1:
                res -= count[plusK[left]]
            left += 1
        assert res == 0
    for i in ans:
        sys.stdout.write('%i\n' % i)
''

Solution (Python):
import os, sys
from io import BytesIO, IOBase
BUFSIZ = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'n' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZ))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZ))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda sett: self.buffer.write(sett.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
if sys.version_info[0] < 3:
    (sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
''
''
from math import ceil

def prod(a, mod=10 ** 9 + 7):
    ans = 1
    for each in a:
        ans = ans * each % mod
    return ans

def gcd(x, y):
    while y:
        (x, y) = (y, x % y)
    return x

def lcm(a, b):
    return a * b // gcd(a, b)

def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(sys.stdin.readline()) if not True else 1):
    (n, k) = map(int, sys.stdin.readline().split())
    t = tuple(map(int, sys.stdin.readline().split()))
    a = list(map(int, sys.stdin.readline().split()))
    for i in range(n):
        if t[i] == 2:
            a[i] *= -1
    count = [0] * (n + 1)
    pre = [0]
    for i in a:
        pre += [pre[-1] + i]
    index = {}
    cc = list(set(pre))
    for i in range(len(cc)):
        index[cc[i]] = i
    minusK = [-1] * (n + 1)
    plusK = [-1] * (n + 1)
    zero = [-1] * (n + 1)
    for i in range(n + 1):
        if pre[i] - k in index:
            minusK[i] = index[pre[i] - k]
        if pre[i] + k in index:
            plusK[i] = index[pre[i] + k]
        zero[i] = index[pre[i]]
    BLOCK_SIZE = 320
    blocks = [[] for i in range(BLOCK_SIZE)]
    q = int(sys.stdin.readline())
    ans = [0] * q
    for i in range(q):
        (l, r) = map(int, sys.stdin.readline().split())
        blocks[l // BLOCK_SIZE] += [[l - 1, r, i]]
    for i in range(len(blocks)):
        if not blocks[i]:
            continue
        blocks[i] = sorted(blocks[i], key=lambda x: x[1])
        left = right = BLOCK_SIZE * i
        res = 0
        count[zero[left]] += 1
        for (l, r, ind) in blocks[i]:
            while right < r:
                right += 1
                if minusK[right] != -1:
                    res += count[minusK[right]]
                count[zero[right]] += 1
            while left < l:
                count[zero[left]] -= 1
                if plusK[left] != -1:
                    res -= count[plusK[left]]
                left += 1
            while left > l:
                left -= 1
                if plusK[left] != -1:
                    res += count[plusK[left]]
                count[zero[left]] += 1
            ans[ind] = res
        while left <= right:
            count[zero[left]] -= 1
            if plusK[left] != -1:
                res -= count[plusK[left]]
            left += 1
        assert res == 0
    for i in ans:
        sys.stdout.write('%i\n' % i)
''

Solution (Python):
import os, sys
from io import BytesIO, IOBase
BUFSIZ = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'n' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZ))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZ))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda sett: self.buffer.write(sett.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
if sys.version_info[0] < 3:
    (sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
''
''
from math import ceil

def prod(a, mod=10 ** 9 + 7):
    ans = 1
    for each in a:
        ans = ans * each % mod
    return ans

def gcd(x, y):
    while y:
        (x, y) = (y, x % y)
    return x

def lcm(a, b):
    return a * b // gcd(a, b)

def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if not True else 1):
    (n, k) = map(int, input().split())
    t = list(map(int, input().split()))
    a = list(map(int, input().split()))
    for i in range(n):
        if t[i] == 2:
            a[i] *= -1
    count = [0] * (n + 1)
    pre = [0]
    for i in a:
        pre += [pre[-1] + i]
    index = {}
    cc = list(set(pre))
    for i in range(len(cc)):
        index[cc[i]] = i
    minusK = [-1] * (n + 1)
    plusK = [-1] * (n + 1)
    zero = [-1] * (n + 1)
    for i in range(n + 1):
        if pre[i] - k in index:
            minusK[i] = index[pre[i] - k]
        if pre[i] + k in index:
            plusK[i] = index[pre[i] + k]
        zero[i] = index[pre[i]]
    BLOCK_SIZE = 320
    blocks = [[] for i in range(BLOCK_SIZE)]
    q = int(input())
    ans = [0] * q
    for i in range(q):
        (l, r) = map(int, input().split())
        blocks[l // BLOCK_SIZE] += [[l - 1, r, i]]
    for i in range(len(blocks)):
        if not blocks[i]:
            continue
        blocks[i] = sorted(blocks[i], key=lambda x: x[1])
        left = right = BLOCK_SIZE * i
        res = 0
        count[zero[left]] += 1
        for (l, r, ind) in blocks[i]:
            while right < r:
                right += 1
                if minusK[right] != -1:
                    res += count[minusK[right]]
                count[zero[right]] += 1
            while left < l:
                count[zero[left]] -= 1
                if plusK[left] != -1:
                    res -= count[plusK[left]]
                left += 1
            while left > l:
                left -= 1
                if plusK[left] != -1:
                    res += count[plusK[left]]
                count[zero[left]] += 1
            ans[ind] = res
        while left <= right:
            count[zero[left]] -= 1
            if plusK[left] != -1:
                res -= count[plusK[left]]
            left += 1
        assert res == 0
    for i in ans:
        sys.stdout.write('%i\n' % i)
''