Problem:


B: AddMulSubDiv

Problem Statement

You have an array A of N integers. A_i denotes the i-th element of A.

You have to process one of the following queries Q times:

 Query 1: The query consists of non-negative integer x, and two positive integers s, t. For all the elements greater than or equal to x in A, you have to add s to the elements, and then multiply them by t. That is, an element with v (v \geq x) becomes t(v + s) after this query.

 Query 2: The query consists of non-negative integer x, and two positive integers s, t. For all the elements less than or equal to x in A, you have to subtract s from the elements, and then divide them by t. If the result is not an integer, you truncate it towards zero. That is, an element with v (v \leq x) becomes $\mathrm{trunc}$ ( \frac{v - s}{t} ) after this query, where $\mathrm{trunc}$ ( y ) is the integer obtained by truncating y towards zero. 

 "Truncating towards zero" means converting a decimal number to an integer so that if x = 0.0 then 0 , otherwise an integer whose absolute value is the maximum integer no more than |x| and whose sign is same as x. For example, truncating 3.5 towards zero is 3, and truncating -2.8 towards zero is -2.

After applying Q queries one by one, how many elements in A are no less than L and no more than R?

Input

N Q L R
A_1 A_2 ... A_N
q_1 x_1 s_1 t_1
:
q_Q x_Q s_Q t_Q

 The first line contains four integers N, Q, L, and R. N is the number of elements in an integer array A, Q is the number of queries, and L and R specify the range of integers you want to count within after the queries.

 The second line consists of N integers, the i-th of which is the i-th element of A.

 The following Q lines represent information of queries. The j-th line of them corresponds to the j-th query and consists of four integers q_j, x_j, s_j, and t_j.  Here, q_j = 1 stands for the j-th query is Query 1, and q_j = 2 stands for the j-th query is Query 2. x_j, s_j, and t_j are parameters used for the j-th query.

Constraints

 1 \leq N \leq 2 \times 10^5

 1 \leq Q \leq 2 \times 10^5

 -2^{63} < L \leq R < 2^{63}

 0 \leq |A_i| \leq 10^9

 q_j \in \{ 1, 2 \}

 0 \leq x_j < 2^{63}

 1 \leq s_j, t_j \leq 10^9

 Inputs consist only of integers.

 The absolute value of any element in the array dosen't exceed 2^{63} at any point during query processing.

Output

Output the number of elements in A that are no less than L and no more than R after processing all given queries in one line.

Sample Input 1

3 3 3 10
1 -2 3
1 2 2 3
2 20 1 3
2 1 20 5

Output for Sample Input 1

1



Sample input:
3 3 3 10
1 -2 3
1 2 2 3
2 20 1 3
2 1 20 5


Sample output:
1

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    n = I()
    a = LI()
    s = sum([i%2 for i in a])
    if s in (0,n):
        print(0)
    else:
        print(n-2+(s%2))
    return

#B
def B():
    n,Q,L,R = LI()
    a = LI()
    a.sort()
    query = LIR(Q)
    l = -1
    r = n
    while r-l > 1:
        m = (l+r)>>1
        am = a[m]
        for q,x,s,t in query:
            if q == 1:
                if am < x:
                    continue
                am += s
                am *= t
            else:
                if am > x:
                    continue
                am -= s
                if am < 0:
                    am = -((-am)//t)
                else:
                    am //= t
        if am < L:
            l = m
        else:
            r = m
    left = r
    l = 0
    r = n
    while r-l > 1:
        m = (l+r)>>1
        am = a[m]
        for q,x,s,t in query:
            if q == 1:
                if am < x:
                    continue
                am += s
                am *= t
            else:
                if am > x:
                    continue
                am -= s
                if am < 0:
                    am = -((-am)//t)
                else:
                    am //= t
        if am <= R:
            l = m
        else:
            r = m
    print(r-left)
    return

#C
def C():
    n = I()

    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#G
def G():
    n = I()

    return

#H
def H():
    n = I()

    return

#I
def I_():
    n = I()

    return

#J
def J():
    n = I()

    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Accepted

Solution code:
import bisect
n,Q,L,R = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
p = []
for i in range(Q):
    p.append(tuple(map(int,input().split())))


def f(z):
    for q,x,s,t in p:
        if q == 1:
            if z >= x:
                z = t*(z+s)
        else:
            if z <= x:
                if z-s < 0:
                    z = -(abs(z-s)//t)
                else:
                    z = (z-s)//t

    return z


ng = pow(2,63)
ok = -ng

for i in range(100):
    mid = (ok+ng)//2
    if f(mid) <= R:
        ok = mid
    else:
        ng = mid

right = ok        

ok = pow(2,63)
ng = -ok
        
for i in range(100):
    mid = (ok+ng)//2
    if f(mid) >= L:
        ok = mid
    else:
        ng = mid
left = ok

k1 = bisect.bisect_left(a,left)
k2 = bisect.bisect_right(a,right)


print(k2-k1)