HackerRank The Strange Function problem solution

In this HackerRank The Strange Function problem you need to complete the function maximumValue which takes an integer array as input and returns the maximum value of f among all subsegments [l,r].

HackerRank The Strange Function problem solution


Problem solution in Python programming.

from math import gcd

def parseInput(f):
    return [f(x) for x in input().split()]

n=int(input())
array=parseInput(int)
stack=[]
answer=float('-inf')
for number in array:
    for i in range(len(stack)):
        stack[i][0]=gcd(abs(stack[i][0]),abs(number))
        stack[i][1]+=number
        if number > stack[i][2]:
            stack[i][1]-=number-stack[i][2]
            stack[i][2]=number

    stack.append([number,0,number])
    newStack=[]
    for i in range(len(stack)):
        if newStack and newStack[-1][0] == stack[i][0]:
            if newStack[-1][1] <= stack[i][1]:
                if newStack[-1][1]+newStack[-1][2] > stack[i][1]+stack[i][2]:
                    newStack.append(stack[i])
                    continue
                newStack[-1][1]=stack[i][1]
                newStack[-1][2]=stack[i][2]
        else:
            newStack.append(stack[i])
    stack = newStack[:]
    answer=max(answer,max(abs(stack[i][0])*stack[i][1] for i in range(len(stack))))
print(answer)


Problem solution in Java Programming.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
import java.util.TreeMap;

public class Solution98 {
    static final Scanner scanner = new Scanner(System.in);
    static class Segment {
        int left, right, val;
        Segment(int left, int right, int val) {
            this.left = left;
            this.right = right;
            this.val = val;
        }
    }
    private static int gcd(int x, int y) {
        if (y == 0) {
            return x;
        }
        return gcd(y, x % y);
    }

    public static void main(String[] args) {
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        long ans = 0;
        long sum = 0;
        TreeMap<Integer, Integer> tmap = new TreeMap<>();
        SegmentTree tree = new SegmentTree(n);
        Deque<Segment> dq = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            TreeMap<Integer, Integer> segmentTree = new TreeMap<>();
            for (int j : tmap.keySet()) {
                int k = gcd(j, Math.abs(a[i]));
                int idx = tmap.get(j);
                if (segmentTree.containsKey(k)) {
                    int cur = segmentTree.get(k);
                    segmentTree.put(k, Math.min(idx, cur));
                } else {
                    segmentTree.put(k, idx);
                }
            }
            if (segmentTree.containsKey(Math.abs(a[i]))) {
                int j = segmentTree.get(Math.abs(a[i]));
                segmentTree.put(Math.abs(a[i]), Math.min(i, j));
            } else {
                segmentTree.put(Math.abs(a[i]), i);
            }
            tmap = segmentTree;
            tree.add(i, i, sum);

            Segment s = new Segment(i, i, a[i]);
            while (!dq.isEmpty() && dq.getLast().val <= a[i]) {
                tree.add(dq.getLast().left, dq.getLast().right, -dq.getLast().val);
                s.left = dq.getLast().left;
                dq.removeLast();
            }
            tree.add(s.left, s.right, s.val);
            dq.addLast(s);
            sum += a[i];
            for (int j : tmap.keySet()) {
                int pos = tmap.get(j);
                ans = Math.max(ans, j * (sum - tree.get(pos, i)));
            }
        }

        System.out.println(ans);
    }
}

class SegmentTree {
    private int n;
    private long[] min, add;

    SegmentTree(int size) {
        n = 1;
        while (n < size) {
            n *= 2;
        }
        min = new long[2 * n];
        add = new long[2 * n];
    }

    private void clear(int i, int l, int r) {
        min[i] = 0;
        add[i] = 0;
        if (l == r - 1) {
            return;
        }
        int tm = (l + r) / 2;
        clear(2 * i + 1, l, tm);
        clear(2 * i + 2, tm, r);
    }

    void clear(int n) {
        this.n = n;
        clear(0, 0, n);
    }

    private void push(int i, int tl, int tr) {
        min[i] += add[i];
        if (tl != tr - 1) {
            add[2 * i + 1] += add[i];
            add[2 * i + 2] += add[i];
        }
        add[i] = 0;
    }

