Strange Nim Game
Source: codechef
Difficulty: 2445

Strange Nim Game
Alice and Bob are playing a strange variant of the Nim game. The rules are as follows:
There are$N$towers, with the$i$-th tower having$A_i$rings.
On their turn, a player selects a tower$i$that contains a positive number of rings, and a
positive
digit$d$such that$d$appears in the decimal representation of$A_i$.
Then, they remove$d$rings from the$i$-th tower.
For example, if$A_i = 5028$, the current player can remove$2, 5,$or$8$rings from it.
The game ends when all rings from all towers are removed. The player who removed the last ring wins.
Alice always makes the first move, and both players play optimally.
You are given the initial number of rings in$N$towers, represented by the array$A$.
Process$Q$queries and updates of the following types:
Query:
1 L R
Consider only the towers from indices$L$through$R$, inclusive - i.e. the towers$[A_L, A_{L+1}, \ldots, A_R]$.
Count the number of non-empty
subsequences
of these towers that will result in Alice winning, if the game is played with only the towers in this subsequence.
The answer can be large, so compute it modulo$10^9 + 7$.
Update:
2 i x
Set$A_i = x$.
Input Format
The first line contains an integer$N$— the number of towers.
The second line contains$N$space-separated integers$A_1, A_2, \ldots, A_N$— the initial number of rings in each tower.
The third line contains an integer$Q$— the number of queries.
The next$Q$lines contain the queries. Each line will be in one of two types:
1 L R
, denoting a query with parameters$L$and$R$.
2 i x
, denoting an update with parameters$i$and$x$.
Output Format
For each query, print a single integer on a new line — the number of subsequences of towers from index$L$to$R$such that Alice will win if both players play optimally on this subsequence, starting with the initial configuration of the towers.
The answers must be printed modulo$10^9 + 7$.
Constraints$1 \leq N \leq 2 \times 10^5$$1 \leq Q \leq 10^5$$1 \leq A_i \leq 2 \times 10^5$Each query/update is either of the form
1 L R
or
2 i x
.
For queries,$1 \leq L \leq R \leq N$For updates,$1 \leq i \leq N$and$1 \leq x \leq 2\times 10^5$There is at least one type 1 query.
Sample 1:
Explanation:
Initial Towers Configuration
:
The towers initially contain the following number of rings:$[11, 2, 3]$.
Query 1 (
1 1 3
)
:
We need to find how many subsequences of towers from index$1$to$3$will result in Alice winning if both players play optimally.
The subsequences of towers selected are:$[11]$— Alice wins.$[2]$— Alice wins.$[3]$— Alice wins.$[11, 2]$— Bob wins.$[11, 3]$— Bob wins.$[2, 3]$— Bob wins.$[11, 2, 3]$— Alice wins.
Therefore, the total number of subsequences where Alice wins is$4$.
Query 2 (
2 1 10
)
:
The number of rings in the 1st tower is updated to$10$, so the towers are now:$[10, 2, 3]$.
Query 3 (
1 1 3
)
:
We now need to find how many subsequences of towers from index$1$to$3$will result in Alice winning.
Since the towers are now$[10, 2, 3]$, the subsequences that Alice will win on are as follows:$[10]$— Bob wins.$[2]$— Alice wins.$[3]$— Alice wins.$[10, 2]$— Alice wins.$[10, 3]$— Alice wins.$[2, 3]$— Bob wins.$[10, 2, 3]$— Bob wins.
Hence, the total number of subsequences where Alice wins is$4$.

Sample Input:
3
11 2 3
3
1 1 3
2 1 10
1 1 3

Sample Output:
4
4

C++ solution:
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
using namespace std;

#ifdef LOCAL
#include "codes/debug.h"
#else
#define debug(...)
#endif

using ll = int64_t;
#define sz(x) ((int)(x).size())
const char nl = '\n';

const int maxn = 2e5 + 5;
int grundy[maxn + 1];

int mex (vector<int> v) {
  int ret = 0;

  for (int i = 0; i < sz(v); i++) {
    if (v[i] == ret)
      ret++;
    else if (v[i] < ret) 
      continue;
    else  
      break;
  }

  return ret;
}

