【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，最坏情况确实比线段树更快。

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <string>
  5 #include <cstdlib>
  6 #include <cctype>
  7 #include <cmath>
  8 #include <algorithm>
  9 #include <vector>
 10 #include <map>
 11 #include <set>
 12 #include <stack>
 13 #include <queue>
 14 #include <assert.h>
 15 #define FREAD(fn) freopen((fn), "r", stdin)
 16 #define RINT(vn) scanf("%d", &(vn))
 17 #define PINT(vb) printf("%d", vb)
 18 #define RSTR(vn) scanf("%s", (vn))
 19 #define PSTR(vn) printf("%s", (vn))
 20 #define CLEAR(A, X) memset(A, X, sizeof(A))
 21 #define REP(N) for(int i=0; i<(N); i++)
 22 #define REPE(N) for(int i=1; i<=(N); i++)
 23 #define pb(X) push_back(X)
 24 #define pn() printf("\n")
 25 using namespace std;
 26 const int MAX_N = (1<<20);//注意要把最大值扩展到2的幂次
 27 const int INFP = 0x7fffffff;
 28 const int INFN = -0x7fffffff;
 29
 30 int n, m;//m为大于n的最小的2的幂
 31 int a[MAX_N], b[MAX_N];
 32 int ta[MAX_N][32], tb[MAX_N][32];//spare table, t[i][j],i为起点，2^j为区间长度
 33
 34 void build_max(){
 35     for(int i=n; i<m; i++) a[i] = INFN;//负无穷填充
 36     REP(m) ta[i][0] = a[i];
 37     for(int j=1; j<__builtin_ctz(m); j++){//m即区间长度的上限
 38         for(int i=0; i+(1<<j) <= m; i++){
 39             ta[i][j] = max(ta[i][j-1], ta[i+(1<<(j-1))][j-1]);
 40         }
 41     }
 42 }
 43
 44 void build_min(){
 45     for(int i=n; i<m; i++) b[i] = INFP;//正无穷填充
 46     REP(m) tb[i][0] = b[i];
 47     for(int j=1; j<__builtin_ctz(m); j++){//m即区间长度的上限
 48         for(int i=0; i+(1<<j) <= m; i++){
 49             tb[i][j] = min(tb[i][j-1], tb[i+(1<<(j-1))][j-1]);
 50         }
 51     }
 52 }
 53
 54 //闭区间
 55 int qmax(int l, int r){
 56     int k = log(r-l+1)/log(2.0);
 57     return max(ta[l][k], ta[r-(1<<k)+1][k]);
 58 }
 59
 60 int qmin(int l, int r){
 61     int k = log(r-l+1)/log(2.0);
 62     return min(tb[l][k], tb[r-(1<<k)+1][k]);
 63 }
 64
 65 //左闭右开，l为起始点
 66 int lowerbound(int l){
 67     int lo = l, hi = n;//初始左右界桩
 68     int ans = n;//失败返回右界桩
 69     while(lo < hi){
 70         int mi = (lo+hi)/2;
 71         int qa = qmax(l, mi);
 72         int qb = qmin(l, mi);
 73         if(qa > qb) hi = mi;
 74         else if(qa < qb) lo = mi+1;
 75         else{
 76             ans = min(ans, mi);//命中而左移和未命中而左移是不同的！
 77             hi = mi;
 78         }
 79
 80     }
 81     return ans;
 82 }
 83 int upperbound(int l){
 84     int lo = l, hi = n;
 85     int ans = -1;
 86     while(lo < hi){
 87         int mi = (lo+hi)/2;
 88         int qa = qmax(l, mi);
 89         int qb = qmin(l, mi);
 90         if(qa > qb) hi = mi;
 91         else if(qa < qb) lo = mi+1;
 92         else{
 93             ans = max(ans, mi);
 94             lo = mi+1;
 95         }
 96     }
 97     return ans;
 98 }
 99
