题解 P4891 【序列】

· · 题解

关于这一道题的话。。。

我们先从题干看起，题目要求更改A序列或者B序列，最后求一个min（Bi，Ci）的总乘积，其实要修改B的话很容易，O(1)即可。但是要修改A的话，会导致C序列大幅改变。于是这时候就有同学站出来说要用线段树了，但是答案是要一个总乘积的，就算对于C序列的修改时间复杂度降下去了，求积的部分也会很难受。

于是我们可以这么想，要是可以维护这个答案就好了，然后这道题就变成一道简单的乘法逆元版子题了。

首先，我们建立一个mul数组来维护每一位的min(Bi,Ci),sum为初始的答案。

在修改B序列时，我们直接更改B[i]，然后将新的min(Bi,Ci)与原来的mul[i]比较，若有不同，则将原来的除掉，将新的乘上，然后更新mul数组。

对于A序列的修改，我们从要修改的第i位开始，把比更改的值小的C[i]全部更新成修改后的值，之后就是照葫芦画瓢。与B序列修改一样的处理方式。

当然，这道题是要模的，由于计算中涉嫌除法运算，不能直接模，所以我们就可以运用乘法逆元

             (a/b) mod p == (a*b^(p-2)) mod p

下面是AC代码

#include<cstdio>
#include<algorithm>
using namespace std;
long long n,q;
long long a[100010],b[100010],c[100010],sum=1,mul[100010];
const long long mod = 1e9+7;

long long ksm(long long a){
    long long summ = 1,b = mod-2;
    while(b){
        if(b&1)summ=(summ*a)%mod;
        a = (a*a)%mod;
        b>>=1;
    }
    return summ;
}

int main(){
    scanf("%lld%lld",&n,&q);
    for(long long i = 1; i <= n; i++)scanf("%lld",&a[i]);
    for(long long i = 1; i <= n; i++)scanf("%lld",&b[i]);
    for(long long i = 1; i <= n; i++)c[i] = max(c[i-1],a[i]);
    for(long long i = 1; i <= n; i++)sum=(sum*min(c[i],b[i]))%mod,mul[i]=min(c[i],b[i]);
    while(q--){
        long long op,id,val;
        scanf("%lld%lld%lld",&op,&id,&val);
        if(op==1){
            b[id] = val%mod;
            if(min(c[id],b[id])!=mul[id]){
                sum = ((sum*ksm(mul[id])%mod)*min(c[id],b[id]))%mod;
                mul[id] = min(c[id],b[id]);
            }
        }
        else {
            while(c[id]<val){
                if(id>n)break;
                c[id] = val%mod;
                if(min(c[id],b[id])!=mul[id]){
                    sum = ((sum*ksm(mul[id])%mod)*min(c[id],b[id]))%mod;
                    mul[id] = min(c[id],b[id]);
                }
                id++;
            }

        }
        printf("%lld\n",sum%mod);
    }
}