一、题目
二、题目链接
http://codeforces.com/contest/920/problem/F
三、题意
给定$N$个范围在$[1, 1e6)$的数字和$M$个操作。操作有两种类型:
$1$ $l$ $r$:更新区间$[l$, $r]$的数字a为d[a]。其中d[i]表示数字i的因子的个数。如:d[1] = 1, d[2] = 2, d[3] = 2, d[4] = 3。
$2$ $l$ $r$:查询区间$[l, r]$的数字和并输出。
四、思路
典型的数据结构题。很明显这是线段树的菜。
对于线段树的每个节点,维护所“管辖”区间的和值和最大值。
更新时,如果当前区间的最大值$maxv<=2$,那么,不需要往下更新下去了。因为$d[1] = 1$, $d[2] = 2$。否则,继续更新下去。这样并不会超时,因为对于一个范围在$[1, 1e6)$的数字而言,反复做$i = d[i]$这样的操作,次数并不会太多。
另外,更新完子区间后,要做上推合并操作。这是线段树很常见的操作。
五、源代码
#pragma GCC optimize(2) #pragma comment(linker, "/STACK:102400000, 102400000") #include<bits/stdc++.h> using namespace std; typedef long long LL; ; template <class T> inline void read(T &x) { int t; bool flag = false; ')) ; '; + t - '; if(flag) x = -x; } typedef struct { LL maxv, sum; } Node; Node data[MAXN * ]; << ], n, q; void init() { ; ; i <= N; ++i) { for(int j = i; j <= N; j += i) d[j]++; } memset(data, , sizeof(data)); } void pushup(int root){ data[root].sum = data[root << ].sum + data[root << | ].sum; data[root].maxv = max(data[root << ].maxv, data[root << | ].maxv); } , , int r = n) { if(l > x || r < x)return; if(l == r && l == x) { data[root].sum = data[root].maxv = LL(val); return; } ; , l, mid); | , mid + , r); pushup(root); } , , int r = n) { if(l > r || l > ur || r < ul)return; if(ul <= l && ur >= r && data[root].maxv <= 2LL)return; if(l == r) { data[root].sum = data[root].maxv = LL(d[data[root].sum]); return; } ; , l, mid); | , mid + , r); pushup(root); } LL query(, , int r = n) { if(l > r || l > qr || r < ql)return 0LL; if(ql <= l && qr >= r)return data[root].sum; ; , l, mid) + query(ql, qr, root << | , mid + , r); } int main() { #ifndef ONLINE_JUDGE freopen("Finput.txt", "r", stdin); #endif // ONLINE_JUDGE init(); int tmp, type, l, r; scanf("%d%d", &n, &q); ; i <= n; ++i){ read(tmp); build(i, tmp); } while(q--){ read(type), read(l), read(r); )update(l, r); else printf("%lld\n", query(l, r)); } ; }