网站建设属于应用软件吗,广东省建设监理协会信息管理网站,观澜建网站,舟山建设信息港https://www.luogu.org/problemnew/show/P4755 考虑分治#xff0c;在 [l, r] 区间中用线段树找到最大的一个点#xff0c;处理经过它的可行数对的个数#xff0c;统计个数可以离线树状数组处理 因为最多被分成 2n 个区间#xff08;像线段树一样#xff09;#xff0c;对…https://www.luogu.org/problemnew/show/P4755 考虑分治在 [l, r] 区间中用线段树找到最大的一个点处理经过它的可行数对的个数统计个数可以离线树状数组处理 因为最多被分成 2n 个区间像线段树一样对于每个区间使用类似于启发式合并的思想将要处理的区间放到 vector 里面最多有 n log n 个查询复杂度 n log^2 n #include bits/stdc.h
#define For(i, a, b) for(int i a; i b; i)
using namespace std;typedef unsigned long long ull;
typedef long long ll;template typename _T
inline void read(_T f) {f 0; _T fu 1; char c getchar();while(c 0 || c 9) {if(c -) fu -1; c getchar();}while(c 0 c 9) {f (f 3) (f 1) (c 15); c getchar();}f * fu;
}const int N 1e5 5;int Max[N 2], wz[N 2], a[N], pre[N], f[N];
long long ans;
int n, len;void build(int u, int l, int r) {if(l r) {Max[u] a[l];wz[u] l;return;}int mid (l r) 1;build(u 1, l, mid);build(u 1 | 1, mid 1, r);if(Max[u 1] Max[u 1 | 1]) Max[u] Max[u 1], wz[u] wz[u 1];else Max[u] Max[u 1 | 1], wz[u] wz[u 1 | 1];
}int Q1, Q2;void query(int u, int l, int r, int L, int R) {if(l L R r) {if(Max[u] Q1) {Q1 Max[u];Q2 wz[u];}return;}int mid (L R) 1;if(mid l) query(u 1, l, r, L, mid);if(mid 1 r) query(u 1 | 1, l, r, mid 1, R);
}int lowbit(int x) {return x -x;}
void add(int x) {for(int i x; i n; i lowbit(i)) f[i];}
int query(int x) {int ans 0; for(int i x; i; i - lowbit(i)) ans f[i]; return ans;}struct ele {int l, r, v;bool operator (const ele A) const {return v A.v;}ele (int a, int b, int c) : l(a), r(b), v(c) {}ele () {}
};vector ele Q;
vector int t[N];void solve(int l, int r) {if(l r) return;Q1 0; query(1, l, r, 1, n);int L Q2 - l, R r - Q2; int tmp Q2;if(L R) for(int i l; i Q2; i) { Q.push_back(ele(Q2, r, pre[Q1] / pre[a[i]])); }else for(int i Q2; i r; i) Q.push_back(ele(l, Q2, pre[Q1] / pre[a[i]]));solve(l, tmp - 1); solve(tmp 1, r);
}int main() {cin n;for(int i 1; i n; i) { read(a[i]), pre[i] a[i]; };sort(pre 1, pre n 1); len unique(pre 1, pre n 1) - pre - 1;for(int i 1; i n; i) a[i] lower_bound(pre 1, pre len 1, a[i]) - pre;build(1, 1, n); solve(1, n);for(vector ele :: iterator it Q.begin(); it ! Q.end(); it) it - v upper_bound(pre 1, pre len 1, it - v) - pre - 1;for(int i 1; i n; i) t[a[i]].push_back(i);sort(Q.begin(), Q.end()); int LEN Q.size(), now 0;for(int i 0; i len; i) {for(vector int :: iterator it t[i].begin(); it ! t[i].end(); it) add(*it);while(Q[now].v i now LEN) {ans (long long)(query(Q[now].r) - query(Q[now].l - 1));now;}}cout ans endl;return 0;
} 转载于:https://www.cnblogs.com/LJC00118/p/9712365.html
