分块满江红,玄关
  • 板块P2357 守墓人
  • 楼主IDNo1
  • 当前回复12
  • 已保存回复12
  • 发布时间2023/8/28 22:00
  • 上次更新2023/11/3 00:37:12
查看原帖
分块满江红,玄关
777131
IDNo1楼主2023/8/28 22:00

之前对着题解打一遍,不仅看不懂,还扎样例,后来拿while手敲了一遍,结果样例过了,可是提交评测却满江红,庆祝求助!

#include<bits/stdc++.h>
#define re register int
#define ll long long
#define rll register long long 
const int N = 200005;
using namespace std;
int in[N]/*第 $i$ 个所在的块*/;
ll a[N], res[N]/*整块和*/, cnt[N];
int sq, n, m, opt, k, l, r;
inline int read()
{
    re 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 * 10 + ch - '0', ch = getchar();
    return x * f;
}
inline void write(re x)
{
    if(x < 0) 
	{
        putchar('-');
        x = -x;
    }
    if(x > 9) 
	{
        write(x / 10);
    }
    putchar(x % 10 + '0');
}
inline void add(re l, re r, re k)
{
	re i = l;
	while(in[i] == in[l])
	{
		res[in[i]] += k;
		a[i] += k;
		i ++;
	}
	while(i + sq <= r)
	{
		res[in[i]] += k * sq;
		cnt[in[i]] += k;
		i += sq;
	}
	while(i <= r)
	{
		res[in[i]] += k;
		a[i] += k;
		i ++;
	}
}
inline ll query(re l, re r)
{
	rll tmp = 0, i = l;
	while(in[i] == in[l])
	{
		tmp += a[i] + cnt[in[i]];
		i ++;
	}
	while(i + sq <= r)
	{
		tmp += res[in[i]];
		i += sq;
	}
	while(i <= r)
	{
		tmp += a[i] + cnt[in[i]];
		i ++;
	}
	return tmp;
}
int main()
{
	n = read(), m = read();
	sq = sqrt(n);
	for(re i = 1;i <= n;i ++)
	{
		in[i] = (i - 1) / sq + 1;
		a[i] = read();
		res[in[i]] += a[i];
	}
	while(m --)
	{
		opt = read();
		if(opt == 1)
		{
			l = read(), r = read(), k = read();
			add(l, r, k);
		}
		else if(opt == 2)
		{
			k = read();
			a[1] += k;
			res[1] += k;
		}
		else if(opt == 3)
		{
			k = read();
			a[1] -= k;
			res[1] -= k;
		}
		else if(opt == 4)
		{
			l = read(), r = read();
			write(query(l, r));
			putchar('\n');
		}
		else if(opt == 5)
		{
			write(a[1] + cnt[1]);
			putchar('\n');
		}
	}
	return 0;
} 

2023/8/28 22:00
加载中...