100 int main(){
101     //FREAD("689d.txt");
102     RINT(n);
103     m = 1;
104     while(m < n) m <<= 1;//扩展为2的幂
105     REP(n) RINT(a[i]);
106     REP(n) RINT(b[i]);
107     build_max();
108     build_min();
109     __int64 ans = 0;
110     int rmin = 0, rmax = 0;
111     REP(n){//for each left end = i, enumerate rmin, rmax
112         rmin = lowerbound(i);
113         rmax = upperbound(i);
114         if(rmin <= rmax)
115             ans += rmax - rmin + 1;
116         //printf("left = %d, rmin = %d, rmax = %d\n", i, rmin, rmax);
117     }
118     cout << ans;
119     return 0;

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <string>
  5 #include <cstdlib>
  6 #include <cctype>
  7 #include <cmath>
  8 #include <algorithm>
  9 #include <vector>
 10 #include <map>
 11 #include <set>
 12 #include <stack>
 13 #include <queue>
 14 #include <assert.h>
 15 #define FREAD(fn) freopen((fn), "r", stdin)
 16 #define RINT(vn) scanf("%d", &(vn))
 17 #define PINT(vb) printf("%d", vb)
 18 #define RSTR(vn) scanf("%s", (vn))
 19 #define PSTR(vn) printf("%s", (vn))
 20 #define CLEAR(A, X) memset(A, X, sizeof(A))
 21 #define REP(N) for(int i=0; i<(N); i++)
 22 #define REPE(N) for(int i=1; i<=(N); i++)
 23 #define pb(X) push_back(X)
 24 #define pn() printf("\n")
 25 using namespace std;
 26 const int MAX_N = (1<<20);//注意要把最大值扩展到2的幂次
 27 const int INFP = 0x7fffffff;
 28 const int INFN = -0x7fffffff;
 29
 30 struct Node
 31 {
 32     int l, r;
 33     int v;
 34     Node(){}
 35 };
 36
 37 int n, m;//m为大于n的最小的2的幂
 38 int a[MAX_N], b[MAX_N];
 39 Node sta[MAX_N*2], stb[MAX_N*2];//这个是segment tree
 40
 41 void build_max(int A[], Node AT[], int N){
 42     m = 1;
 43     while(m < N) m <<= 1;//m个叶节点，m-1个内部节点，下标从1开始
 44     for(int i=0; i<N; i++){
 45         RINT(AT[m+i].v);
 46         //AT[m+i].v = A[i];//复制叶节点到m-2m
 47         AT[m+i].l = AT[m+i].r = i;
 48     }
 49     for(int i=N; i<m; i++){
 50         AT[m+i].v = INFN;//末尾用负无穷填充
 51         AT[m+i].l = AT[m+i].r = i;
 52     }
 53     for(int i=m-1; i>=1; i--){//自底向上生成内部节点
 54         AT[i].v = max(AT[i*2].v, AT[i*2+1].v);
 55         AT[i].l = AT[i*2].l;
 56         AT[i].r = AT[i*2+1].r;
 57     }
 58     // for(int i=1; i<=m*2-1; i++)
 59     //     printf("%d %d\n", i, AT[i].v);
 60 }
 61
 62 void build_min(int A[], Node AT[], int N){
 63     m = 1;
 64     while(m < N) m <<= 1;//m个叶节点，m-1个内部节点，下标从1开始
 65     for(int i=0; i<N; i++){
 66         RINT(AT[m+i].v);
 67         //AT[m+i].v = A[i];//复制叶节点到m-2m
 68         AT[m+i].l = AT[m+i].r = i;
 69     }
 70     for(int i=N; i<m; i++){
 71         AT[m+i].v = INFP;//末尾用正无穷填充
 72         AT[m+i].l = AT[m+i].r = i;
 73     }
 74     for(int i=m-1; i>=1; i--){//自底向上生成内部节点
 75         AT[i].v = min(AT[i*2].v, AT[i*2+1].v);
 76         AT[i].l = AT[i*2].l;
 77         AT[i].r = AT[i*2+1].r;
 78     }
 79     // for(int i=1; i<=m*2-1; i++)
 80     //     printf("%d %d\n", i, AT[i].v);
 81 }
 82
 83 //闭区间,cur为当前子树根
 84 int qmax(int cur, int l, int r){//其实l, r在全局的查询中不会变
 85     if(l <= sta[cur].l && sta[cur].r <= r){
 86         //printf("hit [%d, %d]\n", sta[cur].l, sta[cur].r);
 87         return sta[cur].v;//当前区间包含在目标区间内
 88     }
 89     if(sta[cur].r < l || sta[cur].l > r) return INFN;//不相交则不再递归
 90     else return max(qmax(cur*2, l, r), qmax(cur*2+1, l, r));
 91 }
 92
 93 int qmin(int cur, int l, int r){
 94     if(l <= stb[cur].l && stb[cur].r <= r) return stb[cur].v;
 95     if(stb[cur].r < l || stb[cur].l > r) return INFP;
 96     else return min(qmin(cur*2, l, r), qmin(cur*2+1, l, r));//原来min是先算右边的，再算左边的
 97 }
 98
 99 //左闭右开，l为起始点
100 int lowerbound(int lo, int hi, int l){
101     int ans = n;
102     while(lo < hi){
103         int mi = (lo+hi)/2;
104         int qa = qmax(1, l, mi);
105         int qb = qmin(1, l, mi);
106         if(qa > qb) hi = mi;
107         else if(qa < qb) lo = mi+1;
108         else{
109             ans = min(ans, mi);//命中而左移和未命中而左移是不同的！
110             hi = mi;
111         }
112
113     }
114     return ans;
115 }
116 int upperbound(int lo, int hi, int l){
117     int ans = 0;
118     while(lo < hi){
119         int mi = (lo+hi)/2;
120         int qa = qmax(1, l, mi);
121         int qb = qmin(1, l, mi);
122         if(qa > qb) hi = mi;
123         else if(qa < qb) lo = mi+1;
124         else{
125             ans = max(ans, mi);
126             lo = mi+1;
127         }
128     }
129     return ans;
130 }
131
132 int main(){
133     FREAD("689d.txt");
134     RINT(n);
135     build_max(a, sta, n);
136     build_min(b, stb, n);
137     __int64 ans = 0;
138     int rmin = 0, rmax = 0;
139     REP(n){//for each left end = i, enumerate rmin, rmax
140         rmin = lowerbound(i, n, i);
141         if(rmin >= i && rmin < n){//剪枝，rmin存在，则rmax存在
142             rmax = upperbound(rmin, n, i);
143             ans += rmax - rmin + 1;
144         }
145         //if(n == 190593 && i == n/2) break;//这个是为了测试时间，发现跑了一半已经快超时了
146         printf("left = %d, rmin = %d, rmax = %d\n", i, rmin, rmax);
147     }
148     cout << ans;
149     return 0;
150 }

T了的线段树

时间： 2024-11-01 14:34:16

【CF689D Friends and Subsequences】二分搜索，区间查询的相关文章

Distinct Subsequences -- LeetCode

原题链接: http://oj.leetcode.com/problems/distinct-subsequences/ 这道题应该很容易感觉到是动态规划的题目.还是老套路,先考虑我们要维护什么量.这里我们维护res[i][j],对应的值是S的前i个字符和T的前j个字符有多少个可行的序列(注意这道题是序列,不是子串,也就是只要字符按照顺序出现即可,不需要连续出现).下面来看看递推式,假设我们现在拥有之前的历史信息,我们怎么在常量操作时间内得到res[i][j].假设S的第i个字符和T的第j个字符

POJ 3468 线段树 区间更新区间查询

题意:给出一段数列,任意区间加上一个整数v,任意区间查询.给出N个数,Q次操作. 线段树的题,延迟指针不更新到底就行了. #include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxn 100005 long long sum[maxn<<2],col[maxn<<2]; void

thinkphp区间查询、统计查询与SQL直接查询实例分析_php实例

本文实例讲述了thinkphp区间查询.统计查询与SQL直接查询.分享给大家供大家参考.具体方法如下: 一.区间查询: 复制代码 代码如下: $data['id']=array(array('gt',4),array('lt',10));//默认关系是(and)并且的关系  //SELECT * FROM `tp_user` WHERE ( (`id` > 4) AND (`id` < 10) )    $data['id']=array(array('gt',4),array('lt',10

c++-一个二分搜索的递归函数问题

问题描述 一个二分搜索的递归函数问题 使用函数 int binarysearch(int tint x[]int n);编写递归二分搜索算法,并且不使用其它辅助递归函数. 然后我编写的了如下代码:int search(int tint x[]int n){ int low=(n-1)/2; if( x > x+n ) return -1;if( t > x[low] ){ search(tx+low+1n);}else if( t < low ){ search(txlow+2);}el

access数据库-access时间段的区间查询

问题描述 access时间段的区间查询 在access中,我需要在一个查询中实现[时间段]的[区间查询],比如表1:计划项目(text),计划开始时间例如 1月1日(date),时长例如13周(number)需要查询从3月1日到3月31日之间的计划项目,剩余时间 该如何设计谢谢比如表:[合同名称] [合同日期] [周数] A 12/01/2014 52B 05/05/2013 26 C 05/02/2014 26D 15/12/2013 26查询时间段 [开始时间] [结束时间]例如[01/01

C#文本框中如何编写二分搜索？如何二分搜索文本框？二分搜索的C#怎么写？

问题描述 C#文本框中如何编写二分搜索?如何二分搜索文本框?二分搜索的C#怎么写? C#文本框中如何编写二分搜索?如何二分搜索文本框?二分搜索的C#怎么写? 解决方案 文本框和二分搜索没有关系 参考:http://trsiemens.blog.sohu.com/82302528.html 把int i = int.Parse(Console.ReadLine()); 修改为int i = int.Parse(textBox1.Text); 解决方案二: 文本框怎么进行二分搜索,,

Ruby实现二分搜索(二分查找)算法的简单示例_ruby专题

在计算机科学中,二分搜索(英语:binary search),也称折半搜索(英语:half-interval search).对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法.搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束:如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较.如果在某一步骤数组为空,则代表找不到.这种搜索算法每一次比较都使搜索范围缩小一半

二分搜索-切蛋糕

题目1551:切蛋糕 时间限制:1 秒内存限制:128 兆特殊判题:否提交:266 解决:90 题目描述: 有如下图半价为R的圆形蛋糕,被切一刀后(图中红色直线 ),分成两个部分(黄色和绿色),已知其比例为r,求刀 痕长度(图中红色直线). 输入: 输入包括多组测试数据,包括一个整数R(1<=R<=1000),和一 个浮点数r(0<r<1),精确到第四位小数. 输出: 对于每组测试用例,输出一个浮点数,代表刀痕的长度,保 留二位小数. 样例输入: 1000 0.5000 500 0

《编程珠玑（第2版•修订版）》—第2章2.2节无处不在的二分搜索

2.2 无处不在的二分搜索我想到的一个数在1到100之间,你来猜猜看.50?太小了.75?太大了.如此,游戏进行下去,直到你猜中我想到的数为止.如果我的整数位于1到n之间,那么你可以在log2n次之内猜中.如果n是1 000,10次就可以完成:如果n是100万,则最多20次就可以完成. 这个例子引出了一项可以解决众多编程问题的技术:二分搜索.初始条件是已知一个对象存在于一个给定的范围内,而一次探测操作可以告诉我们该对象是否低于.等于或高于给定的位置.二分搜索通过重复探测当前范围的中点来定位对象.