线段树求调玄关
  • 板块学术版
  • 楼主Hyvial
  • 当前回复10
  • 已保存回复10
  • 发布时间2024/8/21 18:31
  • 上次更新2024/8/21 20:47:35
查看原帖
线段树求调玄关
1137394
Hyvial楼主2024/8/21 18:31

没错又是我

这道题只拿了0分,疑似int溢出,可我#define int long long 了呀,到底是为什么QWQ。

#include <bits/stdc++.h>
#define PII pair <int, int>
#define int long long
#define DB double
#define lson x << 1
#define rson x << 1 | 1
#define tl Tree[x].left
#define tr Tree[x].right
#define mid ((tl + tr) >> 1)

namespace FastIO
{
	inline void read(int MOD, int &ret){
		char ch = getchar();int ngtv = 1;
		if(MOD == 0) {while(ch < '0' || ch > '9'){if(ch == '-') ngtv = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){ret = ret * 10 + (ch - '0');ch = getchar();}}
		else {while(ch < '0' || ch > '9'){if(ch == '-') ngtv = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){ret = (ret * 10 % MOD + (ch - '0') % MOD) % MOD;ch = getchar();} }
		ret *= ngtv;}
	inline void cread(char &ch){while(ch == ' ' || ch == '\n' || ch == '\r' || ch == 0) ch = getchar();ch = getchar();}
}
using namespace FastIO;
using namespace std;

const int N = 1e5 + 10, MN = 4e5 + 10;
int n, m, op, a, b, c, d, A[N];

struct Node
{
	int left, right, sum, tag;
}Tree[MN];

void init_tree(int x, int l, int r)
{
	tl = l;
	tr = r;
	
	if(l == r)
	{
		Tree[x].sum = A[l];
		return ;
	}

	init_tree(lson, l, mid);
	init_tree(rson, mid + 1, r);
	
	Tree[x].sum = Tree[lson].sum + Tree[rson].sum;
}

void pushdown(int x)
{
	Tree[lson].tag += Tree[x].tag;
	Tree[rson].tag += Tree[x].tag;
	Tree[lson].sum += (mid - tl + 1) * Tree[x].tag;
	Tree[rson].sum += (tr - mid) * Tree[x].tag;

	Tree[x].tag = 0;
}

void add(int x, int l, int r, int k)
{
	if(r < tl || tr < l)
		return ;

	if(l <= tl && tr <= r)
	{
		Tree[x].tag += k;
		Tree[x].sum += k * (tl - tr + 1);
		return ;
	}
	
	pushdown(x);
	
	add(lson, l, r, k);
	add(rson, l, r, k);
	
	Tree[x].sum = Tree[lson].sum + Tree[rson].sum;
}

int sum(int x, int l, int r)
{
	if(r < tl || tr < l)
		return 0;
	
	if(l <= tl && tr <= r)
		return Tree[x].sum;
	
	pushdown(x);
	
	return sum(lson, l, r) + sum(rson, l, r);
}

signed main()
{
//	freopen("P1438_1.in", "r", stdin);
//	freopen("蒟蒻.out", "w", stdout);
	
	read(0, n), read(0, m);
	for(int i = 1; i <= n; i ++ )
		read(0, A[i]);
	for(int i = n - 1; i > 0; i -- )
		A[i + 1] = A[i + 1] - A[i];
	
	init_tree(1, 1, n);
	
	while(m -- )
	{
		scanf("%lld", &op);
		if(op == 1)
		{
			scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
			add(1, a, a, c);
			if(a < b)
				add(1, a + 1, b, d);
			if(b < n)
				add(1, b + 1, b + 1, -((b - a) * d + c));
		}
		else
		{
			scanf("%lld", &a);
			printf("%lld\n", sum(1, 1, a));
		}
	}
	
	return 0;
}
2024/8/21 18:31
加载中...