5号关注,权值线段树70分萌新求助
  • 板块P2717 寒假作业
  • 楼主Zelotz
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/2/13 18:00
  • 上次更新2023/10/28 08:38:38
查看原帖
5号关注,权值线段树70分萌新求助
347589
Zelotz楼主2022/2/13 18:00

对拍 nn 组了,一直不知道哪里有问题

wa的点显示答案是 00

#include <bits/stdc++.h>
using namespace std;
#define srand srand(time(NULL))
#define random(x) rand() % (x)
#define il inline
#define ptc putchar
#define reg register
#define mp make_pair
typedef __int128 LL;
typedef long long ll;
typedef pair<int, int> PII;
namespace cyyh {
	template <typename T>
	il void read(T &x) {
		x = 0; T f = 1; char ch;
		while (!isdigit(ch = getchar())) f -= (ch == '-') << 1;
		while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch & 15), ch = getchar(); x *= f;
	}
	template <typename T>
	il void write(T x) {
		if (x < 0) ptc('-'), x = -x;
		if (x > 9) write(x / 10);
		ptc(x % 10 + '0');
	}
	template <typename T>
	il T lowbit(const T &x) {
		return x & -x;
	}
}
using namespace cyyh; 
#define int long long
const int N = 1e5, M = 2e7, INF = 1e10 + 1;
int n, k, s[N], root, tot, t[M], ls[M], rs[M], ans;
void build(int l, int r, int x, int &id) {
	if (l > x || r < x) return ;
	if (!id) id = ++tot;
//	cout << (!id) << endl;
	if (l == r) {
		++t[id];
		return ;
	}
	int mid = l + r >> 1;
	build(l, mid, x, ls[id]), build(mid + 1, r, x, rs[id]);
	t[id] = t[ls[id]] + t[rs[id]];
}
int query(int l, int r, int x, int y, int id) {
	if (!id) return 0;
	if (l > y || r < x) return 0;
	if (l >= x && r <= y) return t[id];
	int mid = l + r >> 1;
	return query(l, mid, x, y, ls[id]) + query(mid + 1, r, x, y, rs[id]);
}
signed main() {
//	freopen("1.txt", "r", stdin);
//	freopen("myout.txt", "w", stdout);
	read(n), read(k);
	for (int i = 1; i <= n; ++i) read(s[i]), s[i] += s[i - 1];
	build(1, INF << 1, -k + INF, root);
//	cout << root <<endl;
	for (int i = 1; i <= n; ++i) {
		int x = s[i] - i * k - k;
//		cout << x <<endl;
		ans += query(1, INF << 1, 1, x + INF, root);
		build(1, INF << 1, s[i] - (i + 1) * k + INF, root);
	}
	write(ans);
	return 0;
}
2022/2/13 18:00
加载中...