题解 P4891 【序列】

Fading · 2018-09-23 18:28:24 · 题解

对于这个题目，我很想吐槽。

对于10%……什么鬼？只有5个点你说10%？？？？？？

还有这个数据也太水了吧，我暴力都可以碾标算了，还跑了rank\ 1？？？

我的暴力是O(n \times q\times log_2mod)的。

首先预处理初始的答案。

对于询问opt=0,x,y, 暴力修改[x,n]的每一个c[i],然后用乘法逆元修改答案(除原来的再乘新的),复杂度O(n\times log_2mod)

有一个剪枝,如果当前的c[i]>=y,直接退出循环,因为c[i+1]>=c[i]

对于询问opt=1,x,y, 直接修改b[x],然后用乘法逆元修改答案,复杂度O(log_2mod)

结果过了？？？这都可以过？？？？？？

我也很绝望啊。

代码如下:

#include<bits/stdc++.h>
#define ljc 1000000007
using namespace std;
int n,q,a[200005],b[200005],c[200005];
long long ans=1;
inline int read(){
    int x=0;char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x;
}
inline long long fast_pow(int a,int b,int p){
    long long s=1,t=a,k=b;
    while (k){
        if (k%2) s=s*t%p;
        t=t*t%p;
        k/=2;
    }
    return s;
}
inline long long max(long long a,long long b){
    if (a>b) return a;return b;
}
inline long long min(long long a,long long b){
    if (a<b) return a;return b;
}
int main(){
    n=read(),q=read();
    for (register int i=1;i<=n;i++){
        a[i]=read();
        c[i]=max(c[i-1],a[i]);
    }
    for (register int i=1;i<=n;i++){
        b[i]=read();
        ans=min(b[i],c[i])*ans%ljc;
    }
    int opt,x,y;
    for (register int i=1;i<=q;i++){
        opt=read(),x=read(),y=read();
        if (opt==1){
            if (b[x]<c[x]){
                ans=ans*fast_pow(b[x],ljc-2,ljc)%ljc;
                ans=ans*min(y,c[x])%ljc;
            }
            b[x]=y;
        }
        if (opt==0){
            a[x]=y;
            while (y>c[x]&&x<=n){
                if (c[x]<b[x]){
                    ans=ans*fast_pow(c[x],ljc-2,ljc)%ljc;
                    ans=ans*min(y,b[x])%ljc;
                }
                c[x++]=y;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}