CF1042D Petya and Array树状数组-USB迷|专注于互联网分享

CF1042D Petya and Array 树状数组

题目描述

Petya has an array a a a consisting of n n n integers. He has learned partial sums recently, and now he can calculate the sum of elements on any segment of the array really fast. The segment is a non-empty sequence of elements standing one next to another in the array.

Now he wonders what is the number of segments in his array with the sum less than t t t . Help Petya to calculate this number.

More formally, you are required to calculate the number of pairs l,r l, r l,r ( l≤r l \le r l≤r ) such that al+al+1+⋯+ar−1+ar<t a_l + a_{l+1} + \dots + a_{r-1} + a_r < t al+al+1+⋯+ar−1+ar<t .
输入输出格式
输入格式：

The first line contains two integers n n n and t t t ( 1≤n≤200000,∣t∣≤2⋅1014 1 \le n \le 200,000, |t| \le 2\cdot10^{14} 1≤n≤200000,∣t∣≤2⋅1014 ).

The second line contains a sequence of integers a1,a2,…,an a_1, a_2, \dots, a_n a1,a2,…,an ( ∣ai∣≤109 |a_{i}| \le 10^{9} ∣ai∣≤109 ) — the description of Petya’s array. Note that there might be negative, zero and positive elements.

输出格式：

Print the number of segments in Petya’s array with the sum of elements less than t t t .

输入输出样例
输入样例#1：复制

5 4
5 -1 3 4 -1

输出样例#1：复制

输入样例#2：复制

3 0
-1 2 -3

输出样例#2：复制

输入样例#3：复制

4 -1
-2 1 -2 3

输出样例#3：复制

说明

In the first example the following segments have sum less than 4 4 4 :

[2,2] [2, 2] [2,2] , sum of elements is −1 -1 −1
[2,3] [2, 3] [2,3] , sum of elements is 2 2 2
[3,3] [3, 3] [3,3] , sum of elements is 3 3 3
[4,5] [4, 5] [4,5] , sum of elements is 3 3 3
[5,5] [5, 5] [5,5] , sum of elements is −1 -1 −1

大意：
询问有多少区间sum <t；
自然想到前缀和–> Sum[ j ]- Sum[ i-1 ]< t；
即：
Sum [ j ]- t < Sum[ i-1 ]
其中 j>i>=1；
是不是很熟悉？？
逆序对，没错；

洛谷逆序对
上面是模板题；
逆序对除了归并排序的做法外，还有树状数组；

#include<bits/stdc++.h>
using namespace std;
#define maxn 600005
#define ll long longint n;
int a[maxn];
int b[maxn];
int c[maxn];void add(int x){while(x<=n){c[x]++;x+=x&-x;}
}int query(int x){int res=0;while(x>0){res+=c[x];x-=x&-x;}return res;
}int main(){ios::sync_with_stdio(0);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];b[i]=a[i];}sort(b+1,b+1+n);ll ans=0;for(int i=1;i<=n;i++){add(lower_bound(b+1,b+n+1,a[i])-(b+1)+1);ans+=(i-query(lower_bound(b+1,b+1+n,a[i]+1)-(b+1)));}cout<<ans<<endl;
}

当然如果范围太大的话，应考虑离散化；
那么我们将前缀和预处理出来，然后树状数组处理即可；

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<bitset>
#include<ctime>
#include<deque>
#include<stack>
#include<functional>
#include<sstream>
#include<cctype>
//#pragma GCC optimize("O3")
using namespace std;
#define maxn 600005
#define inf 0x3f3f3f3f
#define INF 0x7fffffff
typedef long long  ll;
typedef unsigned long long ull;
typedef unsigned int U;
#define ms(x) memset((x),0,sizeof(x))
const long long int mod = 1e9 + 7;
#define Mod 20100403
#define sq(x) (x)*(x)
#define eps 1e-15
const int N = 2500005;inline int rd() {int x = 0;char c = getchar();bool f = false;while (!isdigit(c)) {if (c == '-') f = true;c = getchar();}while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f ? -x : x;
}ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a%b);
}int n;
ll t;
ll a[maxn];
ll b[maxn];
ll sum[maxn];void add(ll x) {while (x <= n + 1) {sum[x]++; x += x & -x;}
}ll query(ll x) {ll res = 0;while (x > 0) {res += sum[x]; x -= x & -x;}return res;
}int main()
{ios::sync_with_stdio(false);cin >> n >> t;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++) {a[i] += a[i - 1];b[i] = a[i];}sort(b, b + n + 1);ll res = 0;for (int i = 1; i <= n; i++) {add(lower_bound(b, b + n + 1, a[i - 1]) - b+1 );res += (i - query(lower_bound(b, b + n + 1, a[i] - t + 1) - b));}cout << res << endl;return 0;
}

注意两者的相通点，举一反三；