template <typename T>
struct Fenwick {  // 1-based
  const int n;
  std::vector<T> a;
  Fenwick(int m) : n(m), a(m) {}
  void add (int x, T v) { // add v to index x
    x--;
    for (int i = x + 1; i <= n; i += i & -i) {
      a[i - 1] += v;
    }
  }
  T sum (int x) {  // sum till index x (1...x)
    T ans = 0;
    for (int i = x; i > 0; i -= i & -i) {
      ans += a[i - 1];
    }
    return ans;
  }
};

int twop[maxn + 1];
const int mod = 1e9 + 7;
vector<int> masks;

void solve() {
  int n;
  cin >> n;
  vector<int> a (n + 1);
  for (int i = 1; i <= n; ++i) 
    cin >> a[i], a[i] = grundy[a[i]];
  
  vector<Fenwick<int>> f (7, Fenwick<int> (n)); 
  for (int i = 1; i <= n; ++i) {
    f[a[i]].add (i, 1);
  }

  int q;
  cin >> q;

  for (int i = 0, t, x, y; i < q; ++i) {
    cin >> t >> x >> y;

    if (t == 1) {
      ll ans = 0;

      for (int mask : masks) {
        ll cur = 1;
        
        for (int j = 0; j < 7; ++j) {
          int cnt = f[j].sum (y) - f[j].sum (x - 1);

          if ((mask & (1 << j)) and !cnt) {
            cur = 0;
            break;
          } else if (!cnt)
            continue;

          cur *= twop[cnt - 1];
          cur %= mod;
        } 

        ans += cur;
        ans %= mod;
      }
      
      ans = (twop[y - x + 1] - ans + mod) % mod;

      cout << ans << nl;
    } else {
      f[a[x]].add (x, -1);
      a[x] = grundy[y];
      f[a[x]].add (x, 1);
    }
  }

}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int mx = 0;
  int p = 1;
  twop[0] = 1;
  for (int i = 1; i <= maxn; ++i) {
    p *= 2, p %= mod;
    twop[i] = p; 

    int x = i;

    vector<int> states;
    while (x) {
      int y = x % 10;
      if (y)
        states.push_back (grundy[i - y]);
      x = x / 10;
    }

    sort (states.begin(), states.end());
    grundy[i] = mex (states);
    mx = max (mx, grundy[i]);
  }

  for (int i = 0; i < (1 << 7); ++i) {
    int xo = 0;
    for (int j = 0; j < 7; ++j) {
      if (i & (1 << j)) {
        xo ^= j;
      }
    }

    if (!xo)
      masks.push_back (i);
  }

  int t = 1;
  for (int i = 1; i <= t; i++)
    solve();

  return 0;
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
)

const (
    MOD = 1000000007
    MAXN = 200000
    BITS = 30
)

type SegmentTreeNode struct {
    l, r    int
    left    *SegmentTreeNode
    right   *SegmentTreeNode
    basis   []int
    count   int
}

func (node *SegmentTreeNode) updateFromValue(val int) {
    node.basis = make([]int, BITS)
    tmp := val
    for i := BITS - 1; i >= 0; i-- {
        if (tmp>>i)&1 == 1 {
            if node.basis[i] == 0 {
                node.basis[i] = tmp
                break
            } else {
                tmp ^= node.basis[i]
            }
        }
        if tmp == 0 {
            break
        }
    }
    node.count = 1
}

func (node *SegmentTreeNode) mergeChildren() {
    node.basis = make([]int, BITS)
    copy(node.basis, node.left.basis)
    
    for i := 0; i < BITS; i++ {
        if node.right.basis[i] != 0 {
            tmp := node.right.basis[i]
            for j := BITS - 1; j >= 0; j-- {
                if (tmp>>j)&1 == 1 {
                    if node.basis[j] == 0 {
                        node.basis[j] = tmp
                        break
                    } else {
                        tmp ^= node.basis[j]
                    }
                }
                if tmp == 0 {
                    break
                }
            }
        }
    }
    node.count = node.left.count + node.right.count
}

func build(l, r int, arr []int) *SegmentTreeNode {
    node := &SegmentTreeNode{l: l, r: r, basis: make([]int, BITS)}
    if l == r {
        node.updateFromValue(arr[l-1])
    } else {
        mid := (l + r) / 2
        node.left = build(l, mid, arr)
        node.right = build(mid+1, r, arr)
        node.mergeChildren()
    }
    return node
}

