icontofig | 发布于 2019-08-29 22:08:21 | 阅读量 488 | 线段树
发布于 2019-08-29 22:08:21 | 线段树

题目大意

给定一个序列,有两个操作:

1.询问l---r之间所有数按题目中格式公式的计算求和。

2.更改序列某个位置的值。

题解

其实这题还是蛮简单的……我零基础的队友30s就像出来了(比我快了一些)

这题直接维护区间和是不行的,我们看到询问的操作中的公式跟数的位置和询问区间长度都有关系。

那么我们现在要想的就是如何让区间和与数的位置变成无关的式子。

注意到对于位置 i,有n - i + 1 - n - r,即为我们要求的区间中 位置 i的数字对应的位置系数。

所以我们可以用线段树维护两个值,一个表示 a[i]*(n-i+1)的和,另一个表示a[i]的和。

询问的时候用前一个值对应的区间询问减去后一个值对应的区间询问的(n-r)倍就是我们需要询问的东西了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
typedef long long ll;
struct tree{
	ll sum1,sum2;
	int l,r;
}tr[maxn<<2];
ll a[maxn];
int n,q;
void push_up(int now){
	tr[now].sum1 = tr[now<<1].sum1 + tr[now<<1|1].sum1;
	tr[now].sum2 = tr[now<<1].sum2 + tr[now<<1|1].sum2;
	return;
}
void build(int now,int l,int r){
	tr[now].l = l;
	tr[now].r = r;
	tr[now].sum1 = tr[now].sum2 = 0;
	if(l == r){
		tr[now].sum1 = a[l];
		tr[now].sum2 = a[l] * (n - l + 1);
		return;
	}
	int mid = (l + r) >> 1;
	build(now<<1,l,mid);
	build(now<<1|1,mid+1,r);
	push_up(now);
	return;
}
void update(int now,int pos){
	if(tr[now].l == tr[now].r){
		tr[now].sum1 = a[pos];
		tr[now].sum2 = a[pos] * (n - pos + 1);
		return;
	}
	int mid = (tr[now].l + tr[now].r) >> 1;
	if(pos <= mid)update(now<<1,pos);
	else update(now<<1|1,pos);
	push_up(now);
	return;
}
ll query1(int now,int l,int r){
	if(tr[now].l >= l && tr[now].r <= r){
		return tr[now].sum1;
	}
	ll ret = 0;
	int mid = (tr[now].l + tr[now].r) >> 1;
	if(l <= mid) ret += query1(now<<1,l,r);
	if(r > mid)ret += query1(now<<1|1,l,r);
	return ret;
}
ll query2(int now,int l,int r){
	if(tr[now].l >= l && tr[now].r <= r){
		return tr[now].sum2;
	}
	ll ret = 0;
	int mid = (tr[now].l + tr[now].r) >> 1;
	if(l <= mid)ret += query2(now<<1,l,r);
	if(r > mid)ret += query2(now<<1|1,l,r);
	return ret;
}
int opt,l,r;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for(int i = 1;i <= n;++i){
		cin >> a[i];
	}
	build(1,1,n);
	ll ans;
	while(q--){
		cin >> opt >> l >> r;
		if(opt == 1){
			ans = query2(1,l,r) - query1(1,l,r) * (n - r);
			cout << ans << "\n";
		}
		else{
			a[l] = r;
			update(1,l);
		}
	}
	return 0;
}




内容更新于: 2019-08-29 22:08:37
链接地址: http://blog.leanote.com/post/icontofig/2018

上一篇: 2018 ICPC 徐州赛站网络赛 B.BE,GE or NE 博弈论+记忆化搜索

下一篇: 2018-2019 ACM-ICPC, Asia Shenyang Regional Contest K. Let the Flames Begin 经典约瑟夫问题 + 思维

488 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航