树状数组求调
查看原帖
树状数组求调
1074696
tmlrock楼主2025/8/2 14:16
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;


class fenwick {
	public:
		int t[maxn];
		int N;
		inline void add(int id, int d) {
			for (; id <= N; id += (id & -id))t[id] += d;
		}
		inline int query(int r) {
			int ans = 0;
			for (; r; r ^= (r & -r))ans += t[r];
			return ans;
		}
};
fenwick fen1, fen2;
void Add(int l, int r, int k) {
	fen1.add(l, k);
	fen1.add(r, -k);
	fen2.add(l, k * l);
	fen2.add(r, -k * r);
}
int query(int r) {
	int ans = fen1.query(r) * (r + 1);
	ans -= fen2.query(r);
	return ans;
}
int main() {
	int n = 10;
//	cin>>n;
	fen1.N = fen2.N = n;
	Add(2, 3, 1);
	cout << query(4) << ' ' << query(3) << ' ' << query(2);
	return 0;
}
2025/8/2 14:16
加载中...