Traffic Jams in the Land
题目背景：
CodeForces - 498D
分析：这是一道比较有趣的线段树的题，考虑处理的方法，首先我们发现对于一个时间的处理，因为它的周期只有2~6，那么我们取2~6的最小公倍数60，显然，每过60，时间的状态就会进行重复，那么我们就考虑利用线段树，预处理出从某一点进入，然后完成某一段路程的时间，因为数据范围比较宽松，我们完全可以在每一个线段树的节点中，存储一个60的数组，来表示在t % 60 == i时进入当前这一段路程的时间Xi，从而很方便在复杂度之内处理完成。
Source：
#include #include #include #include #include #include #include using namespace std; inline void R(int &v) { char c = 0; bool p = true; v = 0; while(!isdigit(c)) { if(c == '-') p = false; c = getchar(); } while(isdigit(c)) { v = (v << 3) + (v << 1) + (c ^ '0'); c = getchar(); } if(!p) v = -v; } const int MAXN = 100000 + 10; struct node { int t[60]; } tree[MAXN << 2]; int a[MAXN]; void updata(int k) { for(int i = 0; i < 60; ++i) { /*预处理每一个时刻进入所需要的时间*/ int temp = tree[k << 1].t[i]; int next = (temp + i) % 60; tree[k].t[i] = tree[k << 1].t[i] + tree[k << 1 | 1].t[next]; } } void build(int k, int l, int r) { if(l == r) { for(int i = 0; i < 60; ++i) if(i % a[l]) tree[k].t[i] = 1; else tree[k].t[i] = 2; return ; } register int mid = l + r >> 1; build(k << 1, l, mid); build(k << 1 | 1, mid + 1, r); updata(k); } void modify(int k, int l, int r, int pos, int x) { if(l == r) { a[l] = x; for(int i = 0; i < 60; ++i) if(i % a[l]) tree[k].t[i] = 1; else tree[k].t[i] = 2; return ; } register int mid = l + r >> 1; if(pos <= mid) modify(k << 1, l, mid, pos, x); else modify(k << 1 | 1, mid + 1, r, pos, x); updata(k); } int query(int k, int l, int r, int ql, int qr, int t) { if(ql <= l && r <= qr) return t + tree[k].t[t % 60]; register int mid = l + r >> 1; /*从左到右一段一段依次询问即可*/ if(ql <= mid) t = query(k << 1, l, mid, ql, qr, t); if(qr > mid) t = query(k << 1 | 1, mid + 1, r, ql, qr, t); return t; } int main() { int n, m, l, r; char s[5]; R(n); for(int i = 1; i <= n; ++i) R(a[i]); build(1, 1, n), R(m); for(int i = 1; i <= m; ++i) { scanf("%s", s), R(l), R(r); if(s[0] == 'A') cout << query(1, 1, n, l, r - 1, 0) << '\n'; else modify(1, 1, n, l, r); } return 0; }