题意：

思路：

用线段树解决，每个节点需要设置4个变量，sum记录答案，all记录整个区间的乘积，pre记录该区间内所有前缀的和，suf记录该区间内所有后缀的和。

举个例子，比如现在要合并{a,b,c,d}和{x,y,z,w}这两个区间，那么新增的答案有哪些呢？

有abcdx（省去乘号)，abcdxy,abcdxyz,abcdxyzw，bcdxyzw，cdxyzw，dxyzw。这些就是{a,b,c,d}的所有后缀×{x,y,z,w}所有前缀。

1 #include
     
       2 #include
      
        3 using namespace std; 4 const int maxn = 100000+5; 5 const int mod = 10007; 6 typedef long long ll; 7  8 int n,q; 9 10 struct node11 {12     int l,r;13     ll sum, pre, suf, all;14 }t[maxn<<4];15 16 17 void PushUp(int o)18 {19     t[o].all=(t[o<<1].all*t[o<<1|1].all)%mod;20     t[o].sum=((t[o<<1].sum+t[o<<1|1].sum)%mod+(t[o<<1].suf*t[o<<1|1].pre)%mod)%mod;21     t[o].pre=(t[o<<1].pre+(t[o<<1].all*t[o<<1|1].pre)%mod)%mod;22     t[o].suf=(t[o<<1|1].suf+(t[o<<1|1].all*t[o<<1].suf)%mod)%mod;23 }24 25 void build(int l, int r, int o)26 {27     t[o].l = l;28     t[o].r = r;29     t[o].sum = t[o].pre = t[o].suf = t[o].all = 0;30     if(l==r)  return;31     int mid = (l+r)>>1;32     build(l,mid,o<<1);33     build(mid+1,r,o<<1|1);34     PushUp(o);35 }36 37 void update(int l, int r, int x, int v, int o)38 {39     if(t[o].l == x && t[o].l==t[o].r)40     {41         t[o].sum = t[o].pre = t[o].suf = t[o].all = v;42         return;43     }44     int mid = (l+r)>>1;45     if(x<=mid)  update(l,mid,x,v,o<<1);46     else update(mid+1,r,x,v,o<<1|1);47     PushUp(o);48 }49 50 int main()51 {52     //freopen("in.txt","r",stdin);53     scanf("%d%d",&n,&q);54     build(1,n,1);55     while(q--)56     {57         ll x,y;58         scanf("%lld%lld",&x,&y);59         update(1,n,x,y%mod,1);60         printf("%lld\n",t[1].sum);61     }62     return 0;63 }