func update(node *SegmentTreeNode, idx, val int) {
    if node.l == node.r && node.l == idx {
        node.updateFromValue(val)
        return
    }
    if idx <= node.left.r {
        update(node.left, idx, val)
    } else {
        update(node.right, idx, val)
    }
    node.mergeChildren()
}

func query(node *SegmentTreeNode, l, r int, currentBasis []int, currentCount *int) {
    if node.r < l || node.l > r {
        return
    }
    if l <= node.l && node.r <= r {
        *currentCount += node.count
        for i := 0; i < BITS; i++ {
            x := node.basis[i]
            if x != 0 {
                tmp := x
                for j := BITS - 1; j >= 0; j-- {
                    if (tmp>>j)&1 == 1 {
                        if currentBasis[j] == 0 {
                            currentBasis[j] = tmp
                            break
                        } else {
                            tmp ^= currentBasis[j]
                        }
                    }
                    if tmp == 0 {
                        break
                    }
                }
            }
        }
        return
    }
    query(node.left, l, r, currentBasis, currentCount)
    query(node.right, l, r, currentBasis, currentCount)
}

func main() {
    reader := bufio.NewReader(os.Stdin)
    writer := bufio.NewWriter(os.Stdout)
    defer writer.Flush()
    
    // Calculate Grundy numbers
    grundy := make([]int, MAXN+1)
    for x := 1; x <= MAXN; x++ {
        digits := make(map[int]bool)
        tmp := x
        for tmp > 0 {
            d := tmp % 10
            if d != 0 {
                digits[d] = true
            }
            tmp /= 10
        }
        s := make(map[int]bool)
        for d := range digits {
            if x >= d {
                s[grundy[x-d]] = true
            }
        }
        mex := 0
        for s[mex] {
            mex++
        }
        grundy[x] = mex
    }
    
    // Calculate powers of 2
    pow2 := make([]int, MAXN+30)
    pow2[0] = 1
    for i := 1; i <= MAXN+29; i++ {
        pow2[i] = (pow2[i-1] * 2) % MOD
    }
    
    var N int
    fmt.Fscan(reader, &N)
    
    A := make([]int, N)
    grundyA := make([]int, N)
    for i := 0; i < N; i++ {
        fmt.Fscan(reader, &A[i])
        grundyA[i] = grundy[A[i]]
    }
    
    root := build(1, N, grundyA)
    
    var Q int
    fmt.Fscan(reader, &Q)
    
    for q := 0; q < Q; q++ {
        var typ int
        fmt.Fscan(reader, &typ)
        
        if typ == 1 {
            var L, R int
            fmt.Fscan(reader, &L, &R)
            currentBasis := make([]int, BITS)
            currentCount := 0
            query(root, L, R, currentBasis, &currentCount)
            
            r := 0
            for _, x := range currentBasis {
                if x != 0 {
                    r++
                }
            }
            t := R - L + 1
            ans := (pow2[t] - pow2[t-r] + MOD) % MOD
            fmt.Fprintln(writer, ans)
        } else {
            var i, x int
            fmt.Fscan(reader, &i, &x)
            newG := grundy[x]
            update(root, i, newG)
        }
    }
}

Java solution:
import java.io.*;
import java.util.*;

class Codechef {
    static final int MOD = 1000000007;
    static final int MAX_A = 200000; // maximum value of A[i]
    static int[] grundy = new int[MAX_A+1];
    static int polyLen; // length of our polynomials (a power-of-two >= (max Grundy value + 1))
    
