线段树45pts求调
查看原帖
线段树45pts求调
623219
StrSeeker楼主2024/2/27 21:57
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 200005;
int n, m, a[MAXN];
int p;
struct Segment_Tree {
#define ls (id << 1)
#define rs (id << 1 | 1)
#define mid ((l + r) >> 1)
	struct Segment {
		int l, r;
		int len, a, d;
	}seg[MAXN << 2];
	void build(int id, int l, int r) {
		seg[id] = { l, r, r - l + 1, 0, 0 };
		if (l == r) return;
		build(ls, l, mid), build(rs, mid + 1, r);
	}
	void change(int id,int a,int d) {
		seg[id].a += a;
		seg[id].d += d;
	}
	void pushdown(int id) {
		if (seg[id].a == 0 || seg[id].l == seg[id].r) return;
		change(ls, seg[id].a, seg[id].d);
		change(rs, seg[id].a + seg[id].d * seg[ls].len, seg[id].d);
		seg[id].a = seg[id].d = 0;
	}
	void modify(int id, int l, int r,int a,int d) {
		pushdown(id);
		if (l > seg[id].r || r < seg[id].l) return;
		if (l <= seg[id].l && seg[id].r <= r) {
			change(id, a + (seg[id].l - l) * d, d);
			return;
		}
		modify(ls, l, r, a, d);
        modify(rs, l, r, a, d);
	}
	int get(int id, int x) {
		pushdown(id);
		if (x > seg[id].r || x < seg[id].l) return 0LL;
		if (x == seg[id].l && x == seg[id].r) return seg[id].a;
		return get(ls, x) + get(rs, x);
	}
}sgt;
signed main() 
{
	cin >> n >> m;
	sgt.build(1, 1, n);
	for(int i=1;i<=n;i++)
	{
	    int num;
	    cin>>num;
	    sgt.modify(1,i,i,num,1);
	}
// 	sgt.build(1, 1, n);
	while (m--) 
	{
		int op; 
		cin >> op;
		if (op == 1) 
        {
			int l, r, a, d; 
            cin >> l >> r >> a >> d;
			sgt.modify(1, l, r, a, d);
		}
		else 
        {
			int x; 
            cin >> x;
			cout << sgt.get(1, x) << endl;
		}
	}
	return 0;
}
2024/2/27 21:57
加载中...