ZOJ-Monthly-August-2014-C.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cassert>
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
#define foreach(it , h) for (typeof((h).begin()) it = (h).begin() ; it != (h).end() ; ++ it)
const int N = 100005;
int n , m , Q , a[N];
int LOG[N];
int GCD[17][N] , id[2000];
void init() {
    for (int i = 0 ; 1 << i < N ; ++ i)
        LOG[1 << i] = i;
    for (int i = 2 ; i < N ; ++ i)
        if (!LOG[i])
            LOG[i] = LOG[i - 1];
}

inline int cal(int l , int r) {
    int j = LOG[r - l + 1];
    return __gcd(GCD[j][l] , GCD[j][r - (1 << j) + 1]);
}
LL ans[N];
struct opt {
    int type;
    int x , l , r , p;
    bool operator < (const opt& R) const {
        if (x == R.x)
            return type < R.type;
        return x < R.x;
    }
};
struct CHU_2_BIT
{
    int n;
    LL B[N] , C[N];
    void init(int size) {
        n = size;
        memset(B , 0 , sizeof(B));
        memset(C , 0 , sizeof(C));
    }
    CHU_2_BIT() {}
    CHU_2_BIT(int size) {
        init(size);
    }
    void _add(LL* c , int x , LL w) {
        for ( ; x <= n ; x += x & -x)
            c[x] += w;
    }
    LL _sum(LL* c , int x) {
        LL res = 0;
        for ( ; x > 0 ; x -= x & -x)
            res += c[x];
        return res;
    }
    void add(int l , int r , LL w) {
        _add(B , l , w) , _add(B , r + 1 , -w);
        _add(C , l , w * l) , _add(C , r + 1 , -w * (r + 1));
    }
    LL sum(int l , int r) {
        LL res = 0;
        res += (r + 1) * _sum(B , r) - l * _sum(B , l - 1);
        res -= _sum(C , r) - _sum(C , l - 1);
        return res;
    }
}T[50];
vector<opt> Vec;
void work() {
    int i , j , x , y ;
    for (i = 1 ; i <= n ; ++ i)
        scanf("%d",&a[i]) , GCD[0][i] = a[i];
    for (j = 1 ; 1 << j <= n ; ++ j)
        for (i = 1 ; i + (1 << j) - 1 <= n ; ++ i)
            GCD[j][i] = __gcd(GCD[j - 1][i + (1 << j - 1)] , GCD[j - 1][i]);
    memset(id , -1 , sizeof(id));
    for (i = 0 ; i < m ; ++ i) {
        scanf("%d",&x) , id[x] = i;
        assert(x < 2000);
    }
    Vec.clear();
    for (i = 0 ; i < Q ; ++ i) {
        scanf("%d%d%d",&x,&y,&j);
        assert(id[j] != -1);
        j = id[j] , ++ x;
        Vec.push_back((opt){i << 1 , x - 1 , x , y , j});
        Vec.push_back((opt){i << 1 | 1 , y , x , y , j});
    }
    for (i = 1 ; i <= n ; ++ i) {
        j = i;
        while (j <= n) {
            int l = j , r = n , mid;
            int tmp = cal(i , j);
            while (l < r) {
                mid = l + r + 1 >> 1;
                if (cal(i , mid) == tmp)
                    l = mid;
                else
                    r = mid - 1;
            }
            // i , l;
            if (tmp < 2000 && ~id[tmp]) {
                //printf("%d %d %d : %d\n" , i , j , l , tmp);
                Vec.push_back((opt){-1 , i , j , l , id[tmp]});
            }
            j = l + 1;
        }
    }
    sort(Vec.begin() , Vec.end());
    memset(ans , 0 , sizeof(ans));
    for (i = 0 ; i < m ; ++ i)
        T[i].init(n);
    for (vector<opt>::iterator it = Vec.begin() ; it != Vec.end() ; ++ it) {
        if (it -> type < 0) {
            T[it -> p].add(it -> l , it -> r , 1);
        } else {
            if (it -> type & 1)
                ans[it -> type >> 1] += T[it -> p].sum(it -> l , it -> r);
            else
                ans[it -> type >> 1] -= T[it -> p].sum(it -> l , it -> r);
        }
    }
    for (i = 0 ; i < Q ; ++ i)
        printf("%lld\n" , ans[i]);
}

int main() {
    init();
    while (~scanf("%d%d%d",&n,&m,&Q))
        work();
    return 0;
}