hdu 5381 (2015 다 교 8) -- The sum of gcd (선분 수)

제목 링크: 클릭 하여 링크 열기
제목 대의: f (l, r) = ∑ ri = l ∑ rj = igcd (ai, ai + 1.... aj), 최초의 n 개 값 을 제시 하고 q 회 질문, 매번 출력 f (l, r) 의 값 을 묻는다. 
대부분 은 모 팀 의 알고리즘 을 말 하 는데 붓 기 를 생각 하지 못 했 습 니까?
우선 임의의 a [i] 에 대해 서 는 매번 gcd 가 최소 반 으로 줄 어 들 기 때문에 뒤쪽 gcd 는 log (a [i] 를 최대 로 낮 출 수 있 습 니 다. 모든 a [i] 에 있어 서 gcd 와 같은 각 구간 을 구 할 수 있 습 니 다.
선분 트 리 로 구간 의 gcd 를 유지 하고 [l, r] 의 gcd 값 x 를 조회 할 수 있 습 니 다. i 부터 왼쪽 경계 l 을 매 거 한 다음 에 2 분 으로 gcd 와 같은 구간 의 오른쪽 경계 r 를 찾 을 수 있 습 니 다. 이것 은 a [i] 에 있어 gcd 와 같은 구간 을 얻 을 수 있 습 니 다. 그리고 다음 구간 의 왼쪽 경 계 는 r + 1 이 되 고 gcd 값 도 gcd (x, a [r + 1]) 가 되 어 이 gcd 의 오른쪽 경 계 를 계속 찾 을 수 있 습 니 다.n 번 째 숫자 를 찾 을 때 까지.이렇게 하면 i 에서 시작 하 는 gcd 와 같은 각 구간 을 얻 을 수 있다.
요구 하 는 f (l, r) 의 경우 모든 gcd (l,, r) 를 종이 에 쓰 면 f (l, r) 는 삼각형 의 구간 과.질문 하 는 l 을 큰 것 에서 작은 것 으로 정렬 하고 새로운 선분 트 리 를 만 들 며 구간 수정, 구간 조회 작업 을 완성 합 니 다. 모든 질문 의 l 에 대해 l 이상 이 고 선분 트 리 에 추가 되 지 않 은 gcd 구간 에 선분 트 리 를 추가 한 다음 에 [l, r] 의 합, 즉 f (l, r) 의 값 을 조회 합 니 다.

#include 
#include 
#include 
#include 
#include 
using namespace std ;
#define LL __int64
#define maxn 10010
#define root 1,n,1
#define int_rt int l,int r,int rt
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
struct node{
    int id , l , r , x ;
}p , q[maxn] ;
vector vec[maxn] ;
int n , m , a[maxn] , k ;
LL ans[maxn] ;
int cl[maxn<<2] ;
int c[maxn] ;
int read() {
    int x = 0 ;
    char ch ;
    ch = getchar() ;
    while( ch < '0' || ch > '9' )
        ch = getchar() ;
    while( ch >= '0' && ch <= '9' ) {
        x = x*10 + ch - '0' ;
        ch = getchar() ;
    }
    return x ;
}
int gcd(int a,int b) {
    return b == 0 ? a : gcd(b,a%b) ;
}
int cmp(node a,node b) {
    return a.l > b.l ;
}
void push_up(int rt) {
    cl[rt] = gcd( cl[rt<<1] , cl[rt<<1|1] ) ;
}
void init(int_rt) {
    if( l == r ) {
        cl[rt] = read() ;
        a[l] = cl[rt] ;
        return ;
    }
    init(lson) ;
    init(rson) ;
    push_up(rt) ;
}
int query(int ll,int rr,int_rt) {
    if( ll <= l && rr >= r ) {
        return cl[rt] ;
    }
    int mid = (l+r)/2 , t1 = 0 , t2 = 0 ;
    if( ll <= mid )
        t1 = query(ll,rr,lson) ;
    if( rr > mid )
        t2 = query(ll,rr,rson) ;
    if( t1 && t2 )
        return gcd(t1,t2) ;
    if( t1 ) return t1 ;
    else return t2 ;
}
int search1(int l,int x) {
    int low = l , mid , high = n , temp ;
    while( low <= high ) {
        mid = (low+high)/2 ;
        if( query(l,mid,root) >= x ) {
            low = mid+1 ;
            temp = mid ;
        }
        else
            high = mid-1 ;
    }
    return temp ;
}
LL sum[maxn<<2] , lazy[maxn<<2] ;
void push(int_rt) {
    int mid = (l+r)/2 ;
    sum[rt] = sum[rt<<1] + sum[rt<<1|1] ;
    sum[rt] += lazy[rt<<1]*(mid-l+1) ;
    sum[rt] += lazy[rt<<1|1]*(r-mid) ;
}
void update(int ll,int rr,int x,int_rt) {
    if( ll > r || rr < l ) return ;
    if( ll <= l && rr >= r ) {
        lazy[rt] += x ;
        return ;
    }
    update(ll,rr,x,lson) ;
    update(ll,rr,x,rson) ;
    push(l,r,rt) ;
}
LL getsum(int ll,int rr,LL s,int_rt) {
    if( ll > r || rr < l ) return 0 ;
    if( ll <= l && rr >= r ) {
        return sum[rt] + (lazy[rt]+s)*(r-l+1) ;
    }
    return getsum(ll,rr,s+lazy[rt],lson) + getsum(ll,rr,s+lazy[rt],rson) ;
}
int main() {
    int t , i , j ;
    int l , r , x ;
    t = read() ;
    while( t-- ) {
        memset(c,0,sizeof(c)) ;
        memset(sum,0,sizeof(sum)) ;
        memset(lazy,0,sizeof(lazy)) ;
        n = read() ;
        init(root) ;
        vec[0].clear() ; vec[n+1].clear() ;
        for(i = 1 ; i <= n ; i++) {
            vec[i].clear() ;
            l = r = i ;
            x = a[i] ;
            p.id = i ; p.x = x ;
            p.l = l ; p.r = r ;
            vec[i].push_back(p) ;
            while( r < n ) {
                x = gcd(x,a[r+1]) ;
                l = r+1 ;
                r = search1(i,x) ;
                p.id = i ; p.x = x ;
                p.l = l ; p.r = r ;
                vec[i].push_back(p) ;
            }
        }
        m = read() ;
        for(i = 0 ; i < m ; i++) {
            q[i].l = read() ;
            q[i].r = read() ;
            q[i].id = i ;
        }
        sort(q,q+m,cmp) ;
        l = r = n+1 ;
        int num = 0 ;
        for(i = 0 ; i < m ; i++) {
            while( l > q[i].l ) {
                l-- ;
                for(j = 0 ; j < vec[l].size() ; j++)
                    update(vec[l][j].l,vec[l][j].r,vec[l][j].x,root) ;
            }
            ans[ q[i].id ] = getsum(q[i].l,q[i].r,(LL)0,root) ;
        }
        for(i = 0 ; i < m ; i++)
            printf("%I64d
", ans[i]) ;
    }
    return 0 ;
}

f(l,r)=∑ri=l∑rj=igcd(ai,ai+1....aj)