线段树板子全WA求调
  • 板块P2068 统计和
  • 楼主IQ勇士
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/8/8 14:31
  • 上次更新2023/10/27 16:27:52
查看原帖
线段树板子全WA求调
158652
IQ勇士楼主2022/8/8 14:31

RT,

#include<iostream>
#include<cstdio>
using namespace std;
struct tree{
	long long sum;
	long long tag;
}t[400001];
void build(int index, int l, int r)
{
	t[index].tag = 0;
	if(l == r)
		t[index].sum = 0;
	else
	{
		int m = (l + r) / 2;
		build(index * 2, l, m);
		build(index * 2 + 1, m + 1, r);
	}
}
bool noj(int l1, int r1, int l2, int r2)
{
	return l1 > r2 || l2 > r1;
}
bool qb(int l1, int r1, int l2, int r2)
{
	return l1 <= l2 && r1 >= r2;
}
void pushup(int index)
{
	t[index].sum = t[index * 2].sum + t[index * 2 + 1].sum;
}
void tagging(int tt, int index, int l, int r)
{
	if(l == r)
		t[index].sum += tt;
	else
		t[index].tag += tt;
}
void pushdown(int index, int l, int r)
{
	int m = (l + r) / 2;
	tagging(t[index].tag, index * 2, l, m);
	tagging(t[index].tag, index * 2 + 1, m + 1, r);
	t[index].sum += (r - l + 1) * t[index].tag;
	t[index].tag = 0;
}
int chaxun(int L, int R, int l, int r, int index)
{
	if(qb(L, R, l, r))
		return t[index].sum;
	if(noj(L, R, l, r))
		return 0;
	int m = (l + r) / 2;
	pushdown(index, l, r);
	return chaxun(L, R, l, m, index * 2) + chaxun(L, R, m + 1, r, index * 2 + 1);
}
void xiugai(int dex, int l, int r, int index, int x)
{
	if(dex < l || dex > r)
		return;
	if(l == dex && r == dex)
	{
		t[index].sum += x;
		return;
	}
	int m = (l + r) / 2;
	if(dex <= m)
		xiugai(dex, l, m, index * 2, x);
	else
		xiugai(dex, m + 1, r, index * 2 + 1, x);
	pushup(index);	
} 
int n, w, aa, bb;
char c;
int main()
{
	cin >> n >> w;
	build(1, 1, n);
	for(int i = 1; i <= w; i++)
	{
		cin >> c;
		if(c == 'x')
		{
			cin >> aa >> bb;
			xiugai(aa, 1, n, 1, bb);
		}
		else
		{
			cin >> aa >> bb;
			cout << chaxun(aa, bb, 1, n, 1) << endl;
		}
	}
	return 0;
}
2022/8/8 14:31
加载中...