题目大意
给出一个长为n的数列A,一个长为m的数列B
求问A中有多少个长度为m的子区间S,满足S中的元素全都不小于B中下标对应的元素
题解
说实话真的还是对bitset的应用不熟悉。
这题bitset只是最后用来优化的。
首先我们假定一个tmp数组,其中tmp[i][j]表示对Ai是否≥Bj。
如果一个长度为m的子区间要成为满足题目条件的S,那么和tmp[i]数组有什么关系?
一定是要求:对于区间内每一个i及其对应位置的j,tmp[i][j]都为1.这是显然的。
考虑如何优化这个问题。
首先,大小关系其实本质上来说只有m+1种,也就是对于tmp[i]的取值最多有m+1种,所以我们可以将B数组内的数全部排序,然后用m+1个bitset(假设为s)逐位去置1,然后九不需要算tmp数组了,我们需要取用tmp的时候,只需要找到最后一个小于等于A[i]的B[j](这里的B已经排序好了),然后取s[j]就可以了。而且bitset也会在我们接下来的做法中发挥很重要的作用。预处理这些bitset的复杂度是O(m2/W)的(W为bitset优化的效果)
之后考虑如何去搞这个题。
新设一个新的m位bitset,假设为curi,其中curi[j] = 1当且仅当对于所有的k∈[j,m],Ai+k-j >= Bk,这样只需要求有多少curi[1] = 1即可。
首先可以确定A数组的后m-1个数是肯定不可以作为区间点的,毕竟区间长度都不够,所以我们可以按照下面的公式来做:
curi = ((curi+1 >> 1) | Im) & sposi。posi表示最后一个小于等于A[i]的B[posi]。
这样通过右移位来进行对齐,可以达到我们预期的效果。
而且,我们可以不用开n个cur,只需要开一个进行滚动就可以了。
最终的时间复杂度是O(nm/W)
代码
#include <bits/stdc++.h> using namespace std; typedef pair<int,int>PI; const int maxn = 150005; const int maxm = 40005; PI a[maxn],b[maxm]; bitset<maxm>s[maxm]; bitset<maxm>cur,upd; const int INF = 1e9+7; int n,m; int p; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 1;i <= n;++i){ cin >> p; a[i].first = p; a[i].second = i; } for(int i = 1;i <= m;++i){ cin >> p; b[i].first = p; b[i].second = i; } s[0].reset(); b[m+1].first = INF; b[m+1].second = m+1; sort(b+1,b+m+2); for(int i = 1;i <= m;++i){ s[i] = s[i-1]; s[i].set(b[i].second); } int ans = 0; cur.reset(); upd.reset(); upd.set(m); for(int i = n;i > 0;--i){ int pos = upper_bound(b+1,b+m+2,a[i]) - b - 1; cur = ((cur >> 1) | upd) & s[pos]; if(cur[1]){ ans++; } } cout << ans << endl; return 0; }
No Leanote account ? Sign up now.