分块求助
查看原帖
分块求助
519384
Link_Cut_Y楼主2022/3/19 08:56
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 500010, M = 710;

int add[M];
int len, n, m;
int w[N];

int get(int x)
{
	return x / len;
}

void modify(int l, int r, int v)
{
	if (get(l) == get(r))
	{
		for (int i = l; i <= r; i ++ )
			w[i] += v;
		return;
	}
	
	int i = l, j = r;
	while (get(i) == get(l)) w[i] += v, i ++ ;
	while (get(j) == get(r)) w[j] += v, j -- ;
	
	for (int k = get(i); k <= get(j); k ++ )
		add[k] += v;
}

int main()
{
	scanf("%d%d", &n, &m);
	len = sqrt(n);
	
	for (int i = 1; i <= n; i ++ )
		scanf("%d", &w[i]);
	
	while (m -- )
	{
		int op, l, r, v;
		scanf("%d", &op);
		if (op == 1)
		{
		    scanf("%d%d%d", &l, &r, &v);
		    modify(l, r, v);
		}
		
		else
		{
		    scanf("%d", &l);
		    printf("%d\n", w[l] + add[get(l)]);
		}
	}
	
	return 0;
}
2022/3/19 08:56
加载中...