    public static void main(String[] args) throws IOException {
        // Fast I/O
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        
        // Precompute Grundy values for all numbers 0..MAX_A.
        computeGrundy();
        
        // Determine the maximum Grundy value computed.
        int globalMax = 0;
        for (int n = 0; n <= MAX_A; n++){
            globalMax = Math.max(globalMax, grundy[n]);
        }
        // We want to store our polynomials in an array whose indices cover all possible XOR values.
        // Since each leaf is: poly[0] = 1 and poly[g] = 1 (where g is the Grundy value),
        // the maximum index we need is at least globalMax. Moreover, when XOR–combining several values,
        // the maximum possible result is less than (polyLen). So choose polyLen to be the smallest power–of–two greater than globalMax.
        polyLen = 1;
        while(polyLen <= globalMax) polyLen *= 2;
        
        // Read N and the initial towers.
        int N = Integer.parseInt(br.readLine().trim());
        int[] A = new int[N+1]; // 1-indexed towers
        int[] B = new int[N+1]; // B[i] = grundy(A[i])
        String[] parts = br.readLine().split(" ");
        for (int i = 1; i <= N; i++){
            A[i] = Integer.parseInt(parts[i-1]);
            B[i] = grundy[A[i]];
        }
        
        // Build segment tree for XOR–convolution.
        // Each leaf corresponds to a tower and holds a polynomial P of length polyLen:
        // P[0] = 1 (the option of not picking that tower) and P[B[i]]++ (picking it).
        int size = 1;
        while(size < N) size *= 2;
        long[][] segtree = new long[2*size][];
        // Initialize leaves.
        for (int i = 0; i < size; i++){
            if(i < N){
                segtree[size + i] = leafPoly(B[i+1]);
            } else {
                // Identity for XOR–convolution: polynomial with coefficient 1 at index 0.
                segtree[size + i] = identityPoly();
            }
        }
        // Build internal nodes.
        for (int i = size - 1; i > 0; i--){
            segtree[i] = mergePoly(segtree[2*i], segtree[2*i+1]);
        }
        
        // Precompute powers of 2 up to N (since an interval of length m has 2^m subsets)
        long[] pow2 = new long[N+1];
        pow2[0] = 1;
        for (int i = 1; i <= N; i++){
            pow2[i] = (pow2[i-1] * 2) % MOD;
        }
        
        // Process Q queries/updates.
        int Q = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        for (int qi = 0; qi < Q; qi++){
            String line = br.readLine();
            String[] arr = line.split(" ");
            int type = Integer.parseInt(arr[0]);
            if(type == 1){
                // Query: 1 L R
                int L = Integer.parseInt(arr[1]);
                int R = Integer.parseInt(arr[2]);
                // Query the segment tree for the convolution polynomial on [L,R].
                long[] poly = query(segtree, size, L, R);
                int m = R - L + 1;
                // poly[0] is the count of subsets (including the empty one) whose XOR is 0.
                // Total number of subsets is 2^m, so the number of non-empty winning subsets (those with XOR != 0)
                // is 2^m - poly[0] (note that the empty subset is counted in poly[0]).
                long ans = (pow2[m] - poly[0]) % MOD;
                if(ans < 0) ans += MOD;
                sb.append(ans).append("\n");
            } else {
                // Update: 2 i x   => set A[i] = x.
                int i = Integer.parseInt(arr[1]);
                int x = Integer.parseInt(arr[2]);
                A[i] = x;
                int newG = grundy[x];
                B[i] = newG;
                // Update the leaf at position i (1-indexed).
                int pos = size + i - 1;
                segtree[pos] = leafPoly(newG);
                // Update the ancestors.
                pos /= 2;
                while(pos >= 1){
                    segtree[pos] = mergePoly(segtree[2*pos], segtree[2*pos+1]);
                    pos /= 2;
                }
            }
        }
        
        out.print(sb.toString());
        out.close();
    }
    
    // Precompute Grundy values for numbers 0..MAX_A.
    // We use a temporary reachable array of length 16 to be safe.
    static void computeGrundy() {
        grundy[0] = 0;
        for (int n = 1; n <= MAX_A; n++){
            boolean[] reachable = new boolean[16]; 
            int temp = n;
            boolean[] digitSeen = new boolean[10];
            while(temp > 0){
                int d = temp % 10;
                temp /= 10;
                if(d == 0) continue;
                if(digitSeen[d]) continue;
                digitSeen[d] = true;
                // allowed move: n -> n-d
                int nxt = n - d;
                if(nxt >= 0) {
                    int g = grundy[nxt];
                    if(g < reachable.length)
                        reachable[g] = true;
                }
            }
            int g = 0;
            while(g < reachable.length && reachable[g]) g++;
            grundy[n] = g;
        }
    }
    
