线段树求助 9pts
查看原帖
线段树求助 9pts
400468
Aakkosetsumussa楼主2023/8/10 16:36
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1000005;
ll tagx[maxn<<2], tagw[maxn<<2], w[maxn], a[maxn];
ll n, m, opt, x, y, k, d;
inline void push_up(long long u) {
	w[u]=w[u*2]+w[u*2+1];
}
inline void build(long long u, long long L, long long R) {
	if(L==R) {
		w[u]=a[L];
		return;
	}
	long long M=(L+R)>>1;
	build(u*2, L, M);
	build(u*2+1, M+1, R);
	push_up(u);
}
inline long long S(long long ax, long long ay, long long len) {
	long long an=ax+ay*(len-1ll);
	return 1ll*(ax+an)*len/2;
}
inline void make_tag(long long u, long long len, ll x, ll y) {
	tagx[u]+=x, tagw[u]+=y;
	w[u]+=S(x, y, len);
}
inline void push_down(long long u, long long L, long long R) {
	long long M=(L+R)>>1;
	make_tag(u*2, M-L+1, tagx[u], tagw[u]);
	make_tag(u*2+1, R-M, tagx[u]+tagw[u]*(M-L+1), tagw[u]);
	tagx[u]=0, tagw[u]=0;
}
inline ll query(long long u, long long L, long long R, long long l, long long r) {
	if(l<=L&&R<=r) return w[u];
	else if(L<=r&&R>=l) {
		long long M=(L+R)>>1;
		push_down(u, L, R);
		return query(u*2, L, M, l, r)+query(u*2+1, M+1, R, l, r);
	} else return 0;
}
inline void update(long long u, long long L, long long R, long long l, long long r, long long x, long long y) {
	if(l<=L&&R<=r) make_tag(u, R-L+1, x, y);
	else if(L<=r&&R>=l) {
		long long M=(L+R)>>1;
		push_down(u, L, R);
		update(u*2, L, M, l, r, x, y);
		update(u*2+1, M+1, R, l, r, x+y*(M-L+1), y);
		push_up(u);
	}
}
main() {
	scanf("%lld %lld", &n, &m);
	for(long long i=1; i<=n; i++) scanf("%lld", &a[i]);
	build(1, 1, n);
	while(m--) {
		scanf("%d", &opt);
		if(opt==1) {
			scanf("%lld %lld %lld %lld", &x, &y, &k, &d);
			update(1, 1, n, x, y, k, d);
		} else {
			scanf("%lld", &x);
			printf("%lld\n", query(1, 1, n, x, x));
		}
	//	cout<<w[1]<<endl;
	}
	return 0;
}
2023/8/10 16:36
加载中...