子串计数(genies)
Description
给出一段含有 n 个元素的序列 a, 要求求出子串和小于等于 t 的子串个数
Input Data
输入共两行
第一行包含两个整数, n,t 分别表示序列 a 元素的个数和限制 t
第二行包含 n 个数表示元素 a_i
Output Data
共一行, 含一个数
表示子串和小于等于 t 的子串个数.
- Input / Output Sample
- input #1:
- 5 4
- 5 -1 3 4 -1
- output #1:
- 7
- Solution:
一道妙题, 首先分析性质. 如果从 L+1 到 R 可以构成一个合法的区级显然 s[R]-S[L]<=t, 且 L<=R;
前缀和的想法是显然的, 但是还是突破不了枚举子串的瓶颈.
假设当前枚举到第 i 个元素那么我要从 s[0]-s[i-1]找到尽可能多的 s[j] (j∈[0,i-1])使 s[i]-s[j]<=t, 不妨考虑移项
s[j]>=s[i]-t, 而此时 s[i]-t 是定值!!! 我们只需要统计前面的 s[j]有多少个 s[j]>=s[i]-t 就行了! 即求 s[i]-t 的排行 rank,
n-rank 就是答案!
然而这种方法不是很妙, 更妙的方法是这样的:
首先我们知道归并排序只会把他分成越分越小, 而不会改变他原序列的前后顺序.
对于每一次归并的 [L,T] 和[T+1,R], 在每一段都是升序排序的, 我们弄一个指针 pt1 指在 [L,T] 弄另外的指针 pt2 指在[T+1,R]
对于 s[pt1]不断的把 pt2 往右移动, 找到第一个不能满足 s[pt2]-s[pt1]<=t 的点 (前面可以满足的记录). 这样可以保证处理 2 段区间的复杂度是 O(n) 的
对于全部的数据复杂度显然是 O(n log n)的.
- Code:
- # include <bits/stdc++.h>
- # define int long long
- using namespace std;
- const int N=200020;
- int n;
- int t,ans=0;
- int s[N];
- void solve(int l,int r)
- {
- if (l>=r) return;
- int mid=(l+r)>>1;
- solve(l,mid); solve(mid+1,r);
- int ret=0;
- for (int i=l,j=mid;i<=mid;i++) {
- while (j<r&&s[j+1]-s[i]<=t) j++;
- ret+=j-mid;
- }
- ans+=ret;
- inplace_merge(s+l,s+mid+1,s+r+1);
- }
- signed main()
- {
- scanf("%lld%lld",&n,&t);
- for (int i=1;i<=n;i++) {
- int x; scanf("%lld",&x);
- s[i]=s[i-1]+x;
- }
- solve(0,n);
- printf("%lld\n",ans);
- return 0;
- }
[暴力 Treap 或 离线归并] 子串计数(genies)
来源: http://www.bubuko.com/infodetail-2938862.html