2013 ACMICPC Hangzhou Rabbit Kingdom

Rabbit Kingdom
제목 설명
N 개 수의 서열, M 개 에 게 물 어보 고 각각 두 개의 수 L, R 을 물 어보 세 요.-- [L, R] 중 몇 개 수 와 구간 에 있 는 모든 수 (자기 만 빼 고 호 질)
해법
우선 O (N * sqrt (N) 가 각 수의 상호 질 을 미리 처리 하면 좌우 로 어느 곳 까지 연장 할 수 있 는 지, l [i], r [i] 로 기억 해 야 합 니 다.
이제 두 가지 해법 이 있 습 니 다.
Solution Of cxlove 
그녀 는 애 장, 야옹 ~  http://blog.csdn.net/ACM_cxlove?viewmode=contents
애 장의 해법 은 정 해 야 한다. 하나의 BIT 로 어떤 수 를 유지 할 수 있 는 지.
모든 l [i] 위 치 를 사 이 드 시트 로 i 를 삽입 하여 뒤에 사용 할 수 있 도록 합 니 다.
먼저 질문 을 l 로 오프라인 한 다음 에 l [i] < 1 (즉 왼쪽 에서 끝까지 버 틸 수 있 음) 의 숫자 를 i 의 위치 + 1, 만약 r [i] < = n 그러면 r [i] 의 위치 - 1.그럼 접두사 와 이 숫자 가 덮어 쓸 수 있 는 위치 입 니 다.
구간 왼쪽 지침 을 고려 하여 변 화 를 물 었 을 때 구간 왼쪽 지침 left 를 오른쪽으로 이동 하 는 동시에 현재 의 숫자 를 회복 합 니 다. 즉, left 위치 - 1, r [left] < = n 이 라면 r [left] 위치 + 1.
이때 우 리 는 그 사 이 드 시 계 를 사용 해 야 한다. l [i] left 의 숫자 에 대해 서 는 left 이후 에 모두 가능 하 다. 그래서 우 리 는 모든 left 위치의 사 이 드 시 계 를 옮 겨 다 니 며 pos [left] [j] 로 설정 하 는 것 이 그의 id 이다.그러면 pos [left] [j]
 이 자 리 는 가능 합 니 다. 우리 + 1, 동시에 그의 오른쪽 위 치 는 - 1 (r [pos [left] [j]) 입 니 다.
이렇게 해서 우 리 는 문의 위치 q [i]. l 을 쓸 때 l, r 사이 에 몇 개의 숫자 가 있 는 지 조회 하면 된다. 그러면 바로... sum (q[i].r) - sum (q[i].l - 1); 。 이 문 제 는 해결 되 었 다.
code

typedef long long LL;
const int N = 200005;
template<class T> inline T& RD(T &x){
    //cin >> x;
    //scanf("%d", &x);
    char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); '0' <= c && c <= '9'; c = getchar()) x = x * 10 + c - '0';
    //char c; c = getchar(); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';
    return x;
}
struct Query {
    int l , r , id;
    void input (int i) {
        id = i;
        RD(l); RD(r);
    }
    bool operator < (const Query &q) const {
        return l < q.l;
    }
}q[N];
int n , m , a[N] , s[N];
int flag[N] , prime[N] , cnt , minfac[N];
int fac[N][20] , p[N] , l[N] , r[N];
vector <int> pos[N];
void Init () {
    for (int i = 2 ; i < N ; i ++) {
        if (!flag[i]) {
            prime[cnt ++] = i;
            minfac[i] = i;
        }
        for (int j = 0 ; j < cnt && prime[j] * i < N ; j ++) {
            flag[i * prime[j]] = 1;
            minfac[i * prime[j]] = prime[j];
            if (i % prime[j] == 0) break;
        }
    }
    // minfac[1] = 1;
    // fac[1][0] = 1;fac[1][1] = 1;
    for (int i = 2 ; i < N ; i ++) {
        fac[i][0] = 0;
        int m = i;
        while (m != 1) {
            fac[i][++ fac[i][0]] = minfac[m];
            m /= minfac[m];
        }
    }
}
void add (int idx , int v) {
    // cout << "update : " << idx << " " << v << endl;
    for (int i = idx ; i <= n ; i += lowbit (i))
        s[i] += v;
}
int sum (int idx) {
    int ret = 0;
    for (int i = idx ; i > 0 ; i -= lowbit (i))
        ret += s[i];
    return ret;
}
int ans[N];
int main () {
    #ifndef ONLINE_JUDGE
        freopen ("input.txt" , "r" , stdin);
        // freopen ("output.txt" , "w" , stdout);
    #endif
    Init ();
    while (RD(n) , RD(m) , n + m) {
        for (int i = 1 ; i <= n ; i ++)
            RD(a[i]);
        for (int i = 0 ; i < N ; i ++)
            pos[i].clear ();
        memset (p , 0 , sizeof(p));
        for (int i = 1 ; i <= n ; i ++) {
            int idx = 0;
            for (int j = 1 ; j <= fac[a[i]][0] ; j ++)
                idx = max (idx , p[fac[a[i]][j]]);
            for (int j = 1 ; j <= fac[a[i]][0] ; j ++)
                p[fac[a[i]][j]] = i;
            l[i] = idx;
            pos[idx].push_back (i);
        }
        memset (p , 0x11 , sizeof(p));
        for (int i = n ; i > 0 ; i --) {
            int idx = n + 1;
            for (int j = 1 ; j <= fac[a[i]][0] ; j ++)
                idx = min (idx , p[fac[a[i]][j]]);
            for (int j = 1 ; j <= fac[a[i]][0] ; j ++)
                p[fac[a[i]][j]] = i;
            r[i] = idx;
        }
        for (int i = 0 ; i < m ; i ++)
            q[i].input (i);
        sort (q , q + m);
        memset (s , 0 , sizeof(s));
        for (int i = 1 ; i <= n ; i ++) {
            if (l[i] < 1) {
                add (i , 1);
                if (r[i] <= n)
                    add (r[i] , -1);
            }
        }
        int left = 1;
        for (int i = 0 ; i < m ; i ++) {
            while (left < q[i].l) {
                add (left , -1);
                if (r[left] <= n) add (r[left] , 1);
                for (int j = 0 ; j < pos[left].size() ; j ++) {
                    add (pos[left][j] , 1);
                    if (r[pos[left][j]] <= n) add (r[pos[left][j]] , -1);
                }
                left ++;
            }
            ans[q[i].id] = sum (q[i].r) - sum (q[i].l - 1);
            // cout << q[i].id << " " << ans[q[i].id] << " " << left << endl;
        }
        for (int i = 0 ; i < m ; i ++)
            printf ("%d
" , ans[i]);
    }
    return 0;
}

Solution Of Dshawn
나의 방법 은 비교적 번 거 로 우 니 r 에 따라 순 서 를 매 길 것 이다.
두 개의 BIT 로 가능 한 왼쪽 구간 의 위치 수 를 유지 합 니 다. (즉, 오른쪽 구간 에 반드시 만족 하 라 고 요구 할 수 있 습 니 다!!)
우선 왼쪽 포인터 first 가 있 습 니 다. 왼쪽 포인터 < = query [i]. r 일 때 계속 오른쪽으로 미 끄 러 집 니 다. 이와 동시에:
1. 그러면 first 위치의 이 숫자 에 대해 L [first] 는 성공 적 인 구간 입 니 다. 그러면 L [first] + 1 이 필요 합 니 다.
2. 나 는 사 이 드 시계 로 R [first] 의 위치 에 그의 왼쪽 포인터 위치 와 그의 위 치 를 기록한다. addR(R[first] , L[first] , first);
3. 오른쪽 구간 이 first 위치 에 있 는 구간 에 대해 멀리 갔 을 것 입 니 다. 그래서 우 리 는 사 이 드 시트 를 옮 겨 다 니 며 모든 R [X] = first 구간 을 찾 아 지 웠 습 니 다. 그러면 해당 하 는 L [X] - 1 을 지 웠 고 우리 기록 은 X 를 지 웠 습 니 다. 또한 BIT 로 X 의 위치 + 1 을 지 웠 습 니 다. 그러면 이 단 계 를 통 해 우 리 는 모든 오른쪽 구간 < = query [i]. r 의 것 을 지 웠 습 니 다.
질문 에 대한 답 은 query [i]. r - query [i]. l + 1 (총 원소 개수) - 오른쪽 구간 이 맞지 않 는, 우리 가 삭제 한 개수 - 왼쪽 구간 이 맞지 않 는 개수 입 니 다.좌우 구간 이 모두 부합 되 지 않 는 것 은 이미 오른쪽 구간 에 부합 되 지 않 는 개수 에 포함 되 어 있 으 며, 우 리 는 왼쪽 구간 에 부합 되 지 않 는 개수 에 기록 되 어 있 지 않 음 을 주의해 야 한다.
그럼 이 간단 한 용 척 문 제 를 통 해 해결 되 겠 습 니 다.
code

int n , m;
const int N = 4e5 + 9;
using namespace Math;
struct Query{
    int l , r , id;
    bool operator < (const Query & A) const{
        return r < A.r;
    }
}query[N];
int W[N];
int L[N] , R[N];
int last[N];
int tree[N];
int deltree[N];
void delOne(int x){
    for ( ; x < N ; x += low_bit(x))
        deltree[x]++;
}
int querydel(int x){
    int ret = 0;
    for ( ; x ; x -= low_bit(x))
        ret += deltree[x];
    return ret;
}
int head[N];
struct Node{
    int next;
    int r;
    int id;
}node[N];
int tot;
void addR(int x , int r , int id){
    node[tot].next = head[x];
    node[tot].r = r;
    node[tot].id = id;
    head[x] = tot++;
}
void add(int x , int y){
    for ( ; x < N ; x += low_bit(x))
        tree[x] += y;
}
int getsum(int x){
    int ret = 0;
    for ( ; x ; x -= low_bit(x))
        ret += tree[x];
    return ret;
}
int ans[N] , stand[N];
void debug(){
    for (int i = 0 ; i < m ; ++i){
        int ans = 0;
        for (int j = query[i].l ; j <= query[i].r ; ++j){
            bool ok = true;
            for (int k = query[i].l ; k <= query[i].r ; ++k)
                ok &= j == k || __gcd(W[j] , W[k]) == 1;
            ans += ok;
        }
        stand[i] = ans;
    }
}
void solve(){
    n++;
    for (int i = 2 ; i <= n ; ++i) {
            RD(W[i]);
//            W[i] = rand() % (int)2e5 + 1;
//            printf("%d " , W[i]);
    }
//    puts("");
    for (int i = 0 ; i < m ; ++i){
//        scanf("%d%d" , &query[i].l , &query[i].r);
        RD(query[i].l , query[i].r);
//        query[i].l = rand() % (n - 1) + 1;
//        query[i].r = query[i].l + rand() % (n - query[i].l);
//        printf("Query %d %d
" , query[i].l , query[i].r);
        query[i].l++;query[i].r++;
        query[i].id = i;
    }
//    debug();
    sort(query , query + m);
    for (int i = 1 ; i < N ; ++i) last[i] = 1;
    for (int i = 2 ; i <= n ; ++i){
        getFactors(W[i]);
        L[i] = 1;
        for (int j = 0 ; j < facCnt ; ++j){
            checkMax(L[i] , last[factor[j][0]]);
            last[factor[j][0]] = i;
        }
    }
    for (int i = 1 ; i < N ; ++i) last[i] = n + 1;
    for (int i = n ; i >= 2 ; --i){
        getFactors(W[i]);
        R[i] = n + 1;
//        cout << "factor ";
        for (int j = 0 ; j < facCnt ; ++j){
//                cout << factor[j][0] << ' ';
            checkMin(R[i] ,  last[factor[j][0]]);
            last[factor[j][0]] = i;
        }
//        cout << endl;
    }
//    for (int i = 2 ; i <= n ; ++i) printf("[%d,%d]
" , L[i] , R[i]);
//    for (int i = 2 ; i <= n ; ++i)
//        for (int j = i + 1 ; j <= n ; ++j)
//            printf("%d %d %d
" , i , j , __gcd(W[i] , W[j]));
    RST(tree);
    RST(deltree);
    int first = 2;
    tot = 0;
    FLC(head , -1);
    for (int i = 0 ; i < m ; ++i){
        while(first <= query[i].r){
            add(L[first] , 1);
            addR(R[first] , L[first] , first);
            for (int j = head[first] ; j != -1 ; j = node[j].next){
                add(node[j].r , -1);
                delOne(node[j].id);
            }
            first++;
        }
        ans[query[i].id] = query[i].r - query[i].l + 1 - (getsum(query[i].r) - getsum(query[i].l - 1) + querydel(query[i].r) - querydel(query[i].l - 1));
    }
    for (int i = 0 ; i < m ; ++i) {
            printf("%d
" , ans[i]);
//            if (ans[i] != stand[i]) {
//                    cout << "^^^" << endl;
//                    system("pause");
//            }
    }
}
int main(){
//    srand(time(0));
    getPrime();
    while(RD(n , m) , (n || m)) solve();
}