Precision

The first line contains two integers $n, q ~ (1 \leq n, q \leq 10^5)$ denoting the length of sequence and the count of operations.

The second line contains n integers $a_i ~ (1 \leq a_i \leq 10^4)$ denoting the thickness of i-th position.

The third line contains n integers $c_i ~ (1 \leq c_i \leq 10^4)$ denoting the volatility of i-th position.

Following q lines, each line contains three integers:

- 0 p v, modify $c_p$ to $c_p + v ~ (1 \leq p \leq n, -10 \leq v \leq 10)$ .
- 1 l r, calculate the precision value $\frac{1}{A}$ of interval $[l,r] ~ (1 \leq l, r \leq n)$

C++11(clang++ 3.9) 解法, 执行用时: 63ms, 内存消耗: 4444K, 提交时间: 2020-06-13 16:32:10

#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define LL long long
LL n,q,a[N],c[N],f[N],t[N],o,x,y;
LL lowbit(LL x){return x&-x;}
void change(LL x,LL c){while(x<N)t[x]+=c,x+=lowbit(x);}
LL ask(LL x){LL res=0;while(x)res+=t[x],x-=lowbit(x);return res;}
int main()
{
	scanf("%lld%lld",&n,&q);
	for(LL i=1;i<=n;i++)
	  scanf("%lld",&a[i]);
	for(LL i=1;i<=n;i++)
	  scanf("%lld",&c[i]),f[i]=a[i]*c[i];
	for(LL i=1;i<=n;i++)
	  change(i,f[i]);
	while(q--)
	  {
	  scanf("%lld%lld%lld",&o,&x,&y);
	  if(o)printf("%lld\n",4ll*(ask(y)-ask(x-1)));
	  else change(x,a[x]*y);
	  }
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 85ms, 内存消耗: 4968K, 提交时间: 2020-06-16 12:11:25

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) (x&(-x))
int n,m,a[100005];
ll c[100005];
void update(int x,ll w){
	int i;
	for (i=x;i<=n;i+=lowbit(i)) c[i]+=w;
}
ll getsum(int x){
	int i; ll res=0;
	for (i=x;i;i-=lowbit(i)) res+=c[i];
	return res;
}
int main(){
	int i,x,y,z;
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++) scanf("%d",&a[i]);
	memset(c,0,sizeof(c));
	for (i=1;i<=n;i++){
		scanf("%d",&x);
		update(i,a[i]*x);
	}
	while (m--){
		scanf("%d%d%d",&z,&x,&y);
		if (!z) update(x,a[x]*y);
		else printf("%lld\n",(getsum(y)-getsum(x-1))*4);
	}
	return 0;
}

详情