建设网站教程全集,wordpress 列表函数,中企动力上班怎么样,苏州百度seo关键词优化Ultimate Weirdness of an Array 写不出来#xff0c; 日常好菜啊。。 考虑枚举GCD#xff0c; 算出一共有多少个对 f(l, r) GCD#xff0c; 我们用fuc[ i ] 表示的是在 l i 这个位置开始, 最小的合法的 R#xff0c; 可以发现这个函数随 i 单调不下降#xff0c; …Ultimate Weirdness of an Array 写不出来 日常好菜啊。。 考虑枚举GCD 算出一共有多少个对 f(l, r) GCD 我们用fuc[ i ] 表示的是在 l i 这个位置开始, 最小的合法的 R 可以发现这个函数随 i 单调不下降 枚举GCD 的时候 找到GCD 的倍数的位置 用线段树更新最大值。 #includebits/stdc.h
#define LL long long
#define LD long double
#define ull unsigned long long
#define fi first
#define se second
#define mk make_pair
#define PLL pairLL, LL
#define PLI pairLL, int
#define PII pairint, int
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(), (x).end()
#define fio ios::sync_with_stdio(false); cin.tie(0);using namespace std;const int N 2e5 7;
const int inf 0x3f3f3f3f;
const LL INF 0x3f3f3f3f3f3f3f3f;
const int mod 998244353;
const double eps 1e-8;
const double PI acos(-1);templateclass T, class S inline void add(T a, S b) {a b; if(a mod) a - mod;}
templateclass T, class S inline void sub(T a, S b) {a - b; if(a 0) a mod;}
templateclass T, class S inline bool chkmax(T a, S b) {return a b ? a b, true : false;}
templateclass T, class S inline bool chkmin(T a, S b) {return a b ? a b, true : false;}int n, a[N];
int maxPos[N][2];
int minPos[N][2];
int cnt[N];
LL H[N];
int mx[2], mn[2], tot;#define lson l, mid, rt 1
#define rson mid 1, r, rt 1 | 1
struct segmentTree {LL sum[N 2]; int lazy[N 2], mn[N 2], mx[N 2];inline void pull(int rt) {sum[rt] sum[rt 1] sum[rt 1 | 1];mx[rt] max(mx[rt 1], mx[rt 1 | 1]);mn[rt] min(mn[rt 1], mn[rt 1 | 1]);}inline void push(int rt, int l, int r) {if(~lazy[rt]) {int mid l r 1;sum[rt 1] 1LL * (mid - l 1) * lazy[rt];sum[rt 1 | 1] 1LL * (r - mid) * lazy[rt];lazy[rt 1] lazy[rt 1 | 1] lazy[rt];mx[rt 1] mn[rt 1] lazy[rt];mx[rt 1 | 1] mn[rt 1 | 1] lazy[rt];lazy[rt] -1;}}void build(int l, int r, int rt) {lazy[rt] -1;if(l r) {sum[rt] l;mx[rt] l;mn[rt] l;return;}int mid l r 1;build(lson); build(rson);pull(rt);}void update(int L, int R, int val, int l, int r, int rt) {if(R l || r L || R L) return;if(mn[rt] val) return;if(L l r R mx[rt] val) {sum[rt] 1LL * (r - l 1) * val;mx[rt] val;mn[rt] val;lazy[rt] val;return;}if(l r) return;push(rt, l, r);int mid l r 1;update(L, R, val, lson);update(L, R, val, rson);pull(rt);}
} Tree;int main() {memset(maxPos, 0xc0, sizeof(maxPos));memset(minPos, 0x3f, sizeof(minPos));scanf(%d, n);for(int i 1; i n; i) {scanf(%d, a[i]);cnt[a[i]];if(i maxPos[a[i]][0]) {maxPos[a[i]][1] maxPos[a[i]][0];maxPos[a[i]][0] i;} else if(i maxPos[a[i]][1]) maxPos[a[i]][1] i;if(i minPos[a[i]][0]) {minPos[a[i]][1] minPos[a[i]][0];minPos[a[i]][0] i;} else if(i minPos[a[i]][1]) minPos[a[i]][1] i;}Tree.build(1, n, 1);for(int v 200000; v 0; v--) {H[v] 1LL * n * n - Tree.sum[1] n;if(!v) break;mx[0] mx[1] -inf - 1;mn[0] mn[1] inf;tot 0;for(int w v; w 200000; w v) {if(maxPos[w][0] -inf - 1) continue;if(maxPos[w][0] mx[0]) mx[1] mx[0], mx[0] maxPos[w][0];else if(maxPos[w][0] mx[1]) mx[1] maxPos[w][0];if(maxPos[w][1] mx[0]) mx[1] mx[0], mx[0] maxPos[w][1];else if(maxPos[w][1] mx[1]) mx[1] maxPos[w][1];if(minPos[w][0] mn[0]) mn[1] mn[0], mn[0] minPos[w][0];else if(minPos[w][0] mn[1]) mn[1] minPos[w][0];if(minPos[w][1] mn[0]) mn[1] mn[0], mn[0] minPos[w][1];else if(minPos[w][1] mn[1]) mn[1] minPos[w][1];tot cnt[w];}if(tot 2) {int p1 mn[0], p2 mn[1];Tree.update(1, p1, p1, 1, n, 1);Tree.update(p1 1, p2, p2, 1, n, 1);Tree.update(p2 1, n, n 1, 1, n, 1);} else if(tot 3) {int p1 mn[0], p2 mn[1], p3 mx[0];Tree.update(1, p1, p2, 1, n, 1);Tree.update(p1 1, p2, p3, 1, n, 1);Tree.update(p2 1, n, n 1, 1, n, 1);} else if(tot 3){int p1 mn[0], p2 mn[1], p3 mx[1], p4 mx[0];Tree.update(p2 1, n, n 1, 1, n, 1);Tree.update(p1 1, p2, p4, 1, n, 1);Tree.update(1, p1, p3, 1, n, 1);}}LL ans 0;for(int i 1; i 200000; i)ans (H[i] - H[i - 1]) * i;printf(%lld\n, ans);return 0;
}/*
*/ 转载于:https://www.cnblogs.com/CJLHY/p/10978952.html
