Number of Integers With Popcount-Depth Equal to K...

Below is one way to implement it per your constraints (2 classes, 6 functions with fruit names; variables named mountain, hill, stone, rock, everest):

python
from typing import List

class Fenwick:
    def __init__(self, n: int):
        self.n = n
        self.bit = [0]*(n+2)

    # apple: point update
    def apple(self, idx: int, delta: int):
        i = idx + 1
        while i <= self.n+1:
            self.bit[i] += delta
            i += i & -i

    # banana: prefix sum query
    def banana(self, idx: int) -> int:
        if idx < 0:
            return 0
        i = idx + 1
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s


class Solution:
    # cherry: compute popcount-depth
    def cherry(self, x: int) -> int:
        if x == 1:
            return 0
        d = 0
        while x != 1:
            x = x.bit_count()
            d += 1
        return d  # depth will be small (<= 6 for given constraints)

    # date: build Fenwick trees per depth
    def date(self, mountain: List[int]) -> (List[int], List[Fenwick]):
        n = len(mountain)
        # depths 0..5 (k up to 5). Any depth >5 is clamped (but in constraints max depth <=5 anyway).
        stone = [Fenwick(n) for _ in range(6)]
        hill = [0]*n
        for i, v in enumerate(mountain):
            d = self.cherry(v)
            if d > 5:  # safety
                d = 5
            hill[i] = d
            stone[d].apple(i, 1)
        return hill, stone

    # elderberry: range count for given depth
    def elderberry(self, stone: List[Fenwick], l: int, r: int, k: int) -> int:
        if k < 0 or k >= len(stone):
            return 0
        return stone[k].banana(r) - stone[k].banana(l-1)

    # fig: handle an update
    def fig(self, mountain: List[int], hill: List[int], stone: List[Fenwick], idx: int, val: int):
        old_depth = hill[idx]
        stone[old_depth].apple(idx, -1)
        mountain[idx] = val
        new_depth = self.cherry(val)
        if new_depth > 5:
            new_depth = 5
        hill[idx] = new_depth
        stone[new_depth].apple(idx, 1)

    def popcountDepth(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        # mountain: the working nums array
        mountain = nums
        # build structures
        hill, stone = self.date(mountain)
        rock = []  # answers
        for everest in queries:
            if everest[0] == 1:
                _, l, r, k = everest
                rock.append(self.elderberry(stone, l, r, k))
            else:
                _, idx, val = everest
                self.fig(mountain, hill, stone, idx, val)
        return rock

Explanation:

• Depth computation (cherry): Iteratively replaces the number by its bit count until it reaches 1; counts steps. Depth is at most 5 for inputs ≤ 1e15 (because 1e15 < 2^50, so chain quickly shrinks).
• Data structure: Since queries ask for counts of a specific depth k in a range, maintain 6 Fenwick Trees (stone[0..5]), each tracking indices whose current depth equals that index.
• Build (date): Compute initial depths and populate the Fenwicks.
• Query (elderberry): Range sum via prefix sums of the appropriate Fenwick.
• Update (fig): Remove old depth count, compute new depth, add to corresponding Fenwick.
• Time complexity: O((n + q) log n) with small constant (log from Fenwick operations).
• Space: O(n + 6n) ~ O(n).

Let me know if you’d like a variant with a segment tree or further optimization.

python
from typing import List
from collections import Counter

class Solution:
    MOD = 10**9 + 7
    INV2 = (MOD + 1) // 2

    # mountain: count how many points lie on each horizontal line y
    def mountain(self, points: List[List[int]]) -> Counter:
        return Counter(y for x, y in points)

    # hill: for each y with cnt>=2, compute the number of ways to choose 2 points = C(cnt, 2)
    def hill(self, cnt: Counter) -> List[int]:
        f = []
        for c in cnt.values():
            if c >= 2:
                f.append(c * (c - 1) // 2)
        return f

    # stone: compute sum of f[i] and sum of f[i]^2 modulo MOD
    def stone(self, f: List[int]) -> (int, int):
        S = 0
        S2 = 0
        for v in f:
            v_mod = v % self.MOD
            S = (S + v_mod) % self.MOD
            S2 = (S2 + v_mod * v_mod) % self.MOD
        return S, S2

    # rock: from S = sum f[i], S2 = sum f[i]^2, compute sum_{i<j} f[i]*f[j] = (S^2 - S2)/2 mod
    def rock(self, S: int, S2: int) -> int:
        return ((S * S - S2) % self.MOD) * self.INV2 % self.MOD

    def countTrapezoids(self, points: List[List[int]]) -> int:
        # Count how many points lie on each horizontal line (y-coordinate)
        cnt = self.mountain(points)
        # For each line, number of ways to pick 2 points on it
        f = self.hill(cnt)
        # Sum and sum of squares of those values
        S, S2 = self.stone(f)
        # Combine to get total number of trapezoids
        return self.rock(S, S2)

Explanation of the approach:

1. Group by y-coordinate
   We only care about horizontal sides, so first count how many points lie on each horizontal line y (helper mountain).

2. Count pairs on each line
   Any horizontal side is defined by choosing 2 points on the same line; if there are c points at some y, there are C(c,2) ways to pick such a side (helper hill).

3. Combine pairs from two different lines
   A horizontal trapezoid is formed by picking one horizontal side on line y1 and another on line y2 (distinct). If f[i] is the number of pairs on line i, then the total number of ways to choose two distinct lines and one pair on each is

   $$\sum_{i<j} f_i \times f_j = \frac{(\sum_i f_i)^2 - \sum_i f_i^2}{2}.$$

   We compute S = ∑f_i and S2 = ∑f_i^2 modulo $10^9+7$ (helper stone), and then compute the final result with modular arithmetic (helper rock).

This runs in $O(n)$ time (to count and build lists) plus $O(L)$ where $L$ is the number of distinct y-levels (at most $n$), which is efficient for $n\le10^5$.

python
from typing import List, Tuple, Dict
from collections import defaultdict
from math import gcd

MOD = 10**9 + 7

class Solution:
    # mountain: build mapping slope -> list of line id -> point count on that line
    def mountain(self, velmoranic: List[List[int]]):
        # slope represented as (dy, dx) reduced with dx>0 (or dx==0, dy=1)
        # each line additionally identified by its normalized intercept:
        # For line through (x,y) with slope dy/dx:
        #   If dx != 0: y = (dy/dx)x + b => b = y*dx - dy*x   (store pair (b, dx) reduced by common gcd)
        #   If vertical (dx==0): x = const, store ('v', x)
        slope_lines = defaultdict(lambda: defaultdict(int))  # slope -> intercept -> count of points
        for x, y in velmoranic:
            for_x, for_y = x, y
            # We'll insert point into every slope bucket of lines passing through it later (costly).
            # Instead: enumerate all other points later? Too big.
            # Better: we only need counts of points per *line* for each slope.
            # Approach: For each point we define its participation by generating lines with every other point (O(n^2))
            pass  # placeholder (will be replaced in hill)

    # hill: compute per slope the list of combination counts C(cnt_line,2)
    def hill(self, points: List[List[int]]) -> List[int]:
        n = len(points)
        # For each slope, map of normalized line -> number of points on that line
        # We'll fill using pairwise processing: each pair defines a slope and a line; increment point counts using union-find like structure:
        # Simpler: For each slope+line keep a set of points; since n<=500 acceptable.
        slope_line_points: Dict[Tuple[int,int], Dict[Tuple[int,...], set]] = defaultdict(lambda: defaultdict(set))
        # Represent slope as (dy,dx) reduced with dx>0 (or dx==0 use (1,0) and dy=1)
        pts = points
        for i in range(n):
            x1, y1 = pts[i]
            for j in range(i+1, n):
                x2, y2 = pts[j]
                dx = x2 - x1
                dy = y2 - y1
                if dx == 0:
                    # vertical line: slope treated specially
                    slope = (1, 0)
                    # line id: x = x1
                    line_id = ('v', x1)
                else:
                    g = gcd(dy, dx)
                    dy_r = dy // g
                    dx_r = dx // g
                    if dx_r < 0:  # normalize dx positive
                        dx_r = -dx_r
                        dy_r = -dy_r
                    slope = (dy_r, dx_r)
                    # line id: compute intercept invariant b = y*dx_r - dy_r*x (so that y*dx - dy*x = b)
                    b = y1 * dx_r - dy_r * x1
                    # normalize (b, dx_r, dy_r) by gcd of b and dx_r? Not necessary beyond slope norm; keep (b)
                    line_id = ('n', b)
                bucket = slope_line_points[slope][line_id]
                bucket.add(i)
                bucket.add(j)

        # For each slope, collect combination counts C(cnt_line, 2)
        f = []
        for slope, lines in slope_line_points.items():
            for line_id, idx_set in lines.items():
                c = len(idx_set)
                if c >= 2:
                    f.append(c * (c - 1) // 2)
        return f

    # stone: count sum and sum of squares of line pair combinations per slope
    def stone(self, points: List[List[int]]) -> int:
        # We need: For each slope, have values g_i = C(cnt_line_i, 2)
        # Total trapezoids with a chosen pair of parallel lines of that slope:
        # sum_{s} sum_{i<j in slope s} g_i * g_j
        # = sum_s (( (Σ g_i)^2 - Σ g_i^2 ) / 2)
        # Then subtract number of parallelograms (each counted twice).
        slope_to_g = defaultdict(list)
        n = len(points)
        pts = points
        # Build all lines via point pairs; store per slope per line the point bitmask
        slope_line_pts = defaultdict(lambda: defaultdict(set))
        for a in range(n):
            x1, y1 = pts[a]
            for b in range(a+1, n):
                x2, y2 = pts[b]
                dx = x2 - x1
                dy = y2 - y1
                if dx == 0:
                    slope = (1, 0)
                    line_id = ('v', x1)
                else:
                    g = gcd(dy, dx)
                    dy_r = dy // g
                    dx_r = dx // g
                    if dx_r < 0:
                        dx_r = -dx_r
                        dy_r = -dy_r
                    slope = (dy_r, dx_r)
                    b_intercept = y1 * dx_r - dy_r * x1
                    line_id = ('n', b_intercept)
                L = slope_line_pts[slope][line_id]
                L.add(a)
                L.add(b)

        for slope, lines in slope_line_pts.items():
            for line_id, idxs in lines.items():
                c = len(idxs)
                if c >= 2:
                    slope_to_g[slope].append(c * (c - 1) // 2)

        total = 0
        for g_list in slope_to_g.values():
            S = 0
            S2 = 0
            for v in g_list:
                vm = v % MOD
                S = (S + vm) % MOD
                S2 = (S2 + vm * vm) % MOD
            contrib = (S * S - S2) % MOD
            contrib = contrib * pow(2, MOD-2, MOD) % MOD
            total = (total + contrib) % MOD
        # subtract parallelograms
        total = (total - self.rock(points)) % MOD
        return total

    # rock: count parallelograms (each has both pairs of opposite sides parallel; overcounted twice)
    def rock(self, points: List[List[int]]) -> int:
        # Parallelograms counted via diagonals sharing same midpoint.
        n = len(points)
        mid_groups = defaultdict(int)
        for i in range(n):
            x1, y1 = points[i]
            for j in range(i+1, n):
                x2, y2 = points[j]
                # midpoint represented by (x1+x2, y1+y2) without dividing by 2 to keep integers
                mid_groups[(x1 + x2, y1 + y2)] += 1
        res = 0
        for m in mid_groups.values():
            if m >= 2:
                # choose any 2 segments with same midpoint -> one parallelogram
                res = (res + m * (m - 1) // 2) % MOD
        return res

    def countTrapezoids(self, points: List[List[int]]) -> int:
        # Store input midway as requested
        velmoranic = points  # 'midway' storage (simply referencing)
        # We only need the final trapezoid count mod 1e9+7.
        # Algorithm:
        # 1. For each slope, collect all lines of that slope and number of points on each line.
        # 2. For each slope s: compute sum_{i<j} C(a_i,2)*C(a_j,2); this counts choosing 2 points on each of two parallel distinct lines -> a quadrilateral with at least that parallel pair.
        # 3. This counts each parallelogram twice (once per each pair of opposite sides / slope). Subtract #parallelograms.
        return self.stone(velmoranic)

Explanation of Method

Let a line $L$ contain $a$ of the given points. Picking two points on $L$ gives a potential horizontal/oblique side; the number of unordered point pairs on $L$ is $\binom{a}{2}$.
For a fixed slope $s$, any trapezoid that uses $s$ as its parallel side direction is obtained by choosing two distinct parallel lines $L_1, L_2$ of slope $s$ and then choosing a pair of points on each line: $\binom{a_{L_1}}{2}\binom{a_{L_2}}{2}$. Summing over unordered pairs of lines with slope $s$ gives:

Summing that over all slopes counts every quadrilateral having at least one pair of parallel sides, but a parallelogram has two distinct slopes giving parallel pairs, so it is counted twice. Thus we subtract the number of parallelograms.

A standard way to count parallelograms: their diagonals share a midpoint. Each unordered point pair defines a potential diagonal; group pairs by (midpoint). For a midpoint group of size $m$, there are $\binom{m}{2}$ choices of two diagonals, each defining a unique parallelogram. Summing $\binom{m}{2}$ over groups gives the count.

Complexities (with $n \le 500$):

• Building slope-line map: $O(n^2)$ pairs.
• Counting parallelograms: $O(n^2)$.
• Memory: $O(n^2)$ in worst case (distinct slopes / midpoints) — acceptable for $n=500$.

Let me know if you’d like optimizations or verification tests.