WA on #11 求调
查看原帖
WA on #11 求调
730504
lizeyuhello楼主2025/7/3 19:46
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e6 + 5, T = 1e3 + 5;
int n, q;
int a[N], b[N];
int l[T], r[T], bl[N], tot, block;
int tag[T];

void build()
{
	block = sqrt(n), tot = n / block;
	if (n % block != 0)
		++tot;
	for (int i = 1; i <= tot; ++i)
	{
		l[i] = (i - 1) * block + 1;
		r[i] = i * block;
	}
	r[tot] = n;
	for (int i = 1; i <= n; ++i)
		bl[i] = (i - 1) / block + 1;
}

void update_part(int L, int R, int K, int p)
{
	for (int i = L; i <= R; ++i)
		a[i] += K;
	memcpy(b + l[p], a + l[p], 8 * (r[p] - l[p] + 1));
}

void update(int L, int R, int K)
{
	if (bl[L] == bl[R])
	{
		update_part(L, R, K, bl[L]);
		return;
	}
	update_part(L, r[bl[L]], K, bl[L]);
	update_part(l[bl[R]], R, K, bl[R]);
	for (int i = bl[L] + 1; i < bl[R]; ++i)
		tag[i] += K;
}

int query_part(int L, int R, int K, int p)
{
	int res = 0;
	for (int i = L; i <= R; ++i)
		res += (a[i] >= K - tag[p]);
	return res;
}

int query(int L, int R, int K)
{
	if (bl[L] == bl[R])
		return query_part(L, R, K, bl[L]);
	int res = 0;
	res += query_part(L, r[bl[L]], K, bl[L]);
	res += query_part(l[bl[R]], R, K, bl[R]);
	for (int i = bl[L] + 1; i < bl[R]; ++i)
	{
		int pos = lower_bound(b + l[i], b + r[i] + 1, K - tag[i]) - b;
		res += r[i] - pos + 1;
	}
	return res;
}

signed main()
{
	scanf("%lld%lld", &n, &q);
	for (int i = 1; i <= n; ++i)
		scanf("%lld", a + i), b[i] = a[i];
	build();
	for (int i = 1; i <= tot; ++i)
		sort(b + l[i], b + r[i] + 1);
	while (q--)
	{
		char op[5];
		int x, y, k;
		scanf(" %s %lld%lld%lld", &op, &x, &y, &k);
		if (op[0] == 'M')
			update(x, y, k);
		else
			printf("%lld\n", query(x, y, k));
	}
	return 0;
}


100 pts WA on #11 求调

被 Hack 了 awa

2025/7/3 19:46
加载中...