    // Return an identity polynomial for XOR–convolution:
    // That is, a polynomial P with P[0] = 1 and P[i] = 0 for i > 0.
    static long[] identityPoly() {
        long[] poly = new long[polyLen];
        poly[0] = 1;
        return poly;
    }
    
    // Returns the leaf polynomial corresponding to a tower with Grundy value g.
    // The polynomial is an array of length polyLen: poly[0] = 1 (not picking the tower),
    // and poly[g] is increased by 1 (if we pick the tower).
    static long[] leafPoly(int g) {
        long[] poly = new long[polyLen];
        poly[0] = 1;
        poly[g] = (poly[g] + 1) % MOD;
        return poly;
    }
    
    // Merge (XOR–convolution) two polynomials A and B (both of length polyLen).
    // That is, define C[w] = sum_{a XOR b = w} A[a] * B[b].
    static long[] mergePoly(long[] A, long[] B) {
        long[] C = new long[polyLen];
        for (int a = 0; a < polyLen; a++){
            if(A[a] == 0) continue;
            for (int b = 0; b < polyLen; b++){
                if(B[b] == 0) continue;
                int idx = a ^ b;
                C[idx] = (C[idx] + A[a] * B[b]) % MOD;
            }
        }
        return C;
    }
    
    // Query the segment tree for the convolution polynomial in the range [l, r] (1-indexed).
    static long[] query(long[][] segtree, int size, int l, int r) {
        l = l + size - 1;
        r = r + size - 1;
        // Identity for XOR–convolution.
        long[] leftRes = identityPoly();
        long[] rightRes = identityPoly();
        while(l <= r) {
            if((l & 1) == 1) {
                leftRes = mergePoly(leftRes, segtree[l]);
                l++;
            }
            if((r & 1) == 0) {
                rightRes = mergePoly(segtree[r], rightRes);
                r--;
            }
            l /= 2;
            r /= 2;
        }
        return mergePoly(leftRes, rightRes);
    }
}

JavaScript solution:
/* -------------------------------------------------------- */
/*   ( The Authentic JS CodeBuff )
 ___ _                      _              _ 
 | _ ) |_  __ _ _ _ __ _ __| |_ __ ____ _ (_)
 | _ \ ' \/ _` | '_/ _` / _` \ V  V / _` || |
 |___/_||_\__,_|_| \__,_\__,_|\_/\_/\__,_|/ |
                                        |__/ 
 */
/* ---------------------------------------------------------   */
/*    Youtube: https://youtube.com/@code-with-Bharadwaj        */
/*    Github :  https://github.com/Manu577228                  */
/* ----------------------------------------------------------- */

let fs = require("fs");
let b = Buffer.alloc(1 << 16);
let p = 0;
let l = 0;

let M = BigInt(1e9 + 7);
let x = 200000;
let g = new Uint32Array(x + 1);
let w = new Array(x + 31).fill(BigInt(1));

function r() {
        if (p === l) {
                p = 0;
                l = fs.readSync(0, b, 0, b.length, null);
                if (l === 0) return -1;
        }
        return b[p++];
}

function n() {
        let c = r();
        while (c <= 32) c = r();
        let v = 0;
        while (c >= 48 && c <= 57) {
                v = v * 10 + (c - 48);
                c = r();
        }
        return v;
}

for (let i = 1; i <= x; i++) {
        let d = new Set();
        let t = i;
        while (t > 0) {
                let v = t % 10;
                if (v !== 0) d.add(v);
                t = Math.floor(t / 10);
        }
        let s = new Set();
        for (let j of d) {
                if (i >= j) s.add(g[i - j]);
        }
        let m = 0;
        while (s.has(m)) m++;
        g[i] = m;
}

for (let i = 1; i <= x + 30; i++) {
        w[i] = (w[i - 1] * BigInt(2)) % M;
}

class N {
        constructor(l, r) {
                this.l = l;
                this.r = r;
                this.f = null;
                this.h = null;
                this.b = new Uint32Array(30);
                this.c = 0;
        }
}

function k(n, v) {
        n.b.fill(0);
        let t = v;
        for (let i = 29; i >= 0; i--) {
                if ((t >> i) & 1) {
                        if (n.b[i] === 0) {
                                n.b[i] = t;
                                break;
                        } else {
                                t ^= n.b[i];
                        }
                }
                if (t === 0) break;
        }
        n.c = 1;
}

