部分题目来自《算法竞赛设计进阶》
问题
给定一个长度为n的数列A，有m个询问，每次给定一个整数T，求出最大的k，满足a[1]，a[2]……a[k]的和小于等于T（不会打sigma）
第一反应是二分，这个时候的复杂度是logn
还有第二种解法，用倍增的思想，复杂度为logk（所求答案）。显然倍增要好很多。我讲讲倍增。
如果是暴力的话显然是从前往后一个一个枚举来计算。这里每次只往后移了一格，我们能不能一下子移很多格呢？
当然可以，我们可以用倍增的思想，第一次移1格，第二次移2格……如果再移就超过答案，就把移的格数除以2。如果最后移的格数是0，那么这一格就是答案
#include<cstdio>
#include<cctype>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 100 + 10;
int a[MAXN], s[MAXN], n, m, sum;void read(int& x)
{int f = 1; x = 0; char ch = getchar();while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); } while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } x *= f;
}int main()
{read(n); read(m);_for(i, 1, n) read(a[i]), s[i] = s[i-1] + a[i];while(m--){int T; read(T);int k = 0, p = 1, sum = 0; //k为当前在哪一格，p为下一步要移多少格，sum为已经走了的格的总和 while(p){if(k + p <= n && sum + s[k + p] - s[k] <= T) {sum += s[k + p] - s[k];k += p;p <<= 1;}else p >>= 1;}printf("%d\n", k);}return 0;
}
hihocoder#1384
发现倍增的套路和二分有点像。出题就出来判断区间是否合法上
这里值得一提的是可以把新加进入的数组sort一遍，然后和之前已经
有序的数组做一次归并，而不用从头再来sort
//这个程序WA，目前还不知道为什么
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cmath>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int MAXN = 5e5 + 10;
int n, m, a[MAXN];
int b[MAXN], t[MAXN];
ll T;inline void read(int& x)
{int f = 1; x = 0; char ch = getchar();while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }x *= f;
}inline void readll(ll& x)
{ll f = 1; x = 0; char ch = getchar();while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }x *= f;
}void merge_sort(int L, int R, int p)
{_for(i, R + 1, R + p) b[i] = a[i];sort(b + R + 1, b + R + p + 1);int i = L, pos = L, j = R + 1;while(i <= R || j <= R + p){if(j > R + p || i <= R && a[i] < b[j]) t[pos++] = a[i++];else t[pos++] = b[j++];}_for(i, L, R + p) a[i] = t[i];
}bool check(int L, int R, int p)
{merge_sort(L, R, p);ll res = 0;int l = L, r = R + p, tmp = m;while(tmp--){if(l >= r) break;res += (a[r] - a[l]) * (a[r] - a[l]);if(res > T) return false;r--; l++;}return true;
}int main()
{int t; read(t);while(t--){read(n); read(m); readll(T);_for(i, 1, n) read(a[i]);int L = 1, R, ans = 0, p;while(L <= n){R = L; p = 1;ans++;while(p){if(R + p <= n && check(L, R, p)) //{R += p;p <<= 1;}else p >>= 1;} L = R + 1;}printf("%d\n", ans);}return 0;
}
RMQ算法模板 poj 3264（快速求区间最值，不支持修改）
#include<cstdio>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 8e4;
const int MAXM = 30;
int dmin[MAXN][MAXM], dmax[MAXN][MAXM], a[MAXN], n, q;void RMQ_init()
{_for(i, 1, n) dmin[i][0] = dmax[i][0] = a[i];for(int j = 1; (1 << j) <= n; j++)for(int i = 1; i + (1 << j) - 1 <= n; i++){dmax[i][j] = max(dmax[i][j-1], dmax[i + (1 << (j-1))][j-1]);dmin[i][j] = min(dmin[i][j-1], dmin[i + (1 << (j-1))][j-1]);}
}int RMQ_ans(int l, int r)
{int k = 0;while((1 << (k + 1)) <= r - l + 1) k++;return max(dmax[l][k], dmax[r - (1 << k) + 1][k]) - min(dmin[l][k], dmin[r - (1 << k) + 1][k]);
}int main()
{scanf("%d%d", &n, &q);_for(i, 1, n) scanf("%d", &a[i]);RMQ_init();while(q--){int l, r;scanf("%d%d", &l, &r);printf("%d\n", RMQ_ans(l, r));}return 0;
}