題目鏈接
省賽選拔學長說是CF的原題，賽后得知學長是用樹狀數(shù)組寫的，補了一個樹狀數(shù)組的代碼。

題意

$N$個數(shù)，問一共有多少個連續(xù)區(qū)間滿足區(qū)間和小于 $M$

思路

記錄每個數(shù)的前綴和$sort$之后，枚舉區(qū)間的起始位置找到前綴和小于$M+pre$的個數(shù)（設當前區(qū)間起始為i，滿足條件的區(qū)間== $Lastpre?Nowpre<M$）Lastpre:后面的前綴和，Nowpre:當前的前綴和

比賽的時候tony5t4rk用vector刪除元素T掉了，后來splay優(yōu)化過了(tql).

#include <bits/stdc++.h> #define LL long long #define P pair<int, int> #define lowbit(x) (x & -x) #define mem(a, b) memset(a, b, sizeof(a)) #define mid ((l + r) >> 1) #define lc rt<<1 #define rc rt<<1|1 using namespace std; const int maxn = 2e5 + 7;int num[maxn]; void Add(int x, int d) {x++;while (x < maxn) {num[x] += d;x += lowbit(x);} } int Sum(int x) {x++;int sum = 0;while(x > 0) {sum += num[x];x -= lowbit(x);}return sum; }int main () {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n;LL m;while (cin >> n >> m) {mem(num, 0);vector<LL> a(n), b(n);for (int i = 0; i < n; ++i) {cin >> a[i];if (i) a[i] += a[i-1];b[i] = a[i];}sort(b.begin(), b.end());b.resize(unique(b.begin(), b.end()) - b.begin());for (LL it : a) {Add(lower_bound(b.begin(), b.end(), it) - b.begin(), 1);}LL ans = 0, sum = 0;for (int i = 0; i < n; ++i) {if (i) sum = a[i-1];LL tmp = Sum(lower_bound(b.begin(), b.end(), sum+m) - b.begin()-1);ans += tmp;Add(lower_bound(b.begin(), b.end(), a[i]) - b.begin(), -1);}cout << ans << endl;}return 0; }

總結

以上是生活随笔為你收集整理的Codeforce 1042 D. Petya and Array(树状数组、前缀和)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。