function m(n) {
        n.b = n.f.b.slice();
        for (let i = 0; i < 30; i++) {
                if (n.h.b[i] !== 0) {
                        let t = n.h.b[i];
                        for (let j = 29; j >= 0; j--) {
                                if ((t >> j) & 1) {
                                        if (n.b[j] === 0) {
                                                n.b[j] = t;
                                                break;
                                        } else {
                                                t ^= n.b[j];
                                        }
                                }
                                if (t === 0) break;
                        }
                }
        }
        n.c = n.f.c + n.h.c;
}

function b_(l, r, a) {
        let n = new N(l, r);
        if (l === r) {
                k(n, a[l - 1]);
        } else {
                let d = (l + r) >> 1;
                n.f = b_(l, d, a);
                n.h = b_(d + 1, r, a);
                m(n);
        }
        return n;
}

let u = new Uint32Array(30);
let z = 0;

function q(n, l, r) {
        if (n.r < l || n.l > r) return;
        if (l <= n.l && n.r <= r) {
                z += n.c;
                for (let i = 0; i < 30; i++) {
                        let x = n.b[i];
                        if (x !== 0) {
                                let t = x;
                                for (let j = 29; j >= 0; j--) {
                                        if ((t >> j) & 1) {
                                                if (u[j] === 0) {
                                                        u[j] = t;
                                                        break;
                                                } else {
                                                        t ^= u[j];
                                                }
                                        }
                                        if (t === 0) break;
                                }
                        }
                }
                return;
        }
        q(n.f, l, r);
        q(n.h, l, r);
}

function y(n, i, v) {
        if (n.l === n.r && n.l === i) {
                k(n, v);
                return;
        }
        if (i <= n.f.r) y(n.f, i, v);
        else y(n.h, i, v);
        m(n);
}

let e = n();
let a = new Uint32Array(e);
for (let i = 0; i < e; i++) a[i] = g[n()];
let o = b_(1, e, a);
let Q = n();

while (Q--) {
        let t = n();
        if (t === 1) {
                let L = n();
                let R = n();
                u.fill(0);
                z = 0;
                q(o, L, R);
                let T = R - L + 1;
                let s = 0;
                for (let x of u)
                        if (x !== 0) s++;
                let v = (w[T] - w[T - s] + M) % M;
                process.stdout.write(v.toString() + '\n');
        } else {
                let i = n();
                let x = n();
                y(o, i, g[x]);
        }
}

Python solution:
def solve():

    import sys,sys

    data = sys.stdin.buffer.read().split()
    if not data: 
        return
    it = iter(data)
    mod = 10**9+7

    # read N and array A
    n = int(next(it))
    A = [int(next(it)) for _ in range(n)]
    Q = int(next(it))
    
    maxA = 200000
    dp = [0]*(maxA+1)
    for x in range(1, maxA+1):
        used = 0
        y = x
        while y:
            d = y % 10
            y //= 10
            if d:
                used |= (1 << d)
        s = set()
        d = 1
        while d <= 9:
            if used & (1 << d):
                s.add(dp[x-d])
            d += 1
        g = 0
        while g in s:
            g += 1
        dp[x] = g

    B = [dp[a] for a in A]
    
    pow2 = [1]*(n+5)
    for i in range(1, n+5):
        pow2[i] = (pow2[i-1]*2) % mod

    def add_to_basis(basis, x):
        for b in basis:
            x = min(x, x ^ b)
            if x == 0:
                break
        if x:
            basis.append(x)
        return basis

    def merge_basis(b1, b2):
        new_basis = b1[:]
        for x in b2:
            add_to_basis(new_basis, x)
        return new_basis

    size = 1
    while size < n:
        size *= 2
    seg = [None]*(2*size)
    for i in range(n):
        seg[size+i] = [B[i]] if B[i] else []
    for i in range(n, size):
        seg[size+i] = []
    for i in range(size-1, 0, -1):
        seg[i] = merge_basis(seg[2*i], seg[2*i+1])
    
    def seg_update(pos, val):
        idx = pos + size
        seg[idx] = [val] if val else []
        idx //= 2
        while idx:
            seg[idx] = merge_basis(seg[2*idx], seg[2*idx+1])
            idx //= 2

    def seg_query(l, r):
        res = []
        l += size; r += size
        while l < r:
            if l & 1:
                res = merge_basis(res, seg[l])
                l += 1
            if r & 1:
                r -= 1
                res = merge_basis(res, seg[r])
            l //= 2; r //= 2
        return res

    out_lines = []
    for _ in range(Q):
        typ = next(it)
        if typ == b'1':
            L = int(next(it))
            R = int(next(it))
            l_idx = L - 1; r_idx = R
            total = R - L + 1
            basis = seg_query(l_idx, r_idx)
            rank = len(basis)
            ans = (pow2[total] - pow2[total - rank]) % mod
            out_lines.append(str(ans))
        else:
            i = int(next(it))
            x = int(next(it))
            new_val = dp[x]
            seg_update(i-1, new_val)
    sys.stdout.write("\n".join(out_lines))
 