    private void add(int i, int lt, int rt, int l, int r, long diff) {
        push(i, lt, rt);
        if (l >= rt || r <= lt) {
            return;
        }

        if (l <= lt && rt <= r) {
            add[i] += diff;
            push(i, lt, rt);
            return;
        }

        int tm = (lt + rt) / 2;
        add(2 * i + 1, lt, tm, l, r, diff);
        add(2 * i + 2, tm, rt, l, r, diff);
        min[i] = Math.min(min[2 * i + 1], min[2 * i + 2]);
    }

    private long get(int i, int lt, int rt, int l, int r) {
        push(i, lt, rt);
        if (l >= rt || r <= lt) {
            return Long.MAX_VALUE;
        }

        if (l <= lt && rt <= r) {
            return min[i];
        }

        int tm = (lt + rt) / 2;
        return Math.min(get(2 * i + 1, lt, tm, l, r), get(2 * i + 2, tm, rt, l, r));
    }

    void add(int l, int r, long diff) {
        add(0, 0, n, l, r + 1, diff);
    }

    long get(int l, int r) {
        return get(0, 0, n, l, r + 1);
    }
}


Problem solution in C++ programming.

#include <bits/stdc++.h>
using namespace std;
 
#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define pconent(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int FFTMOD = 1007681537;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ll isqrt(ll k) {ll r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
#define db(x) cerr << #x << " = " << (x) << " ";
#define endln cerr << "\n";

template<class T> struct MINRMQ {
    int n;
    vector<T> a;
    vector<vector<T> > f;

    T best(T a, T b) {
        return min(a, b);
    }
    void init(int n) {
        this->n = n;
        int p = 1; while ((1 << p) < n) p++;
        a.resize(n), f.resize(p + 1);
        for (int i = 0; i < (int) f.size(); i++) {
            f[i].resize(n);
        }
    }
    void upd(int u, T x) {
        a[u] = x;
    }
    void build() {
        for (int i = 0; i < n; i++) f[0][i] = a[i];
        for (int l = 0, k; (k = 1 << l) < n; l++) {
            for (int i = 0; i + k < n; i++) {
                f[l + 1][i] = best(f[l][i], f[l][i + k]);
            }
        }
    }
    T query(int a, int b) {
        int l = a == b ? 0 : __lg(b - a);
        return best(f[l][a], f[l][b - (1 << l) + 1]);
    }
};
template<class T> struct MAXRMQ {
    int n;
    vector<T> a;
    vector<vector<T> > f;

    T best(T a, T b) {
        return max(a, b);
    }
    void init(int n) {
        this->n = n;
        int p = 1; while ((1 << p) < n) p++;
        a.resize(n), f.resize(p + 1);
        for (int i = 0; i < (int) f.size(); i++) {
            f[i].resize(n);
        }
    }
    void upd(int u, T x) {
        a[u] = x;
    }
    void build() {
        for (int i = 0; i < n; i++) f[0][i] = a[i];
        for (int l = 0, k; (k = 1 << l) < n; l++) {
            for (int i = 0; i + k < n; i++) {
                f[l + 1][i] = best(f[l][i], f[l][i + k]);
            }
        }
    }
    T query(int a, int b) {
        int l = a == b ? 0 : __lg(b - a);
        return best(f[l][a], f[l][b - (1 << l) + 1]);
    }
};
template<class T> struct GCDRMQ {
    int n;
    vector<T> a;
    vector<vector<T> > f;

    T best(T a, T b) {
        return __gcd(abs(a), abs(b));
    }
    void init(int n) {
        this->n = n;
        int p = 1; while ((1 << p) < n) p++;
        a.resize(n), f.resize(p + 1);
        for (int i = 0; i < (int) f.size(); i++) {
            f[i].resize(n);
        }
    }
    void upd(int u, T x) {
        a[u] = x;
    }
    void build() {
        for (int i = 0; i < n; i++) f[0][i] = a[i];
        for (int l = 0, k; (k = 1 << l) < n; l++) {
            for (int i = 0; i + k < n; i++) {
                f[l + 1][i] = best(f[l][i], f[l][i + k]);
            }
        }
    }
    T query(int a, int b) {
        int l = a == b ? 0 : __lg(b - a);
        return best(f[l][a], f[l][b - (1 << l) + 1]);
    }
};
MINRMQ<long long> minrmq;
MAXRMQ<long long> maxrmq;
GCDRMQ<int> gcdrmq;

