差旅网站建设,做网站一般多少钱,公众号app下载,做淘宝还是京东还是做网站分治 主席树。 设$solve(l, r)$表示当前处理到$[l, r]$区间的情况#xff0c;我们可以找到$[l, r]$中最大的一个数的位置$mid$#xff0c;然后扫一半区间计算一下这个区间的答案。 注意#xff0c;这时候左半边是$[l, mid]$#xff0c;而右区间是$[mid, r]$#xff0c;我…分治 主席树。 设$solve(l, r)$表示当前处理到$[l, r]$区间的情况我们可以找到$[l, r]$中最大的一个数的位置$mid$然后扫一半区间计算一下这个区间的答案。 注意这时候左半边是$[l, mid]$而右区间是$[mid, r]$我们在这个区间处理的时候要算完所有$mid$的情况然后我们每一次分治的时候去处理$solve(l, mid - 1)$和$solve(mid 1, r)$要不然当$mid$是端点的时候就会无限递归下去。 问题转化快速算出一个区间内$\leq$一个数的数只要一棵主席树就可以解决了区间最大值可以用$ST$表维护出来。 我们每一次选取一个比较短的区间去枚举然后算另一个区间的答案这样子每一次计算区间的长度至少减少一半这样子可以保证时间复杂度。 时间复杂度$O(nlog^2n)$。 Code #include cstdio
#include cstring
#include cmath
#include algorithm
using namespace std;
typedef long long ll;const int N 1e5 5;
const int Lg 20;
const ll inf 1LL 60; int n, tot 0;
ll ans 0LL, a[N], num[N];template typename T
inline void read(T X) {X 0; char ch 0; T op 1;for(; ch 9 || ch 0; ch getchar())if(ch -) op -1;for(; ch 0 ch 9; ch getchar())X (X 3) (X 1) ch - 48;X * op;
}template typename T
inline void chkMax(T x, T y) {if(y x) x y;
}namespace ST {int st[N][Lg], len[N];inline int bet(int x, int y) {return a[x] a[y] ? x : y;}inline void prework() {for(int j 1; j 18; j)for(int i 1; i (1 j) - 1 n; i)st[i][j] bet(st[i][j - 1], st[i (1 (j - 1))][j - 1]);}inline int qMax(int x, int y) {int k len[y - x 1];return bet(st[x][k], st[y - (1 k) 1][k]);}} using namespace ST;namespace SegT {struct Node {int lc, rc;ll sum;} s[N * 40];int root[N], nodeCnt 0;#define lc(p) s[p].lc#define rc(p) s[p].rc#define sum(p) s[p].sum#define mid ((l r) 1)void ins(int p, int l, int r, int x, int pre) {s[p nodeCnt] s[pre];sum(p);if(l r) return;if(x mid) ins(lc(p), l, mid, x, lc(pre));else ins(rc(p), mid 1, r, x, rc(pre));}ll query(int r1, int r2, int l, int r, int x, int y) {if(x y) return 0LL;if(x l y r) return sum(r2) - sum(r1);ll res 0LL;if(x mid) res query(lc(r1), lc(r2), l, mid, x, y);if(y mid) res query(rc(r1), rc(r2), mid 1, r, x, y);return res;}#undef mid} using namespace SegT;void solve(int l, int r) {if(l r) return;int mid qMax(l, r);if(mid - l r - mid) {for(int i l; i mid; i) {int pos upper_bound(num 1, num 1 tot, (ll) (num[a[mid]] / num[a[i]])) - num - 1;ans query(root[mid - 1], root[r], 1, tot, 1, pos);} } else {for(int i mid; i r; i) {int pos upper_bound(num 1, num 1 tot, (ll) (num[a[mid]] / num[a[i]])) - num - 1;ans query(root[l - 1], root[mid], 1, tot, 1, pos);}}solve(l, mid - 1), solve(mid 1, r);
}int main() {read(n);for(int i 1; i n; i) {read(a[i]);len[i] log2(i), st[i][0] i;num[tot] a[i];}prework();num[tot] inf;sort(num 1, num 1 tot);tot unique(num 1, num tot 1) - num - 1;for(int i 1; i n; i) {a[i] lower_bound(num 1, num 1 tot, a[i]) - num;ins(root[i], 1, tot, a[i], root[i - 1]);}/* for(int i 1; i n; i) printf(%lld , a[i]);printf(\n); */solve(1, n);printf(%lld\n, ans);return 0;
} View Code 转载于:https://www.cnblogs.com/CzxingcHen/p/9905867.html
