救救孩子!——一阶差分线段树求调
查看原帖
救救孩子!——一阶差分线段树求调
285414
Swiftie_wyc22楼主2022/12/22 15:05

能过样例,和测试点1

#include <bits/stdc++.h>
#define rei register int
#define ll long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define rep(i, s, n, c) for (register int i = s; i <= n; i+=c)
#define repd(i, s, n, c) for (register int i = s; i >= n; i-=c)
#define CHECK cout<<"WALKED"<<endl;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
#define pb push_back
#define ls id<<1
#define rs id<<1|1
const int INF = INT_MAX;
long long binpow(long long a, long long b, ll mod){long long res = 1;  while (b > 0){if (b & 1) res = res * a % mod;a = a * a % mod;  b >>= 1;  }  return res;}

using namespace std;

int n, m, opt;
ll l, r, K, D, E;

struct Tree{
	int left, right;
	ll sum, tag;
}tree[100005 * 4]; // 差分线段树数组
int a[100005]; // 原数组
int b[100005]; // 差分数组

inline void pushup(int id) {tree[id].sum = tree[ls].sum + tree[rs].sum;};
inline void pushdown(int id)
{
	if (tree[id].tag) {
		tree[ls].sum = (tree[ls].right - tree[ls].left + 1) * tree[id].tag;
		tree[ls].tag = tree[id].tag;
		tree[rs].sum = (tree[rs].right - tree[rs].right + 1) * tree[id].tag;
		tree[rs].tag = tree[id].tag;
		tree[id].tag = 0;
	}
}
void build(int id, int l, int r)
{
	tree[id].left = l, tree[id].right = r;
	tree[id].tag = 0;
	if (l == r) {
		tree[id].sum = b[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(ls, l, mid);
	build(rs, mid + 1, r);
	pushup(id);
}
void modify(int id, int l, int r, ll val)
{
	if (tree[id].left >r || tree[id].right < l) {
		return;
	}
	if (tree[id].left >= l && tree[id].right <= r) {
		tree[id].sum += (tree[id].right - tree[id].left + 1) * val;
		tree[id].tag = val;
		return;
	}
	pushdown(id);
	modify(ls, l, r, val);
	modify(rs, l, r, val);
	pushup(id);
}
ll query(int id, int l, int r)
{
	if (tree[id].left > r || tree[id].right < l) {
		return 0;
	}
	if (tree[id].left >= l && tree[id].right <= r) {
		return tree[id].sum;
	}
	pushdown(id);
	return query(ls, l, r) + query(rs, l, r);
}

int main()
{
	n = read(), m = read();
	for (int i = 1; i <= n; i++) {
		a[i] = read();
		b[i] = a[i] - a[i - 1];
	}
	build(1, 1, n);
	for (int kase = 1; kase <= m; kase++) {
		opt = read();
		if (opt == 1) {
			l = read(), r = read(), K = read(), D = read();
			E = (r - l) * D + K;
			modify(1, l, l, K);
			modify(1, l + 1, r, D);
			modify(1, r + 1, r + 1, -E);
		} else {
			r = read();
			printf("%lld\n", query(1, 1, r));
		}
	}
    return 0;
}

谢谢!

2022/12/22 15:05
加载中...