You are viewing a single comment's thread. Return to all 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'; } } }
Seems like cookies are disabled on this browser, please enable them to open this website
Polynomial Division
You are viewing a single comment's thread. Return to all comments →
the method is easy, but the debugging took me forever. O(n + qlog(n)) using fenwick trees