Day1
[Sdoi2017]数字表格
推式子的莫比乌斯反演题。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <cmath> 5 6 7 #define maxn 1000010 8 #define R register 9 const int mod = 1e9 + 7; 10 int miu[maxn], fib[maxn], g[maxn], pr[maxn / 20], prcnt, fp[maxn][3]; 11 bool vis[maxn]; 12 inline int qpow(R int base, R int power) 13 { 14 R int ret = 1; 15 for (; power; power >>= 1, base = 1ll * base * base % mod) 16 power & 1 ? ret = 1ll * ret * base % mod : 0; 17 return ret; 18 } 19 int main() 20 { 21 miu[1] = 1; fib[0] = 0; fib[1] = g[0] = g[1] = 1; 22 for (R int i = 2; i < maxn; ++i) 23 { 24 fib[i] = (fib[i - 1] + fib[i - 2]) % mod; g[i] = 1; 25 if (!vis[i]) pr[++prcnt] = i, miu[i] = -1; 26 for (R int j = 1; j <= prcnt && i * pr[j] < maxn; ++j) 27 { 28 vis[i * pr[j]] = 1; 29 miu[i * pr[j]] = -miu[i]; 30 if (i % pr[j] == 0) 31 { 32 miu[i * pr[j]] = 0; 33 break; 34 } 35 } 36 } 37 for (R int i = 1; i < maxn; ++i) 38 fp[i][0] = qpow(fib[i], mod - 2), fp[i][1] = 1, fp[i][2] = fib[i]; 39 for (R int i = 1; i < maxn; ++i) 40 for (R int j = i; j < maxn; j += i) 41 g[j] = 1ll * g[j] * fp[i][miu[j / i] + 1] % mod; 42 for (R int i = 2; i < maxn; ++i) 43 g[i] = (1ll * g[i - 1] * g[i]) % mod; 44 R int T; scanf("%d", &T); 45 for (; T; --T) 46 { 47 R int n, m, ret = 1; scanf("%d%d", &n, &m); 48 for (R int i = 1, j; i <= n && i <= m; i = j + 1) 49 { 50 j = std::min(n / (n / i), m / (m / i)); 51 ret = 1ll * ret * qpow(1ll * g[j] * qpow(g[i - 1], mod - 2) % mod, 1ll * (n / i) * (m / i) % (mod - 1)) % mod; 52 } 53 printf("%d ", ret); 54 } 55 return 0; 56 }
[Sdoi2017]树点涂色
LCT套线段树。
1 #include <cstdio> 2 #include <cstring> 3 4 #define R register 5 #define maxn 100010 6 #define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b)) 7 #define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0) 8 struct Edge { 9 Edge *next; 10 int to; 11 } *last[maxn], e[maxn << 1], *ecnt = e; 12 inline void link(R int a, R int b) 13 { 14 *++ecnt = (Edge) {last[a], b}; last[a] = ecnt; 15 *++ecnt = (Edge) {last[b], a}; last[b] = ecnt; 16 } 17 int son[maxn], size[maxn], fa[maxn], top[maxn], dfn[maxn], pos[maxn], timer, dep[maxn], rig[maxn], n; 18 bool vis[maxn]; 19 void dfs1(R int x) 20 { 21 vis[x] = 1; size[x] = 1; dep[x] = dep[fa[x]] + 1; 22 for (R Edge *iter = last[x]; iter; iter = iter -> next) 23 if (!vis[iter -> to]) 24 { 25 fa[iter -> to] = x; 26 dfs1(iter -> to); 27 size[x] += size[iter -> to]; 28 size[son[x]] < size[iter -> to] ? son[x] = iter -> to : 0; 29 } 30 } 31 void dfs2(R int x) 32 { 33 vis[x] = 0; top[x] = son[fa[x]] == x ? top[fa[x]] : x; dfn[x] = ++timer; pos[timer] = x; 34 for (R Edge *iter = last[x]; iter; iter = iter -> next) 35 if (vis[iter -> to]) dfs2(iter -> to); 36 rig[x] = timer; 37 } 38 inline int getlca(R int a, R int b) 39 { 40 while (top[a] != top[b]) 41 { 42 dep[top[a]] < dep[top[b]] ? b = fa[top[b]] : a = fa[top[a]]; 43 } 44 return dep[a] < dep[b] ? a : b; 45 } 46 int tr[maxn << 2], tag[maxn << 2], ql, qr, qv; 47 inline void update(R int o) {tr[o] = dmax(tr[o << 1], tr[o << 1 | 1]);} 48 inline void pushdown(R int o) 49 { 50 if (tag[o]) 51 { 52 tr[o << 1] += tag[o]; tag[o << 1] += tag[o]; 53 tr[o << 1 | 1] += tag[o]; tag[o << 1 | 1] += tag[o]; 54 tag[o] = 0; 55 } 56 } 57 void build(R int o, R int l, R int r) 58 { 59 if (l == r) { tr[o] = dep[pos[l]]; return ;} 60 R int mid = l + r >> 1; 61 build(o << 1, l, mid); build(o << 1 | 1, mid + 1, r); 62 update(o); 63 } 64 void modify(R int o, R int l, R int r) 65 { 66 if (ql <= l && r <= qr) 67 { 68 tag[o] += qv; tr[o] += qv; return ; 69 } 70 R int mid = l + r >> 1; 71 pushdown(o); 72 if (ql <= mid) modify(o << 1, l, mid); 73 if (mid < qr) modify(o << 1 | 1, mid + 1, r); 74 update(o); 75 } 76 int query(R int o, R int l, R int r) 77 { 78 if (ql <= l && r <= qr) return tr[o]; 79 R int mid = l + r >> 1, ret = 0, tmp; 80 pushdown(o); 81 if (ql <= mid) tmp = query(o << 1, l, mid), cmax(ret, tmp); 82 if (mid < qr) tmp = query(o << 1 | 1, mid + 1, r), cmax(ret, tmp); 83 update(o); 84 return ret; 85 } 86 struct Node *null; 87 struct Node { 88 Node *ch[2], *fa, *mx; 89 inline bool type() 90 { 91 return fa -> ch[1] == this; 92 } 93 inline bool check() 94 { 95 return fa -> ch[type()] == this; 96 } 97 inline void update() 98 { 99 mx = ch[0] != null ? ch[0] -> mx : this; 100 } 101 inline void rotate() 102 { 103 R Node *f = fa, *gf = f -> fa; R bool d = type(); 104 (f -> ch[d] = ch[!d]) != null ? ch[!d] -> fa = f, 1 : 0; 105 (fa = gf), f -> check() ? gf -> ch[f -> type()] = this : 0; 106 (ch[!d] = f) -> fa = this; 107 f -> update(); 108 } 109 inline void splay() 110 { 111 for (; check(); rotate()) 112 if (fa -> check()) 113 { 114 (type() != fa -> type() ? this : fa) -> rotate(); 115 } 116 update(); 117 } 118 inline void access() 119 { 120 R Node *i = this, *j = null; 121 for (; i != null; i = (j = i) -> fa) 122 { 123 i -> splay(); 124 // printf("i %d j %d ", i - null, j - null); 125 if (i -> ch[1] != null) 126 { 127 // printf("%d +1 ", i -> ch[1] -> mx - null); 128 ql = dfn[i -> ch[1] -> mx - null]; qr = rig[i -> ch[1] -> mx - null]; qv = 1; 129 modify(1, 1, n); 130 } 131 if (j != null) 132 { 133 // printf("%d -1 ", j - null); 134 ql = dfn[j -> mx - null]; qr = rig[j -> mx - null]; qv = -1; 135 modify(1, 1, n); 136 } 137 i -> ch[1] = j; 138 } 139 } 140 } mem[maxn]; 141 int main() 142 { 143 // freopen("in.in", "r", stdin); 144 // freopen("out.out", "w", stdout); 145 R int m; scanf("%d%d", &n, &m); null = mem; 146 for (R int i = 1; i < n; ++i) 147 { 148 R int a, b; scanf("%d%d", &a, &b); link(a, b); 149 } 150 dfs1(1); dfs2(1); build(1, 1, n); 151 for (R int i = 1; i <= n; ++i) mem[i] = (Node) {{mem, mem}, mem + fa[i], mem + i}; 152 for (; m; --m) 153 { 154 R int opt, x, y; scanf("%d%d", &opt, &x); 155 if (opt == 1) (mem + x) -> access(); 156 else if (opt == 2) 157 { 158 scanf("%d", &y); 159 R int lca = getlca(x, y), dx, dy, dlca; 160 ql = dfn[x]; qr = dfn[x]; 161 dx = query(1, 1, n); 162 ql = dfn[y]; qr = dfn[y]; 163 dy = query(1, 1, n); 164 ql = dfn[lca]; qr = dfn[lca]; 165 dlca = query(1, 1, n); 166 printf("%d ", dx + dy - dlca * 2 + 1); 167 } 168 else 169 { 170 ql = dfn[x]; qr = rig[x]; 171 printf("%d ", query(1, 1, n)); 172 } 173 } 174 return 0; 175 }
[Sdoi2017]序列计数
循环矩阵快速幂。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <algorithm> 4 #include <bitset> 5 #include <cstring> 6 7 #define R register 8 #define maxn 20000010 9 const int mod = 20170408; 10 int pr[maxn / 20], prcnt; 11 std::bitset<maxn> vis; 12 typedef int Vector[110]; 13 Vector num1, num2, base; 14 int p; 15 void mul(R Vector A, R Vector B) 16 { 17 R Vector C; memset(C, 0, p << 2); 18 for (R int i = 0; i < p; ++i) for (R int j = 0; j < p; ++j) 19 C[(i + j) % p] = (C[(i + j) % p] + 1ll * A[i] * B[j]) % mod; 20 memcpy(A, C, p << 2); 21 } 22 int main() 23 { 24 R int n, m; scanf("%d%d%d", &n, &m, &p); 25 num1[1] = 1; 26 for (R int i = 2; i <= m; ++i) 27 { 28 ++num1[i % p]; 29 if (!vis[i]) pr[++prcnt] = i, --num2[i % p]; 30 for (R int j = 1; j <= prcnt && i * pr[j] <= m; ++j) 31 { 32 vis[i * pr[j]] = 1; 33 if (i % pr[j] == 0) break; 34 } 35 } 36 for (R int i = 0; i < p; ++i) num2[i] += num1[i]; 37 memcpy(base, num1, p << 2); 38 memset(num1, 0, p << 2); num1[0] = 1; 39 for (R int power = n; power; power >>= 1, mul(base, base)) 40 power & 1 ? mul(num1, base), 1 : 0; 41 memcpy(base, num2, p << 2); 42 memset(num2, 0, p << 2); num2[0] = 1; 43 for (R int power = n; power; power >>= 1, mul(base, base)) 44 power & 1 ? mul(num2, base), 1 : 0; 45 printf("%d ", (num1[0] - num2[0] + mod) % mod); 46 return 0; 47 }
Day2
[Sdoi2017]新生舞会
分数规划->二分+费用流。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 5 #define maxn 210 6 #define R register 7 #define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0) 8 typedef double db; 9 struct Edge { 10 Edge *next, *rev; 11 int from, to, cap; 12 db cost; 13 } *last[maxn], *prev[maxn], e[maxn * maxn * 20], *ecnt = e; 14 inline void link(R int a, R int b, R int w, R db c) 15 { 16 *++ecnt = (Edge) {last[a], ecnt + 1, a, b, w, c}; last[a] = ecnt; 17 *++ecnt = (Edge) {last[b], ecnt - 1, b, a, 0, -c}; last[b] = ecnt; 18 } 19 const db inf = 1e9; 20 int a[maxn][maxn], b[maxn][maxn], n, q[maxn * 20], s, t; 21 db ans, dis[maxn]; 22 bool inq[maxn]; 23 inline bool spfa() 24 { 25 for (R int i = 1; i <= t; ++i) dis[i] = inf; 26 R int head = 0, tail = 1; q[1] = s; 27 while (head < tail) 28 { 29 R int now = q[++head]; inq[now] = 0; 30 for (R Edge *iter = last[now]; iter; iter = iter -> next) 31 if (iter -> cap && dis[iter -> to] > dis[now] + iter -> cost) 32 { 33 dis[iter -> to] = dis[now] + iter -> cost; 34 prev[iter -> to] = iter; 35 !inq[iter -> to] ? inq[q[++tail] = iter -> to] = 1 : 0; 36 } 37 } 38 return dis[t] != inf; 39 } 40 inline void mcmf() 41 { 42 R int x = 0x7fffffff; 43 for (R Edge *iter = prev[t]; iter; iter = prev[iter -> from]) cmin(x, iter -> cap); 44 for (R Edge *iter = prev[t]; iter; iter = prev[iter -> from]) 45 { 46 iter -> cap -= x; 47 iter -> rev -> cap += x; 48 ans += iter -> cost * x; 49 } 50 } 51 inline db val(R db k) 52 { 53 memset(last, 0, (t + 1) << 2); ecnt = e; ans = 0; 54 for (R int i = 1; i <= n; ++i) 55 { 56 link(s, i, 1, 0); link(i + n, t, 1, 0); 57 for (R int j = 1; j <= n; ++j) 58 link(i, j + n, 1, k * b[i][j] - a[i][j]); 59 } 60 while (spfa()) mcmf(); 61 return -ans; 62 } 63 int main() 64 { 65 scanf("%d", &n); 66 for (R int i = 1; i <= n; ++i) for (R int j = 1; j <= n; ++j) scanf("%d", &a[i][j]); 67 for (R int i = 1; i <= n; ++i) for (R int j = 1; j <= n; ++j) scanf("%d", &b[i][j]); 68 s = 0; t = n << 1 | 1; 69 R db left = 0, right = 1e4; 70 while (right - left > 1e-7) 71 { 72 R db mid = (left + right) * 0.5; 73 if (val(mid) > 0) left = mid; 74 else right = mid; 75 } 76 printf("%.6lf ", left); 77 return 0; 78 }
[Sdoi2017]硬币游戏
很神的题。一开始只会6方的高斯消元。后来看了题解，计f[i]为i获胜的概率。f[0]表示没人获胜的概率。若我们计S_i表示i获胜的字符串的集合，S_0表示没有人获胜的字符串的集合。显然，这些集合的大小都是正无穷的。但我们只需要知道它们之间的比率。
我们以样例为例。
3 3
THT
HTT
TTH
首先，我们可以确定的是在所有的S_0的后面加上`THT`肯定游戏就结束了。
但问题是赢的不一定是第一个人。
比如，若S_0里最后两位如果是`HT`，那么此时就会在加上第一个`T`时就结束游戏了。同理，最后一位如果是`T`的话，那么加上`TH`以后就结束游戏了。
那么我们可以考虑，在所有的S_0集合后加上`THT`这个后缀，得到的字符串集合可以表示为：{1获胜的集合，2获胜的集合+`HT`，3获胜的集合+`T`}。
（注意：这里的`HT`和`T`均为`THT`的某个后缀）
所以可以得到这样的式子：0.125 * f_0 = f_1 + f_2 * 0.25 + f_3 * 0.5。然后对于每个串都能得到一个这样的式子，再加上所有人获胜的概率和为1，我们就得到了一个n+1个未知数，有n+1个方程的方程组。用高斯消元解决即可。
如何得到上面的系数？我们发现是会有上面的那种情况只有可能是i的某个前缀和j的某个后缀相等。所以可以用KMP把两个串拼起来来找到每个前缀和后缀相等的长度。
1 #include <cstdio> 2 #include <cmath> 3 #include <algorithm> 4 5 #define R register 6 #define maxn 310 7 typedef double db; 8 char s[maxn][maxn], st[maxn << 1]; 9 db a[maxn][maxn], x[maxn], pw[maxn]; 10 int fa[maxn << 1], m; 11 inline db calc(R int a, R int b) 12 { 13 for (R int i = 1; i <= m; ++i) st[i] = s[a][i]; st[m + 1] = '0'; 14 for (R int i = 1; i <= m; ++i) st[i + m + 1] = s[b][i]; 15 fa[1] = 0; 16 R int p = 0; 17 // puts(st + 1); 18 for (R int i = 2; i <= m + m + 1; ++i) 19 { 20 while (p && st[p + 1] != st[i]) p = fa[p]; 21 st[p + 1] == st[i] ? ++p : 0; 22 fa[i] = p; 23 // printf("%d ", fa[i]); 24 } 25 R db ans = 0; 26 // printf("%d %d ", a, b); 27 while (p) 28 { 29 // printf("p = %d ", p); 30 ans += pw[m - p]; 31 p = fa[p]; 32 } 33 // printf("%.2lf ", ans); 34 return ans; 35 } 36 int main() 37 { 38 R int n; scanf("%d%d", &n, &m); 39 for (R int i = 1; i <= n; ++i) scanf("%s", s[i] + 1); 40 pw[0] = 1; for (R int i = 1; i <= m; ++i) pw[i] = pw[i - 1] * 0.5; 41 for (R int i = 1; i <= n; ++i) 42 { 43 a[i][0] = -pw[m]; 44 a[0][i] = 1; 45 for (R int j = 1; j <= n; ++j) 46 { 47 // if (i == j) continue; 48 a[i][j] += calc(i, j); 49 } 50 } 51 a[0][n + 1] = 1; 52 53 for (R int i = 0; i <= n; ++i) 54 { 55 if (fabs(a[i][i]) < 1e-9) 56 { 57 for (R int j = i + 1; j <= n; ++j) 58 if (fabs(a[j][i]) > fabs(a[i][i])) 59 { 60 for (R int k = i; k <= n + 1; ++k) std::swap(a[i][k], a[j][k]); 61 break; 62 } 63 } 64 for (R int j = i + 1; j <= n; ++j) 65 { 66 R db temp = a[j][i] / a[i][i]; 67 for (R int k = i; k <= n + 1; ++k) 68 a[j][k] -= a[i][k] * temp; 69 } 70 } 71 x[n] = a[n][n + 1] / a[n][n]; 72 // fprintf(stderr, "%.2lf %.2lf ", a[n][n], a[n][n + 1]); 73 for (R int i = n - 1; i; --i) 74 { 75 R db tmp = a[i][n + 1]; 76 for (R int j = i + 1; j <= n; ++j) 77 tmp -= a[i][j] * x[j]; 78 x[i] = tmp / a[i][i]; 79 } 80 for (R int i = 1; i <= n; ++i) printf("%.10lf ", x[i]); 81 return 0; 82 }
[Sdoi2017]相关分析
把式子强拆开来发现维护区间x_i的和，y_i的和，x_i^2的和，x_i*y_i的和。还需要资磁x,y分别区间加，区间覆盖成一个等差数列（因为公差为1所以比较容易维护）。
这些线段树都可以做，细节比较多吧，调的时候最好还是靠对拍。
1 #include <cstdio> 2 3 #define R register 4 #define maxn 1048576 5 int xi[maxn], yi[maxn]; 6 typedef long long ll; 7 typedef double db; 8 struct data { 9 db x, y, xy, xx; 10 inline data operator + (const data &that) const {return (data) {x + that.x, y + that.y, xy + that.xy, xx + that.xx};} 11 inline data operator += (const data &that) {x += that.x; y += that.y; xy += that.xy; xx += that.xx; } 12 }; 13 struct Seg { 14 int tag_set_x, tag_set_y, tag_add_x, tag_add_y; 15 data x; 16 } tr[maxn]; 17 ll i2[maxn]; 18 inline void update(R int o) 19 { 20 tr[o].x = tr[o << 1].x + tr[o << 1 | 1].x; 21 } 22 void data_add(R data &x, R int s, R int t, R int len) 23 { 24 x.xx += 2 * s * x.x + (db) s * s * len; 25 x.xy += s * x.y + t * x.x + (db) s * t * len; 26 x.x += (db) s * len; 27 x.y += (db) t * len; 28 } 29 void data_set(R data &x, R int s, R int t, R int l, R int r) 30 { 31 R ll si = (db) (l + r) * (r - l + 1) / 2; 32 x.x = (db) s * (r - l + 1) + si; 33 x.y = (db) t * (r - l + 1) + si; 34 x.xx = (db) s * s * (r - l + 1) + 2 * s * si + i2[r] - i2[l - 1]; 35 x.xy = i2[r] - i2[l - 1] + (db) s * t * (r - l + 1) + si * (s + t); 36 // printf("%lld %lld %lld %lld ", x.x, x.y, x.xx, x.xy); 37 } 38 void pushdown(R int o, R int l, R int r) 39 { 40 R int mid = l + r >> 1; 41 if (tr[o].tag_set_x != -1 || tr[o].tag_set_y != -1) 42 { 43 data_set(tr[o << 1].x, tr[o].tag_set_x, tr[o].tag_set_y, l, mid); 44 data_set(tr[o << 1 | 1].x, tr[o].tag_set_x, tr[o].tag_set_y, mid + 1, r); 45 46 tr[o << 1].tag_set_x = tr[o].tag_set_x; 47 tr[o << 1].tag_set_y = tr[o].tag_set_y; 48 tr[o << 1 | 1].tag_set_x = tr[o].tag_set_x; 49 tr[o << 1 | 1].tag_set_y = tr[o].tag_set_y; 50 tr[o << 1].tag_add_x = 0; 51 tr[o << 1 | 1].tag_add_x = 0; 52 tr[o << 1].tag_add_y = 0; 53 tr[o << 1 | 1].tag_add_y = 0; 54 55 tr[o].tag_set_x = tr[o].tag_set_y = -1; 56 } 57 if (tr[o].tag_add_x || tr[o].tag_add_y) 58 { 59 data_add(tr[o << 1].x, tr[o].tag_add_x, tr[o].tag_add_y, mid - l + 1); 60 data_add(tr[o << 1 | 1].x, tr[o].tag_add_x, tr[o].tag_add_y, r - mid); 61 62 tr[o << 1].tag_add_x += tr[o].tag_add_x; 63 tr[o << 1].tag_add_y += tr[o].tag_add_y; 64 tr[o << 1 | 1].tag_add_x += tr[o].tag_add_x; 65 tr[o << 1 | 1].tag_add_y += tr[o].tag_add_y; 66 67 tr[o].tag_add_x = tr[o].tag_add_y = 0; 68 } 69 } 70 void build(R int o, R int l, R int r) 71 { 72 tr[o].tag_set_x = tr[o].tag_set_y = -1; tr[o].tag_add_x = tr[o].tag_add_y = 0; 73 if (l == r) 74 { 75 tr[o].x = (data) {xi[l], yi[l], (db) xi[l] * yi[l], (db) xi[l] * xi[l]}; 76 return ; 77 } 78 R int mid = l + r >> 1; 79 build(o << 1, l, mid); build(o << 1 | 1, mid + 1, r); 80 update(o); 81 } 82 data ret; int ql, qr, s, t; 83 void query(R int o, R int l, R int r) 84 { 85 if (ql <= l && r <= qr) 86 { 87 ret += tr[o].x; return ; 88 } 89 R int mid = l + r >> 1; 90 pushdown(o, l, r); 91 if (ql <= mid) query(o << 1, l, mid); 92 if (mid < qr) query(o << 1 | 1, mid + 1, r); 93 update(o); 94 } 95 void modify_add(R int o, R int l, R int r) 96 { 97 if (ql <= l && r <= qr) 98 { 99 tr[o].tag_add_x += s; 100 tr[o].tag_add_y += t; 101 data_add(tr[o].x, s, t, r - l + 1); 102 return ; 103 } 104 R int mid = l + r >> 1; 105 pushdown(o, l, r); 106 if (ql <= mid) modify_add(o << 1, l, mid); 107 if (mid < qr) modify_add(o << 1 | 1, mid + 1, r); 108 update(o); 109 } 110 void modify_set(R int o, R int l, R int r) 111 { 112 if (ql <= l && r <= qr) 113 { 114 tr[o].tag_set_x = s; 115 tr[o].tag_set_y = t; 116 tr[o].tag_add_x = tr[o].tag_add_y = 0; 117 data_set(tr[o].x, s, t, l, r); 118 return ; 119 } 120 R int mid = l + r >> 1; 121 pushdown(o, l, r); 122 if (ql <= mid) modify_set(o << 1, l, mid); 123 if (mid < qr) modify_set(o << 1 | 1, mid + 1, r); 124 update(o); 125 } 126 int main() 127 { 128 R int n, m; scanf("%d%d", &n, &m); 129 for (R int i = 1; i <= n; ++i) scanf("%d", &xi[i]); 130 for (R int i = 1; i <= n; ++i) scanf("%d", &yi[i]); 131 for (R int i = 1; i <= n; ++i) i2[i] = i2[i - 1] + (db) i * i; 132 build(1, 1, n); 133 for (; m; --m) 134 { 135 R int opt, l, r; scanf("%d%d%d", &opt, &ql, &qr); 136 if (opt == 1) 137 { 138 ret = (data) {0, 0, 0, 0}; 139 query(1, 1, n); l = ql; r = qr; 140 R db _x = (db) ret.x / (r - l + 1), _y = (db) ret.y / (r - l + 1); 141 printf("%.10lf ", (ret.xy - _y * ret.x - _x * ret.y + _x * _y * (r - l + 1)) / (ret.xx - 2 * _x * ret.x + _x * _x * (r - l + 1))); 142 } 143 else if (opt == 2) 144 { 145 scanf("%d%d", &s, &t); 146 modify_add(1, 1, n); 147 } 148 else 149 { 150 scanf("%d%d", &s, &t); 151 modify_set(1, 1, n); 152 } 153 } 154 return 0; 155 }