const int maxn = 1e6 + 5;
int n;
long long a[maxn];
long long b[maxn];
int l[maxn];
int r[maxn];

int getnext(int i, int u, int v) {
    int g = gcdrmq.query(u, v);
    int lo = v, hi = r[i];
    while (lo < hi) {
        int mi = lo + hi + 1 >> 1;
        if (gcdrmq.query(u, mi) == g) {
            lo = mi;
        }
        else {
            hi = mi - 1;
        }
    }
    return lo + hi >> 1;
}
int getprev(int i, int u, int v) {
    int g = gcdrmq.query(u, v);
    int lo = l[i], hi = u;
    while (lo < hi) {
        int mi = lo + hi >> 1;
        if (gcdrmq.query(mi, v) != g) {
            lo = mi + 1;
        }
        else {
            hi = mi;
        }
    }
    return lo + hi >> 1;
}

long long query1(int i, int u, int x, int y) {
    return gcdrmq.query(u, x) * (maxrmq.query(x, y) - b[u - 1] - a[i]);
}

long long query2(int i, int x, int y, int u) {
    return gcdrmq.query(y, u) * (b[u] - minrmq.query(x - 1, y - 1) - a[i]);
}

long long ff(int i, int u, int v) {
    return gcdrmq.query(u, v) * (b[v] - b[u - 1] - a[i]);
}

void solve() {
    cin >> n;
    FOR(i, 1, n + 1) cin >> a[i];
    partial_sum(a, a + n + 1, b);
    minrmq.init(n + 1);
    maxrmq.init(n + 1);
    gcdrmq.init(n + 1);
    FOR(i, 1, n + 1) minrmq.upd(i, b[i]);
    FOR(i, 1, n + 1) maxrmq.upd(i, b[i]);
    FOR(i, 1, n + 1) gcdrmq.upd(i, a[i]);
    minrmq.build();
    maxrmq.build();
    gcdrmq.build();
    FOR(i, 1, n + 1) l[i] = r[i] = i;
    FOR(i, 2, n + 1) {
        int ptr = i;
        while (ptr > 1 && a[i] >= a[ptr - 1]) ptr = l[ptr - 1];
        l[i] = ptr;
    }
    FORd(i, n, 1) {
        int ptr = i;
        while (ptr < n && a[i] > a[ptr + 1]) ptr = r[ptr + 1];
        r[i] = ptr;
    }
    long long res = -8 * LINF;
    FOR(i, 1, n + 1) {
        if (i - l[i] < r[i] - i) {
            FORd(j, i + 1, l[i]) {
                int ptr = i;
                while (ptr <= r[i]) {
                    int nptr = getnext(i, j, ptr);
                    chkmax(res, query1(i, j, ptr, nptr));
                    ptr = nptr + 1;
                }
            }
        }
        else {
            FOR(j, i, r[i] + 1) {
                int ptr = i;
                while (ptr >= l[i]) {
                    int nptr = getprev(i, ptr, j);
                    chkmax(res, query2(i, nptr, ptr, j));
                    ptr = nptr - 1;
                }
            }
        }
    }
    cout << res << "\n";
}

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0), cin.tie(0);
    if (argc > 1) {
        assert(freopen(argv[1], "r", stdin));
    }
    if (argc > 2) {
        assert(freopen(argv[2], "wb", stdout));
    }
    solve();
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}


