• + 0 comments

    the method is easy, but the debugging took me forever. O(n + qlog(n)) using fenwick trees

    long long mod = 1000000007;
    
    long long extended_gcd(long long a, long long b, long long& x, long long& y) {
        if (a == 0) {
            x = 0;
            y = 1;
            return b;
        }
        long long x1, y1;
        long long gcd = extended_gcd(b % a, a, x1, y1);
        x = y1 - (b / a) * x1;
        y = x1;
        return gcd;
    }
    
    long long inverse(long long a, long long p) {
        long long x, y;
        long long g = extended_gcd(a, p, x, y);
        if (g != 1) {
            std::cout << "Inverse doesn't exist";
            return -666;
        } else {
            long long res = (x % p + p) % p;
            return res;
        }
    }
    
    void update(vector<long long>& fenwick, int i, long long value) {
        while (i < fenwick.size()) {
            fenwick[i] = (fenwick[i] + value) % mod;
            i = i + (i & -i);
        }
    }
    
    long long access(const vector<long long>& fenwick, int i) {
        long long sum = 0;
        while (i > 0) {
            sum = (sum + fenwick[i]) % mod;
            i = i - (i & -i);
        }
        return sum;
    }
    
    int main()
    {
        long long n, a, b, q, c, h, k, l;
        vector<long long> C;
        vector<long long> Xpower;
        vector<long long> fenwick = {0};
        cin >> n >> a >> b >> q;
        long long x = (mod - ((inverse(a, mod) * b) % mod)) % mod, temp = 1;
    
        for (int i=0; i < n; i++) {
            cin >> c;
            C.push_back(c);
            Xpower.push_back(temp);
            fenwick.push_back((c*temp) % mod);
            temp = (temp * x) % mod;
        }
        
        for (int i = 1; i < n + 1; i++) {
            int J = i + (i & -i);
            if (J < n + 1) fenwick[J] = (fenwick[J] + fenwick[i]) % mod;
        }
        
        for (int i=1; i <= q; i++) {
            cin >> h >> k >> l;
            if (h == 1) {
                update(fenwick, k + 1, (l*Xpower[k]) % mod - (C[k]*Xpower[k]) % mod );
                C[k] = l;
            }
            else if (h == 2) {
                long long partialSum = (access(fenwick, l + 1) - access(fenwick, k)) % mod;
                if (partialSum != 0 or (x == 0 and C[k] != 0)) cout << "No" << '\n';
                else cout << "Yes" << '\n';
            }
        }
    }