【CF689D Friends and Subsequences】二分搜索,区间查询

题意:给定两个整数序列a,b,将a,b对齐,问有多少个区间满足a的区间内最大值等于b的区间内最小值。

数据范围:区间长度n属于[1, 200000],序列中的元素在整型范围内

思路:枚举所有n*(n+1)/2个区间复杂度过高。题解的方法是,只枚举区间左端点,然后想办法把对右端点的处理降到O(logn)。能降得益于这道题特有的以下性质:

首先,枚举每个左端点时,将左端点left定义为一个常量,将右端点r定义为变量,r >= left;故题目的两个要求可以翻译为这样两个以右端点r为自变量的函数 max{ar}与min{br},分别表示序列a在区间[left, r]上的最大值,序列b在区间[left, r]上的最小值。

其次,有如下观察事实:

1. 固定左端点,则随着区间的向右扩张,max{ai}不会变小,min{bi}不会变大;即max{ar}单调不降,min{br}单调不升

2. 根据1,可以推出一旦扩张到某个位置出现max{ai} > min{bi},那么再往右扩张就已经没意义了;对称的,若当前位置仍处在max{ar} < min{br}的状态,那么符合条件的右边界r若存在则一定在当前位置右侧。

3. 根据2,可以推出符合条件的右边界r如果存在,则一定连续分布在left右侧的某个区间内。

所以,根据以上性质,尤其第3条,我们便可以使用二分查找来加速原来的对右边界的枚举。假设合法的右边界构成了区间[rmin, rmax],那么分别二分查找rmin, rmax即可。类似lower_bound和upper_bound,对rmin和rmax二分查找的区别仅在于相等时的移动方向:rmin左移而rmax右移。另外注意对查找失败情况的处理,查找前初始化rmin为n-1, rmax为left,这样查找失败<=>rmax < rmin,这种情况不为最终的结果贡献长度。

这样确定一个rmin需要二分logn个位置*每个位置logn的求最值,共计log2n;因此总的时间为n*2log2n = n*log2(n2)

区间查询部分题解说用任意一个可以做RMQ的数据结构即可,于是想借此试试线段树,结果T了。。。然后剪枝,当rmin不合法时continue。然而还是会T,因为最坏情况无法避免n*2log2n的总时间。于是学习别人的姿势改用sparse table,这样需nlogn的预处理,但每个位置求最值只需O(1),所以总的时间为nlogn + n,最坏情况确实比线段树更快。

 #include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <assert.h>
