玄关 求调
  • 板块灌水区
  • 楼主CZ_Yang
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/8/5 16:26
  • 上次更新2024/8/5 17:08:31
查看原帖
玄关 求调
1178154
CZ_Yang楼主2024/8/5 16:26

P1438 无聊的数列 代码得了十分甚至九分but找不到错(

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100010;
int a[N], n, m;
struct TreeNode {
	int l, r, sum, tag=0;
} tr[N<<2];

void build (int p, int l, int r) {
	tr[p].l = l;
	tr[p].r = r;
	if (l == r) {
		tr[p].sum = a[l];
		return;
	}
	int mid = l+r>>1;
	build (p<<1, l, mid);
	build (p<<1|1, mid+1, r);
	tr[p].sum = tr[p<<1].sum + tr[p<<1|1].sum;
}

void pushdown (int p) {
	if(tr[p].tag) {
		int mid = tr[p].l+tr[p].r>>1, le = p<<1, ri = p<<1|1;
		tr[le].sum += tr[p].tag*(mid-tr[p].l+1);
		tr[ri].tag += tr[p].tag*(tr[p].r-mid);
		tr[le].tag += tr[p].tag;
		tr[ri].tag += tr[p].tag;
		tr[p].tag = 0;
	}
}

void add (int p, int x, int y, int z) {
	if (x <= tr[p].l && tr[p].r <= y) {
		tr[p].tag += z;
		tr[p].sum += (tr[p].r-tr[p].l+1)*z;
		return;
	}
	pushdown (p);
	int mid = tr[p].l+tr[p].r>>1;
	if (x <= mid) add (p<<1, x, y, z);
	if (y > mid) add (p<<1|1, x, y, z);
	tr[p].sum = tr[p<<1].sum + tr[p<<1|1].sum;
}

int query (int p, int x, int y) {
	if (x <= tr[p].l && tr[p].r <=y) return tr[p].sum;
	int mid = tr[p].l+tr[p].r>>1;
	int ans = 0;
	pushdown (p);
	if (x <= mid) ans += query(p<<1 ,x, y);
	if (y > mid) ans += query(p<<1|1, x, y);
	return ans;
}

signed main() {
	scanf ("%lld%lld", &n, &m);
	for (int i=1; i<=n; i++) {
		scanf ("%lld", &a[i]);
	}
	for (int i=n-1; i>0; i--) {
		a[i+1] = a[i+1]-a[i];
	}
	build (1, 1, n);
	for (int i=1; i<=m; i++) {
		int mode;
		scanf ("%lld", &mode);
		if(mode == 1) {
			int l, r, k, d;
			scanf ("%lld%lld%lld%lld", &l, &r, &k, &d);
			add (1, l, l, k);
			if(l+1 <= r) add (1, l+1, r, d);
			if(r<n) add (1, r+1, r+1, -(k+d*(r-l)));
		} else {
			int t;
			scanf ("%lld", &t);
			printf ("%lld", query (1, 1, t));
		}
		
	}
}

线段树还是太难了

2024/8/5 16:26
加载中...