CodeForces 671C - Ultimate Weirdness of an Array

タイトル:

 ， F（l， r）   A[1:n] 
A[1....(l-1),(r+1)...n]    。

考え方:

    H[i]   F(l, r) <= i   （l，r）  。
    V[A[i]] = { b1, b2, .... bk },   A[i] % bx == 0
     next  
      next[j] = k,   F(l, k) <= i, k  。
      k  ，   next[j] = n+1;（ ，  ）
      :

      next[j] ，   n-next[j]+1 。

Code：

#include 
#define lson l , m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long LL;
const LL maxn = 200000 + 131;
const LL MaxN = 200000;
struct node {
    LL Max, Min;
    LL Sum, Flag;
};

node Node[maxn<<2];
LL H[maxn], A[maxn], Idx[maxn];
LL L1[maxn], L2[maxn], R1[maxn], R2[maxn];

///SegmentTree
void PushUp(LL rt) {
    Node[rt].Max = max(Node[rt<<1].Max, Node[rt<<1|1].Max);
    Node[rt].Min = min(Node[rt<<1].Min, Node[rt<<1|1].Min);
    Node[rt].Sum = Node[rt<<1].Sum + Node[rt<<1|1].Sum;
}
void PushDown(LL l, LL r, LL rt) {
    LL m = (l + r) >> 1;
    if(Node[rt].Flag)
    {
        Node[rt<<1].Flag = Node[rt<<1].Max = Node[rt<<1].Min = Node[rt].Flag;
        Node[rt<<1|1].Flag = Node[rt<<1|1].Max = Node[rt<<1|1].Min = Node[rt].Flag;
        Node[rt<<1].Sum = Node[rt].Flag * (m - l + 1);
        Node[rt<<1|1].Sum = Node[rt].Flag * (r - m);
        Node[rt].Flag = 0;
    }
}
void Build(LL l, LL r, LL rt) {
    Node[rt].Flag = 0;
    if(l == r) {
        Node[rt].Max = Node[rt].Min = Node[rt].Sum = l;
        return ;
    }
    LL m = (l + r) >> 1;
    Build(lson), Build(rson);
    PushUp(rt);
}
void Update_section(LL L, LL R, LL val, LL l, LL r, LL rt) {
    if(L > R) return ;
    if(Node[rt].Min >= val) return ;
    if(L <= l and r <= R and Node[rt].Max <= val) {
        Node[rt].Flag = val;
        Node[rt].Min = Node[rt].Max = val;
        Node[rt].Sum = LL(r - l + 1) * LL(val);
        return ;
    }
    PushDown(l, r, rt);
    LL m = (l + r) >> 1;
    if(L <= m) Update_section(L, R, val, lson);
    if(R > m)  Update_section(L, R, val, rson);
    PushUp(rt);
}
/// Solve
int main() {
     std::ios::sync_with_stdio(false);
     LL n;
     cin >> n;
     for(LL i = 1; i <= n; ++i) {
        cin >> A[i];
        Idx[A[i]] = i;
     }
     /// Get l(1, b1) -> bk-1, (b1,b2) -> bk, (b2, n) -> n+1
     for(LL i = 1; i <= MaxN; ++i)
     {
         for(LL j = i; j <= MaxN; j +=i)
         if(Idx[j])
         {
             if(L1[i] == 0 or L1[i] > Idx[j]) L2[i] = L1[i], L1[i] = Idx[j];
             else if(L2[i] == 0 or L2[i] > Idx[j]) L2[i] = Idx[j];
             if(R1[i] < Idx[j]) R2[i] = R1[i], R1[i] = Idx[j];
             else if(R2[i] < Idx[j]) R2[i] = Idx[j];
         }
     }
     /// Build Tree
     Build(1,n,1);
     for(LL i = MaxN; i > 0; --i)
     {
         if(L1[i] != R1[i])
         {
             Update_section(1,L1[i],R2[i], 1, n, 1);
             Update_section(L1[i]+1, L2[i], R1[i], 1, n, 1);
             Update_section(L2[i]+1, n, n+1, 1, n, 1);
         }
         H[i] = LL(n*(n+1)) - Node[1].Sum;
         //cout << H[i] << endl;
     }
     LL Ans = 0;
     for(LL i = 1; i < MaxN; ++i)
        Ans += i * (H[i+1]-H[i]);
     cout << Ans <return 0;
}