Codeforces Round 284 Div.1 Problem D - Traffic Jams in the Land

Problem Statement:
498D - Traffic Jams in the Land

Solution:
This problem abuses segment tree so bad :)

The idea is to build 60 (which is gcd of 2,3,4,5,6) segment trees, each segment tree i answers the particular query: what is the time needed to pass through roads in [L..R] given that I start at time T = i mod 60. As such, we can serve all queries in \(O(N\lg{N})\) time. The hardest part is of course to implement the trees (or plant the forest).

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cassert>
using namespace std;

int segtree[400005][60];
int vis[400005][60];
int a[100005];
int N, Q;
int iter;
int build(int p, int t, int L, int R){
    if(vis[p][t%60]) return segtree[p][t%60];
    vis[p][t%60] = 1;
    if(L==R){
        segtree[p][t%60] = 1;
        if(t%a[L] == 0) segtree[p][t%60]++;
        return segtree[p][t%60];
    }
    int M = (L+R)/2;
    int left = build(2*p,t,L,M);
    int right = build(2*p+1,t+left,M+1,R);
    segtree[p][t%60] = left+right;
    build(2*p+1,t,M+1,R);
    return left+right;
}

int rmq(int p,int t,int L,int R,int S,int T){
    if(T<L||R<S)return t;
    if(S<=L&&R<=T){
        return t + segtree[p][t%60];
    }
    int M=(L+R)/2;
    int left = rmq(2*p,t,L,M,S,T);
    int right = rmq(2*p+1,left,M+1,R,S,T);
    return right;
}

void update(int p, int L, int R, int S){
    if(R<S||S<L)return;
    if(R==L && L==S){
        for(int i=0;i<60;++i){
            segtree[p][i] = (i%a[L]==0 ? 2: 1);
        }
        return;
    }
    int M=(L+R)/2;
    update(2*p,L,M,S);
    update(2*p+1,M+1,R,S);
    for(int i=0;i<60;++i){
        int left = segtree[2*p][i];
        segtree[p][i] = segtree[2*p][i] + segtree[2*p+1][(i+left)%60];
    }
}

int main(){
    int x,y;
    char c;
    scanf("%d", &N);
    for(int i=0;i<N;++i){
        scanf("%d", &a[i]);
    }
    for(int i=0;i<60;++i){
        build(1,i,0,N-1);
    }
    scanf("%d",&Q);
    iter = 1;
    for(int qq=0;qq<Q;++qq){
        scanf(" %c%d%d", &c,&x,&y);
        if(c=='C'){
            a[x-1]=y;
            update(1,0,N-1,x-1);
        } else {
            printf("%d\n",rmq(1,0,0,N-1,x-1,y-2));
        }
    }
    return 0;
}