Problem solution in C programming.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define INF 200000
typedef struct _node
{
    int gcd;
    int max;
    long long sum;
}node;
typedef struct _tree_node
{
    enum
    {
        red, black
    }colour;
    int data;
    int real;
    struct _tree_node *left, *right, *parent;
}tree_node;
int a[50000], b[50000], nonzero[50000], rp[30], rc[30], treei[200000], rs, s, N;
long long ans, p[1000], tree[200000];
node t[200000];
tree_node *map[50000];
void getp(long long N, long long *prim)
{
    long long i, j, index = 2, flag;
    if( N <= 1 )
    {
        prim[0] = 0;
        return;
    }
    if( N == 2 )
    {
        prim[0] = 2;
        prim[1] = 0;
        return;
    }
    prim[0] = 2;
    prim[1] = 3;
    for( i = 5 ; i <= N ; i += 2 )
    {
        for( j = 1, flag = 1 ; prim[j] <= sqrt(i) ; j++ )
        {
            if( i % prim[j] == 0 )
            {
                flag = 0;
                break;
            }
        }
        if( flag == 1 )
        {
            prim[index] = i;
            index++;
        }
    }
    prim[index] = 0;
    return;
}
long long CC(long long n, long long d)
{
    if( n == 0 )
    {
        return d;
    }
    if( d == 0 )
    {
        return n;
    }
    while(1)
    {
        n = n % d;
        if( n == 0 )
        {
            return d;
        }
        d = d % n;
        if( d == 0 )
        {
            return n;
        }
    }
}
int max(int x, int y)
{
    return ( x > y ) ? x : y;
}
int min(int x, int y)
{
    return ( x < y ) ? x : y;
}
int abss(int x)
{
    return ( x < 0 ) ? -x : x;
}
int search(tree_node *root, int data)
{
    if(!root)
    {
        return INF;
    }
    if( root -> data == data )
    {
        return root -> real;
    }
    if( data < root -> data )
    {
        return search(root -> left, data);
    }
    return search(root -> right, data);
}
void left_rotate(tree_node **root, tree_node *x)
{
    tree_node *y;
    y = x -> right;
    if(!y)
    {
        return;
    }
    x -> right = y -> left;
    if(y -> left)
    {
        y -> left -> parent = x;
    }
    y -> parent = x -> parent;
    if( x -> parent == NULL )
    {
        *root = y;
    }
    else if( x == x -> parent -> left )
    {
        x -> parent -> left = y;
    }
    else
    {
        x -> parent -> right = y;
    }
    y -> left = x;
    x -> parent = y;
    return;
}
void right_rotate(tree_node **root, tree_node *y)
{
    tree_node *x;
    x = y -> left;
    if(!x)
    {
        return;
    }
    y -> left = x -> right;
    if(x -> right)
    {
        x -> right -> parent = y;
    }
    x -> parent = y -> parent;
    if( y -> parent == NULL )
    {
        *root = x;
    }
    else if( y == y -> parent -> right )
    {
        y -> parent -> right = x;
    }
    else
    {
        y -> parent -> left = x;
    }
    x -> right = y;
    y -> parent = x;
    return;
}
void reconstruct(tree_node **root, tree_node *x)
{
    tree_node *y, *z;
    y = x -> parent;
    z = x -> parent -> parent;
    x -> colour = black;
    z -> colour = red;
    x -> parent = z -> parent;
    if( z -> parent == NULL )
    {
        *root = x;
    }
    else if( z == z -> parent -> left )
    {
        z -> parent -> left = x;
    }
    else
    {
        z -> parent -> right = x;
    }
    if( z -> left == y )
    {
        x -> left = y;
        x -> right = z;
    }
    else
    {
        x -> left = z;
        x -> right = y;
    }
    y -> parent = z -> parent = x;
    y -> left = y -> right = z -> left = z -> right = NULL;
    return;
}
int normal_insert(tree_node **root, tree_node *x)
{
    if( *root == NULL )
    {
        *root = x;
    }
    else if( (*root) -> data == x -> data )
    {
        return 0;
    }
    else
    {
        x -> parent = *root;
        if( (*root) -> data > x -> data )
        {
            return normal_insert(&((*root) -> left), x);
        }
        else
        {
            return normal_insert(&((*root) -> right), x);
        }
    }
    return 1;
}
void insert(tree_node **root, tree_node *x)
{
    if(!normal_insert(root, x))
    {
        return;
    }
    tree_node *y;
    x -> colour = red;
    while( x != *root && x -> parent -> colour == red )
    {
        if( x -> parent == x -> parent -> parent -> left )
        {
            y = x -> parent -> parent -> right;
            if(!y)
                if( x == x -> parent -> left )
                {
                    x -> parent -> colour = black;
                    x -> parent -> parent -> colour = red;
                    right_rotate(root, x -> parent -> parent);
                }
                else
                {
                    y = x -> parent;
                    reconstruct(root, x);
                    x = y;
                }
            else if( y -> colour == red )
            {
                x -> parent -> colour = black;
                y -> colour = black;
                x -> parent -> parent -> colour = red;
                x = x -> parent -> parent;
            }
            else
            {
                if( x == x -> parent -> right )
                {
                    x = x -> parent;
                    left_rotate(root, x);
                }
                x -> parent -> colour = black;
                x -> parent -> parent -> colour = red;
                right_rotate(root, x -> parent -> parent);
            }
        }
        else
        {
            y = x -> parent -> parent -> left;
            if(!y)
                if( x == x -> parent -> right )
                {
                    x -> parent -> colour = black;
                    x -> parent -> parent -> colour = red;
                    left_rotate(root, x -> parent -> parent);
                }
                else
                {
                    y = x -> parent;
                    reconstruct(root, x);
                    x = y;
                }
            else if( y -> colour == red )
            {
                x -> parent -> colour = black;
                y -> colour = black;
                x -> parent -> parent -> colour = red;
                x = x -> parent -> parent;
            }
            else
            {
                if( x == x -> parent -> left )
                {
                    x = x -> parent;
                    right_rotate(root, x);
                }
                x -> parent -> colour = black;
                x -> parent -> parent -> colour = red;
                left_rotate(root, x -> parent -> parent);
            }
        }
    }
    (*root) -> colour = black;
    return;
}
void merge(int *a, int *left, int *right, int left_size, int right_size, int *new_size)
{
    int i = 0, j = 0, index = 0;
    while( i < left_size || j < right_size )
    {
        if( i == left_size )
        {
            a[index++] = right[j];
            j++;
        }
        else if( j == right_size )
        {
            a[index++] = left[i];
            i++;
        }
        else if( left[i] <= right[j] )
        {
            a[index++] = left[i];
            i++;
        }
        else
        {
            a[index++] = right[j];
            j++;
        }
        if( index > 1 && a[index-2] == a[index-1] )
        {
            index--;
        }
    }
    (*new_size) = index;
    return;
}
void init(int n)
{
    N = 1;
    while( N < n )
    {
        N *= 2;
    }
    for( int i = 1 ; i < N + n ; i++ )
    {
        tree[i] = -1000000000000000000LL;
    }
}
int range_sum(int i, int j)
{
    int ansi;
    long long ans = -1000000000000000000LL;
    for( i += N, j += N ; i <= j ; i = ( i + 1 ) / 2, j = ( j - 1 ) / 2 )
    {
        if( i % 2 == 1 )
            if( tree[i] > ans )
            {
                ans = tree[i];
                ansi = treei[i];
            }
        if( j % 2 == 0 )
            if( tree[j] > ans )
            {
                ans = tree[j];
                ansi = treei[j];
            }
    }
    return ansi;
}
void update(int i, long long val)
{
    int j;
    for( j = i + N ; j ; j /= 2 )
        if( val > tree[j] )
        {
            tree[j] = val;
            treei[j] = i;
        }
}
void sort_a(int *a, int size, int *new_size)
{
    if( size < 2 )
    {
        (*new_size) = size;
        return;
    }
    int m = ( size + 1 ) / 2, i;
    int *left, *right;
    left = (int*)malloc(m * sizeof(int));
    right = (int*)malloc(( size - m ) * sizeof(int));
    for( i = 0 ; i < m ; i++ )
    {
        left[i] = a[i];
    }
    for( i = 0 ; i < size - m ; i++ )
    {
        right[i] = a[i+m];
    }
    int new_l_size = 0, new_r_size = 0;
    sort_a(left, m, &new_l_size);
    sort_a(right, size-m, &new_r_size);
    merge(a, left, right, new_l_size, new_r_size, new_size);
    free(left);
    free(right);
    return;
}
long long query(int v, int tl, int tr, int l, int r, int *gcd, int *ma, long long *sum)
{
    int tm, g1, g2, m1, m2;
    long long s1, s2;
    if( tl > r || tr < l )
    {
        *gcd = 0;
        *ma = 0;
        *sum = 0;
        return 0;
    }
    if( tl >= l && tr <= r )
    {
        *gcd = t[v].gcd;
        *ma = t[v].max;
        *sum = t[v].sum;
        return (*gcd) * ( (*sum) - (*ma) );
    }
    tm = ( tl + tr ) / 2;
    query(2*v, tl, tm, l, r, &g1, &m1, &s1);
    query(2*v+1, tm+1, tr, l, r, &g2, &m2, &s2);
    *gcd = CC(g1, g2);
    *ma = max(m1, m2);
    *sum = s1 + s2;
    return (*gcd) * ( (*sum) - (*ma) );
}
void solve(int start, int bs, int ns)
{
    int gcd, ma, i, j;
    long long t, sum;
    for( i = 0 ; i < bs ; i++ )
    {
        if( b[i] == ns )
        {
            continue;
        }
        if( i == bs - 1 )
        {
            j = range_sum(b[i], ns-1);
        }
        else
        {
            j = range_sum(b[i], b[i+1]-1);
        }
        t = query(1, 0, ns-1, start, j, &gcd, &ma, &sum);
        if( t > ans )
        {
            ans = t;
        }
    }
    return;
}
void copy_tree(tree_node **d, tree_node *r)
{
    tree_node *p;
    if(!r)
    {
        return;
    }
    copy_tree(d, r->left);
    p = (tree_node*)malloc(sizeof(tree_node));
    p -> data = r -> data;
    p -> real = r -> real;
    p -> left = p -> right = p -> parent = NULL;
    insert(d, p);
    b[s++] = r -> real + 1;
    copy_tree(d, r -> right);
    return;
}
void build(int v, int tl, int tr)
{
    int tm;
    if( tl == tr )
    {
        t[v].gcd = abss(a[tl]);
        t[v].max = t[v].sum = a[tl];
    }
    else
    {
        tm = ( tl + tr ) / 2;
        build(2*v, tl, tm);
        build(2*v+1, tm+1, tr);
        t[v].gcd = CC(t[2*v].gcd, t[2*v+1].gcd);
        t[v].max = max(t[2*v].max, t[2*v+1].max);
        t[v].sum = t[2*v].sum + t[2*v+1].sum;
    }
    return;
}
int main()
{
    int n, x, ns, i, j, k, l;
    long long sum;
    tree_node *last_node, *p_node;
    getp(1000, p);
    scanf("%d", &n);
    for( i = 0 ; i < n ; i++ )
    {
        scanf("%d", a + i);
    }
    build(1, 0, n-1);
    init(n);
    for( i = sum = 0 ; i < n ; i++ )
    {
        sum += a[i];
        update(i, sum);
    }
    for( i = n - 1 ; i >= 0 ; i-- )
    {
        if( i == n - 1 )
        {
            last_node = NULL;
        }
        else
        {
            last_node = map[i+1];
        }
        if(a[i])
        {
            nonzero[i] = i;
            for( j = rs = 0, x = abss(a[i]) ; p[j] && p[j] * p[j] <= x ; j++ )
            {
                if( x % p[j] == 0 )
                {
                    rp[rs] = p[j];
                    rc[rs] = 0;
                    while( x % p[j] == 0 )
                    {
                        rc[rs]++;
                        x /= p[j];
                    }
                    rs++;
                }
            }
            if( x != 1 )
            {
                rp[rs] = x;
                rc[rs] = 1;
                rs++;
            }
            for( j = s = 0 ; j < rs ; j++ )
            {
                for( k = 0, x = rp[j] ; k < rc[j] ; k++, x *= rp[j] )
                {
                    p_node = (tree_node*)malloc(sizeof(tree_node));
                    p_node -> data = x;
                    p_node -> left = p_node -> right = p_node -> parent = NULL;
                    l = search(last_node, x);
                    if( l != INF )
                    {
                        p_node -> real = l;
                        b[s++] = l + 1;
                    }
                    else
                    {
                        p_node -> real = i;
                    }
                    insert(&map[i], p_node);
                }
            }
            b[s++] = i;
            sort_a(b, s, &ns);
            solve(i, ns, n);
        }
        else
        {
            nonzero[i] = INF;
            s = 0;
            copy_tree(&map[i], last_node);
            if( i != n - 1 && nonzero[i+1] != INF )
            {
                b[s++] = nonzero[i+1];
            }
            sort_a(b, s, &ns);
            solve(i, ns, n);
        }
        if( i != n - 1 )
        {
            nonzero[i] = min(nonzero[i], nonzero[i+1]);
        }
    }
    printf("%lld", ans);
    return 0;
}


Post a Comment

0 Comments