https://www.lydsy.com/JudgeOnline/problem.php?id=4597
https://www.luogu.org/problemnew/show/P4340
妄图直接暴力维护一堆东西，以直接维护题目要求的值（具体见代码...）
最后花了2个小时维护完了，A掉了，然而好像常数比别人大一倍？
上网搜题解，发现大部分东西都可以抵消掉？？回想维护过程中，好像有一堆抵消掉的东西？
看来即使可以暴力维护，也还是要多观察题目性质...
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const ll md=1e9+;
ll n,q;
ll a[];
ll pw3[];
const ll N=;
#define lc (num<<1)
#define rc (num<<1|1)
ll d1[N],d2[N],d3[N],d4[N],d5[N];
//d1:区间乘积
//d2:区间和
//d3:除了全部是乘号外，所有选择方案靠左边全是乘号一段的积的和
//d4:除了全部是乘号外，...靠右边...(带符号)
//d5:答案
//维护过程中发现d4必定为0...
/*
举例：1,2,3
1+2+3,1+2-3,1+2*3,
1-2+3,1-2-3,1-2*3,
1*2+3,1*2-3,1*2*3
d3应当维护1*6+1*2*2=10
d4应当维护3*3-3*3+2*3-2*3=0
*/
void upd(ll l,ll r,ll num)
{
d1[num]=d1[lc]*d1[rc]%md;
d2[num]=(d2[lc]+d2[rc])%md;
ll mid=l+((r-l)>>);
d3[num]=(d3[lc]*pw3[r-mid]%md+d1[lc]**pw3[r-(mid+)]%md
+d1[lc]*d3[rc]%md)%md;
d4[num]=(d4[rc]*pw3[mid-l+]%md//+d1[rc]*2*pw3[mid-l]%md
+d1[rc]*d4[lc]%md)%md;
ll d4l=(d4[lc]+d1[lc])%md,d3r=(d3[rc]+d1[rc])%md;
/*
d5[num]=(2*(r-mid)*d5[lc]%md+(r-mid)*((d5[lc]-d4l+md)%md)%md
+(mid-l+1)*((d5[rc]-d3r+md)%md)%md
+d4l*d3r%md)%md;
*/
ll m=pw3[mid-l],n=pw3[r-(mid+)];
/*
d5[num]=(2*(r-mid)*d5[lc]%md+2*(mid-l+1)*d5[rc]%md
+pw3[mid-l]*(md-2)%md*d3r%md
+(r-mid)*((d5[lc]-d4l+md)%md)%md
+(mid-l+1)*((d5[rc]-d3r+md)%md)%md
+d4l*d3r%md)%md;
*/
d5[num]=(*n*d5[lc]%md+*m*d5[rc]%md
+m*(md-)%md*d3r%md
+n*((d5[lc]-d4l+md)%md)%md
+m*((d5[rc]-d3r+md)%md)%md
+d4l*d3r%md)%md; /*
d5[num]=(2*(r-mid)*d5[lc]%md+2*(mid-l+1)*d5[rc]%md
+pw3[mid-l]*(md-2)%md*d3r%md
+(r-mid)*((d5[lc]-d4l+md)%md)%md
+
printf("1t%lld %lld %lld %lld %lld %lld %lld\n",l,r,d1[num],d2[num],
d3[num],d4[num],d5[num]);
printf("2t%lld %lld %lld\n",(r-mid)*d5[lc]%md+(mid-l+1)*d5[rc]%md,
(r-mid)*d5[lc]%md+(mid-l+1)*d5[rc]%md+pw3[mid-l]*(md-2)%md*d3r%md,
(r-mid)*((d5[lc]-d4l+md)%md)%md
+(mid-l+1)*((d5[rc]-d3r+md)%md)%md
+d4l*d3r%md);
*/
}
void pre(ll l,ll num,ll x)
{
d1[num]=x;
d2[num]=x;
d3[num]=d4[num]=;
d5[num]=x;
}
void build(ll l,ll r,ll num)
{
if(l==r) {pre(l,num,a[l]);return;}
ll mid=l+((r-l)>>);
build(l,mid,lc);build(mid+,r,rc);
upd(l,r,num);
}
void setx(ll L,ll x,ll l,ll r,ll num)
{
if(l==r) {pre(l,num,x);return;}
ll mid=l+((r-l)>>);
if(L<=mid) setx(L,x,l,mid,lc);
else setx(L,x,mid+,r,rc);
upd(l,r,num);
}
int main()
{
ll i,x,y;
pw3[]=;
for(i=;i<=;i++)
pw3[i]=pw3[i-]*%md;
scanf("%lld%lld",&n,&q);
for(i=;i<=n;i++) scanf("%lld",&a[i]);
build(,n,);
//printf("%lld %lld %lld %lld %lld",d1[1],d2[1],d3[1],d4[1],d5[1]);
while(q--)
{
scanf("%lld%lld",&x,&y);
setx(x,y,,n,);
printf("%lld\n",d5[]);
}
return ;
}