微信制作企业网站,江苏国龙翔建设网站,加盟创业商机网,天涯论坛网站建设题意 #xff1a; 描述 现在有一个有n个元素的数组a1, a2, ..., an。 记f(i, j) ai * ai1 * ... * aj。 初始时#xff0c;a1 a2 ... an 0#xff0c;每次我会修改一个ai的值#xff0c;你需要实时反馈给我 ∑f(i, j) (1 i j n) 的值 mod 10007。 输入…题意 描述 现在有一个有n个元素的数组a1, a2, ..., an。 记f(i, j) ai * ai1 * ... * aj。 初始时a1 a2 ... an 0每次我会修改一个ai的值你需要实时反馈给我 ∑f(i, j) (1 i j n) 的值 mod 10007。 输入 第一行包含两个数n(1n100000)和q(1q500000)。 接下来q行每行包含两个数i, x代表我把ai的值改为了x。 输出 分别输出对应的答案一个答案占一行。 代码: #includeiostream
#includecstdio
#includecstdlib
#includecstring
#includequeue
#includealgorithm
#includecmath
#includemap
using namespace std;
#define INF 0x7fffffff
struct node{int l;int r;long long value; //al ~ ar 的乘积long long lsum; //所有前缀积之和 long long rsum; //所有后缀积之和 long long ans; //∑ f(i, j) (1 i j n)
}a[400010]; void buildtree(int i,int l,int r){a[i].l l;a[i].r r;a[i].value 0;a[i].lsum 0 ;a[i].rsum 0;a[i].ans 0;if(l r)return ;int mid (l r) / 2;buildtree(i 1,l,mid);buildtree((i 1) 1,mid1,r);
}void update(int no,int k,int b){if(a[no].l a[no].r){a[no].value b;a[no].lsum b ;a[no].rsum b;a[no].ans b;return ;}int mid (a[no].l a[no].r) / 2;if(kmid) update(no1,k,b); else update((no1)1,k,b);a[no].value (a[no1].value * a[no*21].value)%10007; a[no].lsum (a[no*2].lsum a[no*2].value*a[no*21].lsum)%10007; a[no].rsum (a[no*21].rsum a[no*21].value*a[no*2].rsum)%10007;a[no].ans (a[no*2].ans a[no*21].ans a[no*2].rsum * a[no*21].lsum)%10007;
}int main(){int i,j,n,q,k,b;while(scanf(%d%d,n,q) 2){buildtree(1,1,n);for(i1;iq;i){scanf(%d%d,k,b);update(1,k,b);printf(%d\n,a[1].ans%10007);}} return 0;
} 转载于:https://www.cnblogs.com/jxgapyw/p/4782721.html