#define FREAD(fn) freopen((fn), "r", stdin)
#define RINT(vn) scanf("%d", &(vn))
#define PINT(vb) printf("%d", vb)
#define RSTR(vn) scanf("%s", (vn))
#define PSTR(vn) printf("%s", (vn))
#define CLEAR(A, X) memset(A, X, sizeof(A))
#define REP(N) for(int i=0; i<(N); i++)
#define REPE(N) for(int i=1; i<=(N); i++)
#define pb(X) push_back(X)
#define pn() printf("\n")
using namespace std;
const int MAX_N = (<<);//注意要把最大值扩展到2的幂次
const int INFP = 0x7fffffff;
const int INFN = -0x7fffffff; int n, m;//m为大于n的最小的2的幂
int a[MAX_N], b[MAX_N];
int ta[MAX_N][], tb[MAX_N][];//spare table, t[i][j],i为起点,2^j为区间长度 void build_max(){
for(int i=n; i<m; i++) a[i] = INFN;//负无穷填充
REP(m) ta[i][] = a[i];
for(int j=; j<__builtin_ctz(m); j++){//m即区间长度的上限
for(int i=; i+(<<j) <= m; i++){
ta[i][j] = max(ta[i][j-], ta[i+(<<(j-))][j-]);
}
}
} void build_min(){
for(int i=n; i<m; i++) b[i] = INFP;//正无穷填充
REP(m) tb[i][] = b[i];
for(int j=; j<__builtin_ctz(m); j++){//m即区间长度的上限
for(int i=; i+(<<j) <= m; i++){
tb[i][j] = min(tb[i][j-], tb[i+(<<(j-))][j-]);
}
}
} //闭区间
int qmax(int l, int r){
int k = log(r-l+)/log(2.0);
return max(ta[l][k], ta[r-(<<k)+][k]);
} int qmin(int l, int r){
int k = log(r-l+)/log(2.0);
return min(tb[l][k], tb[r-(<<k)+][k]);
} //左闭右开,l为起始点
int lowerbound(int l){
int lo = l, hi = n;//初始左右界桩
int ans = n;//失败返回右界桩
while(lo < hi){
int mi = (lo+hi)/;
int qa = qmax(l, mi);
int qb = qmin(l, mi);
if(qa > qb) hi = mi;
else if(qa < qb) lo = mi+;
else{
ans = min(ans, mi);//命中而左移和未命中而左移是不同的!
hi = mi;
} }
return ans;
}
int upperbound(int l){
int lo = l, hi = n;
int ans = -;
while(lo < hi){
int mi = (lo+hi)/;
int qa = qmax(l, mi);
int qb = qmin(l, mi);
if(qa > qb) hi = mi;
else if(qa < qb) lo = mi+;
else{
ans = max(ans, mi);
lo = mi+;
}
}
return ans;
} int main(){
//FREAD("689d.txt");
RINT(n);
m = ;
while(m < n) m <<= ;//扩展为2的幂
REP(n) RINT(a[i]);
REP(n) RINT(b[i]);
build_max();
build_min();
__int64 ans = ;
int rmin = , rmax = ;
REP(n){//for each left end = i, enumerate rmin, rmax
rmin = lowerbound(i);
rmax = upperbound(i);
if(rmin <= rmax)
ans += rmax - rmin + ;
//printf("left = %d, rmin = %d, rmax = %d\n", i, rmin, rmax);
}
cout << ans;
return ;
 #include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <assert.h>
#define FREAD(fn) freopen((fn), "r", stdin)
#define RINT(vn) scanf("%d", &(vn))
#define PINT(vb) printf("%d", vb)
#define RSTR(vn) scanf("%s", (vn))
#define PSTR(vn) printf("%s", (vn))
#define CLEAR(A, X) memset(A, X, sizeof(A))
#define REP(N) for(int i=0; i<(N); i++)
#define REPE(N) for(int i=1; i<=(N); i++)
#define pb(X) push_back(X)
#define pn() printf("\n")
using namespace std;
const int MAX_N = (<<);//注意要把最大值扩展到2的幂次
const int INFP = 0x7fffffff;
const int INFN = -0x7fffffff; struct Node
{
int l, r;
int v;
Node(){}
}; int n, m;//m为大于n的最小的2的幂
int a[MAX_N], b[MAX_N];
Node sta[MAX_N*], stb[MAX_N*];//这个是segment tree void build_max(int A[], Node AT[], int N){
m = ;
while(m < N) m <<= ;//m个叶节点,m-1个内部节点,下标从1开始
for(int i=; i<N; i++){
RINT(AT[m+i].v);
//AT[m+i].v = A[i];//复制叶节点到m-2m
AT[m+i].l = AT[m+i].r = i;
}
for(int i=N; i<m; i++){
AT[m+i].v = INFN;//末尾用负无穷填充
AT[m+i].l = AT[m+i].r = i;
}
for(int i=m-; i>=; i--){//自底向上生成内部节点
AT[i].v = max(AT[i*].v, AT[i*+].v);
AT[i].l = AT[i*].l;
AT[i].r = AT[i*+].r;
}
// for(int i=1; i<=m*2-1; i++)
// printf("%d %d\n", i, AT[i].v);
} void build_min(int A[], Node AT[], int N){
m = ;
while(m < N) m <<= ;//m个叶节点,m-1个内部节点,下标从1开始
for(int i=; i<N; i++){
RINT(AT[m+i].v);
//AT[m+i].v = A[i];//复制叶节点到m-2m
AT[m+i].l = AT[m+i].r = i;
}
for(int i=N; i<m; i++){
AT[m+i].v = INFP;//末尾用正无穷填充
AT[m+i].l = AT[m+i].r = i;
}
for(int i=m-; i>=; i--){//自底向上生成内部节点
AT[i].v = min(AT[i*].v, AT[i*+].v);
AT[i].l = AT[i*].l;
AT[i].r = AT[i*+].r;
}
// for(int i=1; i<=m*2-1; i++)
// printf("%d %d\n", i, AT[i].v);
} //闭区间,cur为当前子树根
int qmax(int cur, int l, int r){//其实l, r在全局的查询中不会变
if(l <= sta[cur].l && sta[cur].r <= r){
//printf("hit [%d, %d]\n", sta[cur].l, sta[cur].r);
return sta[cur].v;//当前区间包含在目标区间内
}
if(sta[cur].r < l || sta[cur].l > r) return INFN;//不相交则不再递归
else return max(qmax(cur*, l, r), qmax(cur*+, l, r));
} int qmin(int cur, int l, int r){
if(l <= stb[cur].l && stb[cur].r <= r) return stb[cur].v;
if(stb[cur].r < l || stb[cur].l > r) return INFP;
else return min(qmin(cur*, l, r), qmin(cur*+, l, r));//原来min是先算右边的,再算左边的
} //左闭右开,l为起始点
int lowerbound(int lo, int hi, int l){
int ans = n;
while(lo < hi){
int mi = (lo+hi)/;
int qa = qmax(, l, mi);
int qb = qmin(, l, mi);
if(qa > qb) hi = mi;
else if(qa < qb) lo = mi+;
else{
ans = min(ans, mi);//命中而左移和未命中而左移是不同的!
hi = mi;
} }
return ans;
}
int upperbound(int lo, int hi, int l){
int ans = ;
while(lo < hi){
int mi = (lo+hi)/;
int qa = qmax(, l, mi);
int qb = qmin(, l, mi);
if(qa > qb) hi = mi;
else if(qa < qb) lo = mi+;
else{
ans = max(ans, mi);
lo = mi+;
}
}
return ans;
} int main(){
FREAD("689d.txt");
RINT(n);
build_max(a, sta, n);
build_min(b, stb, n);
__int64 ans = ;
int rmin = , rmax = ;
REP(n){//for each left end = i, enumerate rmin, rmax
rmin = lowerbound(i, n, i);
if(rmin >= i && rmin < n){//剪枝,rmin存在,则rmax存在
rmax = upperbound(rmin, n, i);
ans += rmax - rmin + ;
}
//if(n == 190593 && i == n/2) break;//这个是为了测试时间,发现跑了一半已经快超时了
printf("left = %d, rmin = %d, rmax = %d\n", i, rmin, rmax);
}
cout << ans;
return ;
}

T了的线段树

上一篇:CocoaPods私有库管理


下一篇:用CSS里的 viewport-fit 标签应对iPhone X 的刘海