样例及#1均对,但交上去0pts,求调
查看原帖
样例及#1均对,但交上去0pts,求调
470465
__int__楼主2023/7/13 23:12

RT,搞不懂为什么全错

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>

using namespace std;

const int N = 1e6 + 10;

int n, q, a[N], b[N];
int t, len, L[N], R[N], add[N], pos[N];

#define p_l pos[l]
#define p_r pos[r]
#define p_p pos[p]
inline void bf_update(int p, int l, int r, int d) {
	for (int i = l; i <= r; i ++ ) a[i] += d;
	for (int i = L[p_p]; i <= R[p_p]; i ++ ) b[i] = a[i];
	sort(b + L[p_p], b + 1 + R[p_p]);
}

inline void update(int l, int r, int d) {
	if (p_l == p_r) bf_update(l, l, r, d);
	else {
		bf_update(l, l, R[p_l], d), bf_update(l, L[p_r], r, d);
		for (int i = p_l + 1; i <= p_r - 1; i ++ )
			add[i] += d;
	}
}

inline int bf_query(int p, int l, int r, int d, int &res) {
	for (int i = l; i <= r; i ++ )
		if (add[p_p] + a[i] >= d) res ++ ;
}

inline int query(int l, int r, int d) {
	int res = 0;
	if (p_l == p_r) bf_query(l, l, r, d, res);
	else {
		bf_query(l, l, R[p_l], d, res), bf_query(r, L[p_r], r, d, res);
		for (int i = p_l + 1; i <= p_r - 1; i ++ )
			res += R[i] - (lower_bound(b + L[i], b + 1 + R[i], d - add[i]) - b) + 1;
	}
	return res;
}

signed main()
{
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i ++ )
		scanf("%d", a + i), b[i] = a[i];
	
	len = t = sqrt(n);
	for (int i = 1; i <= t; i ++ )
		L[i] = (i - 1) * t + 1, R[i] = i * t;
	if (R[t] < n) t ++ , L[t] = R[t - 1] + 1, R[t] = n;
	
	for (int i = 1; i <= t; i ++ )
		for (int j = L[i]; j <= R[i]; j ++ )
			pos[j] = i;
			
	for (int i = 1; i <= t; i ++ )
		sort(b + L[i], b + 1 + R[i]);
	
	char opt;
	for (int l, r, c; q -- ; ) {
		cin >> opt >> l >> r >> c;
		if (opt == 'M') update(l, r, c);
			else printf("%d\n", query(l, r, c));
	}
	
	return 0;
}
2023/7/13 23:12
加载中...