SHOI2016 随机序列（线段树）

发表于 |
字数统计: 966字 | 阅读时长 ≈ 5min

问题描述

你的面前有 $n$ 个数排成一行，分别为 $a_1, a_2, \dots, a_n$。你打算在每相邻的两个 $a_i$ 和 $a_{i+1}$ 间都插入一个加号、减号或者乘号。那么一共有 $3^{n-1}$ 种可能的表达式。

你对所有可能的表达式的值的和非常感兴趣。但这毕竟太简单了，所以你还打算支持一个修改操作，可以修改某个 $a_i$ 的值。

你能够编写一个程序对每个修改都输出修改完之后所有可能表达式的和吗？注意，修改是永久的，也就是说每次修改都是在上一次修改的基础上进行，而不是在最初的表达式上进行。

输入格式

第一行包含两个正整数 $n$ 和 $Q$，为数的个数和询问的个数。
第二行包含 $n$ 个非负整数，依次表示 $a_1, a_2, \dots, a_n$。
接下来 $Q$ 行，每行包含两个非负整数 $t$ 和 $v$，表示要将 $a_t$ 修改为 $v$，其中 $1 \leq t \leq n$。

保证对于 $1 \leq j \leq n, 1 \leq i \leq Q$，都有 $a_j, v_i \leq 10^4$。

输出格式

输出 $Q$ 行。对于每个修改输出一行，包含一个整数，表示修改之后所有可能表达式的和，对 $10^9 + 7$ 取模。

样例输入

1
2
3
4
5
6
7
5 5
9384 887 2778 6916 7794
2 8336
5 493
3 1422
1 28
4 60

样例输出

1
2
3
4
5
890543652
252923708
942282590
228728040
608998099

提示

Case # $n, Q$
1, 2 $\leq 10$
3 - 5 $\leq 1\,000$
6 - 10 $\leq 100\,000$

观察一下能够发现，会对答案产生贡献的只有第一个非乘号的位置之前的部分，也就是开始的连续一段乘号

那么考虑用线段树维护，每个点存三个值，区间内的答案，区间内的总方案数，区间乘积

合并的时候讨论左右区间之间放什么，如果放加减，那么贡献是左区间答案乘以右区间方案数

如果放乘号，当左区间全放乘号时，贡献是右区间答案乘以左区间乘积和，否则还是左区间答案乘右区间方案数

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 100005
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
inline int _R()
{
    char t=GC;int x=0;
    while(t<48||t>57)t=GC;
    for(;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
    return x;
}
const int mod=1e9+7;
int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
int sub(int a,int b){a-=b;return a<0?a+mod:a;}
int mul(int a,int b){return 1ll*a*b%mod;}
int n,q,a[N];
struct node
{
    node *ls,*rs;
    int b,l,m;
}seg[N<<1],*rt,*tl,*null;
void Init()
{
    rt=tl=null=seg;
    null->ls=null->rs=null;
}
void update(node *p)
{
    node *l=p->ls,*r=p->rs;
    p->l=add(mul(mul(l->l,r->b),3),mul(l->m,sub(r->l,r->b)));
    p->m=mul(l->m,r->m);
}
void build(node *&p,int l,int r)
{
    p=++tl;p->ls=p->rs=null;
    if(l==r){p->l=p->m=a[l];p->b=1;return;}
    int mid=l+r>>1;
    build(p->ls,l,mid);
    build(p->rs,mid+1,r);
    update(p);
    p->b=mul(3,mul(p->ls->b,p->rs->b));
}
void modify(node *p,int l,int r,int x,int d)
{
    if(l==r){p->l=p->m=d;return;}
    int mid=l+r>>1;
    if(x<=mid)modify(p->ls,l,mid,x,d);
    else modify(p->rs,mid+1,r,x,d);
    update(p);
}
int main()
{
    int i,j,k,x,y;
    n=_R();q=_R();
    for(i=1;i<=n;i++)a[i]=_R();
    Init();build(rt,1,n);
    for(i=1;i<=q;i++)
    {
        x=_R();y=_R();
        modify(rt,1,n,x,y);
        printf("%d\n",rt->l);
    }
}