线段树写法求助,WA70pts#2#9#10,悬灌
查看原帖
线段树写法求助,WA70pts#2#9#10,悬灌
775993
codwarm楼主2023/11/25 11:28

rt,直接从线段树1模板复制过来改的,不知道为什么不对,求猪。

// Problem: #P1362. 【模板】树状数组 2(区间修改、单点询问)
// Contest: Hydro
// URL: http://43.139.23.174/p/P1362
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Author: Eason
// Date:2023-11-25 10:09:12
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define il inline
#define gc getchar
#define int ll
inline int read()
{
	int f=1,k=0;
	char c = getchar();
	while (c <'0' || c > '9')
	{
		if (c=='-') f=-1;
		c=getchar();
	}
	while(c >= '0' && c <= '9')  k = (k << 1)+(k << 3)+(c^48),c=getchar();
	return k*f;
}
const int N = 500005;
int n,m,op,x,y,k,sum[N*5],a[N],tag[N];

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

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

void modify(int k,int l,int r,int x,int y,int  v)
{
	if (x > r || y < l) return;
	if (x <= l && y >= r)
	{
		sum[k] += (r-l+1) * v;
		tag[k] += v;
	}
	else
	{
		pushdown(k,l,r);
		int mid = l + r >> 1;
		modify(k<<1,l,mid,x,y,v);
		modify (k<<1|1,mid+1,r,x,y,v);
		sum[k] = sum[k<<1] + sum[k << 1 | 1];
	}
}

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

signed main()
{
	n = read(),m = read();
	for (int i = 1;i <= n;i++) a[i] = read();
	build(1,1,n);
	while (m--)
	{
		op = read();
		if (op == 1)
		{
			x = read(),y = read(),k = read();
			modify(1,1,n,x,y,k);
		}
		else
		{
			x = read();
			cout << query(1,1,n,x,x) << endl;
		}
	}
	return 0;
}
2023/11/25 11:28
加载中...