题解 | #小沙的算数#

F.线段树平衡树？太麻烦了,并查集！

观察可以发现,用乘号连在一起的可以连一条边,加号会分开一个又一个区间使他们互不影响,那就使用乘号连起来的结点合并,将所有数相乘的结果存储在父亲结点,用now[i]表示以i作为父亲结点时该联通块相乘的结果,当改变数x的结果时可以明显发现,改变的值将会被放大now[i]/a[x]倍,那就将所有结果先算出来放在sum里,然后将结果+放大后改变的值就是改变后的sum了

除以用乘法逆元解决,其次注意取余后的sum可能比原值小,需要先+mod%mod否则可能出负数

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1000000007;
int fa[2000015];
int now[2000015];
int a[2000015];
int n,m,sum;
int has[2000015];
string ys;
int find(int x)
{
    return x==fa[x]?x:fa[x] = find(fa[x]);
}
void merge(int x,int y)
{
	now[find(x)] = (now[find(x)]*now[find(y)])%mod;
    now[find(x)]%=mod;
    fa[find(y)] = find(x);
}
int qmi(int a, int b, int p){int res = 1 % p;a %= p;while (b > 0){if(b & 1) res = res * a % p;a = a * a % p;b >>= 1;}return res;}
signed main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i = 1;i<=n+10;++i)
        fa[i] = i;
    cin>>ys;
    for(int i = 1;i<=n;++i)
    {
        cin>>a[i];
        a[i]%=mod;
        now[i] = a[i];
        if(i>1&&ys[i-2]=='*')
            merge(i,i-1);
    }
    for(int i = 1;i<=n;++i)
    {
        if(!has[find(i)])
        {
            sum = (sum+now[find(i)])%mod;
            has[find(i)] = 1;
            sum%=mod;
        }
    }
    for(int i = 1;i<=m;++i)
    {
        int x,y;
        cin>>x>>y;
        int c = y-a[x];
        int xx = find(x);
        sum=(sum+mod)%mod;
        sum = (sum+mod+(c*((now[xx]*qmi(a[x],mod-2,mod))%mod)%mod)%mod)%mod;
        cout<<sum%mod<<endl;
        now[xx] = (now[xx]*qmi(a[x],mod-2,mod)%mod)*y%mod;
        a[x] = y%mod;
    }
    return 0;
}