if __name__ == '__main__':
    solve()

Ruby solution:
def solve
  input = $stdin.read.split
  ptr = 0
  mod = 10**9 + 7

  n = input[ptr].to_i
  ptr += 1
  a = input[ptr, n].map(&:to_i)
  ptr += n
  q = input[ptr].to_i
  ptr += 1

  max_a = 200000
  dp = Array.new(max_a + 1, 0)

  (1..max_a).each do |x|
    used = 0
    y = x
    while y > 0
      d = y % 10
      y /= 10
      used |= (1 << d) if d != 0
    end
    s = {}
    (1..9).each do |d|
      if (used & (1 << d)) != 0 && x >= d
        s[dp[x - d]] = true
      end
    end
    g = 0
    while s.key?(g)
      g += 1
    end
    dp[x] = g
  end

  b = a.map { |num| dp[num] }

  pow2 = Array.new(n + 5, 1)
  (1..n+4).each do |i|
    pow2[i] = (pow2[i-1] * 2) % mod
  end

  size = 1
  while size < n
    size *= 2
  end
  seg = Array.new(2 * size) { [] }

  n.times do |i|
    seg[size + i] = b[i] != 0 ? [b[i]] : []
  end
  (n...size).each do |i|
    seg[size + i] = []
  end
  (size - 1).downto(1) do |i|
    basis = seg[2*i].dup
    seg[2*i + 1].each do |x|
      basis.each do |b|
        x = [x, x ^ b].min
        break if x == 0
      end
      basis << x if x != 0
    end
    seg[i] = basis
  end

  update_seg = lambda do |pos, val|
    pos += size
    seg[pos] = val != 0 ? [val] : []
    pos /= 2
    while pos >= 1
      basis = seg[2*pos].dup
      seg[2*pos + 1].each do |x|
        basis.each do |b|
          x = [x, x ^ b].min
          break if x == 0
        end
        basis << x if x != 0
      end
      seg[pos] = basis
      pos /= 2
    end
  end

  query_seg = lambda do |l, r|
    res = []
    l += size
    r += size
    while l < r
      if l % 2 == 1
        new_res = res.dup
        seg[l].each do |x|
          new_res.each do |b|
            x = [x, x ^ b].min
            break if x == 0
          end
          new_res << x if x != 0
        end
        res = new_res
        l += 1
      end
      if r % 2 == 1
        r -= 1
        new_res = res.dup
        seg[r].each do |x|
          new_res.each do |b|
            x = [x, x ^ b].min
            break if x == 0
          end
          new_res << x if x != 0
        end
        res = new_res
      end
      l /= 2
      r /= 2
    end
    res
  end

  output = []
  q.times do
    typ = input[ptr]
    ptr += 1
    if typ == '1'
      l = input[ptr].to_i - 1
      ptr += 1
      r = input[ptr].to_i - 1
      ptr += 1
      total = r - l + 1
      basis = query_seg.call(l, r + 1)
      rank = basis.size
      ans = (pow2[total] - pow2[total - rank]) % mod
      output << ans.to_s
    else
      i = input[ptr].to_i - 1
      ptr += 1
      x = input[ptr].to_i
      ptr += 1
      new_val = dp[x]
      update_seg.call(i, new_val)
    end
  end
  puts output.join("\n")
end

solve