小沙的算数

小沙的算数

namespace std;typedef long long ll;const int mod = 1e9 + 7;const int N = 1e6 + 10;ll n, q;char str[N];ll a[N], s[N];ll f[N];ll qmi(ll a, ll b) { ll ans = 1; while (b) { if (b &1) ans = ans * a % mod; a = a * a % mod; b >>= 1; } return ans;}ll find (ll tar) { if (tar == f[tar]) return tar; return f[tar] = find(f[tar]);}void init () { for (int i =1; i <= n; i ++) f[i] = i;}int main () { cin >> n >> q; cin >> (str + 1); init(); for (int i = 1; i<= n; i ++) { cin >> a[i]; s[i] = a[i]; } for (int i = 1; i < n; i ++) { if (str[i] == '*') { ll fa = find(i), fa2 =find(i + 1); f[fa] = fa2; s[fa2] = s[fa2] * s[fa] % mod; } } ll res = 0; for (int i =1; i<= n; i++) if (find(i) == i) (res += s[i]) %= mod; while (q --) { ll x, y; cin >> x >> y; ll fa = find(x); res = (res - s[fa] + mod) % mod; s[fa] = s[fa] * qmi(a[x], mod - 2) % mod; a[x] = y; s[fa] = s[fa] * y% mod; (res += s[fa]) %= mod; cout << res << endl; } return 0;}

没看出这是并查集可以处理的问题。这里主要是查询整个表达式的值，然后修改，又要修改整个表达式的值，一开始是想前缀和差分。但是复杂度太高，不可实现。 这里通过并查集实现了整个表达式的值的修改和查询

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。