我用树状数组写了一份代码但是问题好多,QAQ,sos!!! wwww
查看原帖
我用树状数组写了一份代码但是问题好多,QAQ,sos!!! wwww
842110
wadecrush楼主2023/7/24 20:51

我的本意是将他看作一共区间修改单点查询的问题,在位置l处加上首项,然后在l+1到r之间加上公差,在r+1位置减去前面的差分和,但是好像写的不对,大佬救命!!!

#include<bits/stdc++.h>
#define int long long
using namespace std;

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 << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
inline void write(int x) 
{
	if (x < 0)
	{
		putchar('-');
		x = -x;
	}
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
	return;
}

int n, m;
const int N = 1e5 + 10;
int tr[N], a[N];
void add(int x,int c)
{
	for (int i = x; i <= n; i += lobit(i))
	{
		tr[i] += c;
	}
}
int  query(int x)
{
	int cnt = 0;
	for (int i = x; i >= 1; i -= lobit(i))
	{
		cnt += tr[i];
	}
	return cnt;
}
signed main()
{
	n = read();
	m = read();
	for (int i = 1; i <= n; i++)
	{
		a[i] = read();
	}
	while (m--)
	{
		int opt = read();
		if (opt == 1)
		{
			int l, r, k, d;
			l = read();
			r = read();
			k = read();
			d = read();
			add(l, k);
			add(l + 1, d);
			add(r + 1, -(k + (r - l) * d));
		}
		else
		{
			int p;
			p = read();
			int ans = query(p) + a[p];
			write(ans);
			puts("");
		}
	}
	return 0;
}
2023/7/24 20:51
加载中...