线段树求调
查看原帖
线段树求调
1333328
Co_Ce楼主2025/7/24 20:06
#include <bits/stdc++.h>
#define int long long

using namespace std;

constexpr int N = 5e5 + 10;

int n, m;

int a[N];

int opt;

int x, y, k;

int ls(int x) {
	return x << 1;
}

int rs(int x) {
	return x << 1 + 1;
}

struct node {
	int L, R;
	int w;
	int tag;
}tree[4 * N];

void pushup(int u) {
	tree[u].w = tree[ls(u)].w + tree[rs(u)].w;
}

void build(int u,int L, int R) {
	if(L == R) {
		tree[u].w = a[L];
		return ;
	}
	int mid = (L + R) / 2;
	build(ls(u), L, mid);
	build(rs(u), mid + 1, R);
	pushup(u);
}

int query1(int u, int L, int R, int p) {
	if(L == R) {
		return tree[u].w;
	}
	else {
		int mid = (L + R) / 2;
		if(mid >= p) {
			return query1(ls(u), L, mid, p);
		}
		else {
			return query1(rs(u), mid + 1, R, p);
		}
	}	
}

bool inrange(int L, int R, int l, int r) {
	return (l <= L) && (R <= r);
}

bool outofrange(int L, int R, int l, int r) {
	return (r < L) || (l > R);
}

void maketag(int u, int len, int x) {
	tree[u].tag += x;
	tree[u].w += len * x;
}

void pushdown(int u, int L, int R) {
	int mid = (L + R) / 2;
	maketag(ls(u), mid - L + 1, tree[u].tag);
	maketag(rs(u), R - mid, tree[u].tag);
	tree[u].tag = 0;
}

void update(int u, int L, int R, int l, int r, int k) {
	if(inrange(L, R, l, r)) {
		maketag(u, R - L + 1, k);
	}
	else if(!outofrange(L, R, l, r)) {
		int mid = (L + R) / 2;
		pushdown(u, L, R);
		update(ls(u), L, mid, l, r, k);
		update(rs(u), mid + 1, R, l, r, k);
		pushup(u);
	}
}

signed main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i];
	build(1, 1, n);
	while(m--) {
		cin >> opt;
		if(opt == 1) {
			cin >> x >> y >> k;
			update(1, 1, n, x, y, k);
		}
		else if(opt == 2) {
			cin >> x;
			cout << query1(1, 1, n, x) << "\n";
		}
	}
	return 0;
} 
2025/7/24 20:06
加载中...