Submission #74671054

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct BIT {
	vector<int> tree;
	int n;
	BIT(int n = 0) {
		init(n);
	}
	void init(int n_) {
		n = n_;
		tree.assign(n + 2, 0);
	}
	void add(int i, int v) {
		for (; i <= n; i += i & -i)
			tree[i] += v;
	}
	int query(int i) {
		int res = 0;
		for (; i > 0; i -= i & -i)
			res += tree[i];
		return res;
	}
	int queryRange(int l, int r) {
		if (l > r)
			return 0;
		return query(r) - query(l - 1);
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int N;
	ll K;
	cin >> N >> K;

	vector<int> P(N);
	for (int i = 0; i < N; i++)
		cin >> P[i];

	// 坐标压缩
	vector<int> vals = P;
	sort(vals.begin(), vals.end());
	vals.erase(unique(vals.begin(), vals.end()), vals.end());

	auto getId = [&](int x) {
		return lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;
	};

	int M = vals.size();
	for (int i = 0; i < N; i++)
		P[i] = getId(P[i]);

	BIT bit(M);
	ll ans = 0;
	int r = -1;
	ll curInv = 0;

	for (int l = 0; l < N; l++) {
		if (r < l - 1) {
			r = l - 1;
			curInv = 0;

		}
		if (l > 0 && r >= l - 1) {
			int cnt = bit.query(P[l - 1] - 1);
			curInv -= cnt;
			bit.add(P[l - 1], -1);
		}

		while (r < N - 1 && curInv < K) {
			r++;
			int cnt = bit.queryRange(P[r] + 1, M);
			curInv += cnt;
			bit.add(P[r], 1);
		}


		if (curInv == K) {

			ll cntR = 1;


			while (r < N - 1) {
				int nextCnt = bit.queryRange(P[r + 1] + 1, M);
				if (nextCnt == 0) {
					r++;
					bit.add(P[r], 1);

					cntR++;
				} else {
					break;
				}
			}

			ans += cntR;
		}

	}



	bit = BIT(M);
	ans = 0;
	r = -1;
	curInv = 0;

	for (int l = 0; l < N; l++) {

		if (l > 0) {
			int cnt = bit.query(P[l - 1] - 1);
			curInv -= cnt;
			bit.add(P[l - 1], -1);
		}


		if (r < l - 1) {
			r = l - 1;
		}


		while (r < N - 1 && curInv < K) {
			r++;
			int cnt = bit.queryRange(P[r] + 1, M);
			curInv += cnt;
			bit.add(P[r], 1);
		}
		if (curInv == K) {

			ll cntR = 1;
			while (r < N - 1) {
				int nextCnt = bit.queryRange(P[r + 1] + 1, M);
				if (nextCnt == 0) {
					r++;
					bit.add(P[r], 1);
					cntR++;
				} else {
					break;
				}
			}
			ans += cntR;
		}
	}

	cout << ans << endl;
}

Submission Info

Judge Result