广告联盟的网站怎么做,刷赞网站怎么做的,贵南网站建设,网站建设岗位叫什么题面
分析
存在负数不满足单调性#xff0c;因此无法二分或者双指针#xff0c;对于每一段符合条件的区间 [ l , r ] [l, r] [l,r] 都有 s u m [ r ] − s u m [ l − 1 ] k sum[r] - sum[l - 1] k sum[r]−sum[l−1]k #xff0c;也就是 s u m [ l − …题面
分析
存在负数不满足单调性因此无法二分或者双指针对于每一段符合条件的区间 [ l , r ] [l, r] [l,r] 都有 s u m [ r ] − s u m [ l − 1 ] k sum[r] - sum[l - 1] k sum[r]−sum[l−1]k 也就是 s u m [ l − 1 ] s u m [ r ] − k sum[l - 1] sum[r] - k sum[l−1]sum[r]−k 那么如果对于所有区间的前缀和来进行顺序存储那么对于当前前缀和 s u m [ i ] sum[i] sum[i] 可以去找小于等于 s u m [ i ] − k sum[i] - k sum[i]−k 的符合条件的前缀和有多少但是前缀和的范围很大所以就要进行离散化将所有需要用到的前缀和都进行i离散化重新定下标然后可以通过树状数组每次对遍历到的前缀和的位置加一统计可以加上树状数组查询 s u m [ i ] − k sum[i] - k sum[i]−k 的结果也就是这之前有多少个满足条件的前缀和。
代码
#include bits/stdc.husing namespace std;
using ll long long;const int N 2e5 10;ll a[N];
int tr[N];
mapll, int m;void add(int u) {for(int i u; i N; i (i -i)) {tr[i] ;}return ;
}int query(int x) {int ans 0;for(int i x; i 1; i - i -i) ans tr[i];return ans;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;ll k;cin n k;for(int i 1; i n; i ) {cin a[i];a[i] a[i - 1];}m[0] 1;for(int i 1; i n; i ) {m[a[i]] 1;m[a[i] - k] 1;}int now 1;for(auto x: m) {x.second now ;}//for(auto j: m) cout j.first j.second endl;ll ans 0;add(m[0]);for(int i 1; i n; i ) {ans query(m[a[i] - k]);add(m[a[i]]);}cout ans \n;
}
