C++11(clang++ 3.9) 解法, 执行用时: 116ms, 内存消耗: 4200K, 提交时间: 2019-03-16 12:59:12

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;

typedef long long LL;

const int N=100005;
const int MOD=1000000007;

int n,m,a[N],s[N],ny[N];
struct tree{int s,tag;}t[N*4];
set<int> se;

int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

void build(int d,int l,int r)
{
    t[d].tag=1;
    if (l==r) {t[d].s=s[l];return;}
    int mid=(l+r)/2;
    build(d*2,l,mid);build(d*2+1,mid+1,r);
    t[d].s=(t[d*2].s+t[d*2+1].s)%MOD;
}

void pushdown(int d)
{
    if (t[d].tag==1) return;
    int w=t[d].tag;t[d].tag=1;
    t[d*2].s=(LL)t[d*2].s*w%MOD;t[d*2].tag=(LL)t[d*2].tag*w%MOD;
    t[d*2+1].s=(LL)t[d*2+1].s*w%MOD;t[d*2+1].tag=(LL)t[d*2+1].tag*w%MOD;
}

void ins(int d,int l,int r,int x,int y,int z)
{
    if (l<r) pushdown(d);
    if (l==x&&r==y) {t[d].s=(LL)t[d].s*z%MOD;t[d].tag=(LL)t[d].tag*z%MOD;return;}
    int mid=(l+r)/2;
    if (y<=mid) ins(d*2,l,mid,x,y,z);
    else if (x>mid) ins(d*2+1,mid+1,r,x,y,z);
    else ins(d*2,l,mid,x,mid,z),ins(d*2+1,mid+1,r,mid+1,y,z);
    t[d].s=(t[d*2].s+t[d*2+1].s)%MOD;
}

int query(int d,int l,int r,int x,int y)
{
    if (l<r) pushdown(d);
    if (l==x&&r==y) return t[d].s;
    int mid=(l+r)/2;
    if (y<=mid) return query(d*2,l,mid,x,y);
    else if (x>mid) return query(d*2+1,mid+1,r,x,y);
    else return (query(d*2,l,mid,x,mid)+query(d*2+1,mid+1,r,mid+1,y))%MOD;
}

int main()
{
    ny[0]=ny[1]=1;
    for (int i=2;i<=10000;i++) ny[i]=(LL)(MOD-MOD/i)*ny[MOD%i]%MOD;
    n=read();m=read();s[0]=2;
    for (int i=0;i<n-1;i++) s[0]=(LL)s[0]*3%MOD;
    for (int i=1;i<=n;i++)
    {
        a[i]=read();
        s[i]=(LL)s[i-1]*(a[i]?a[i]:1)%MOD*ny[3]%MOD;
        if (!a[i]) se.insert(i);
    }
    s[n]=(LL)s[n]*3%MOD*ny[2]%MOD;
    build(1,1,n);
    while (m--)
    {
        int x=read(),y=read();
        if (!a[x]) se.erase(x);
        else ins(1,1,n,x,n,ny[a[x]]);
        a[x]=y;
        if (!a[x]) se.insert(x);
        else ins(1,1,n,x,n,a[x]);
        int p;
        if (!se.size()) p=n;
        else p=*se.begin()-1;
        printf("%d\n",query(1,1,n,1,p));
    }
    return 0;
}