简化题意
定义一个长度为\(n\)的权值\(val(p) = \sum \limits_{i=1}^{n-1}p^{'}_ip^{'}_{i+1}\)，其中\(p^{'}\)为\(p\)排序后的序列。特殊的，如果\(n\le 1\),\(val(p)=\text{0}\)
现在给定长度为\(n\)一个序列\(a\)，\(a\)的所有子序列\(a^{'}\)的\(val(a^{'})\)的\(\text{sum}\)
hint
复杂度
\(O(qn^2) \to O(qn) \to \text{无修改} \to O(q \text{log}\ n)\)
做法的提示
考虑分治数据结构，信息合并可以\(\mathcal{O}(1)\)
做法
最暴力的做法
考虑到排列顺序其实不会影响答案，所以我们忽略，考虑离散化。我们令排序后的序列为\(p\)，点对\((i, j)\)能对答案产生贡献的概率为\(\frac{1}{2 ^ {j - i + 1}}\)，所以可以列出答案式子：
\[ans = \sum \limits_{i = 1}^{n} \sum \limits_{j = i + 1}^{n} \frac{p_ip_j}{2^{j-i+1}} \]对于每一次的更改直接考虑重新计算一边答案就行了
从式子层面进行优化
上面提到要考虑分治，于是考虑分治。由于左区间和右区间一定没有交点，因此我们可以考虑拆开贡献。显然的，贡献能够分成三部分：
- \(i, j\)都在左区间
- \(i, j\)都在右区间
- \(i\)在左区间，\(j\)在右区间(钦定\(i < j\))
容易对第三种情况列出式子：
\(\Large \sum \limits_{i = l}^{mid} \sum \limits_{j = mid + 1}^{r} \frac{p_ip_j}{2 ^ {j - i + 1}}\)
= \(\Large \sum \limits_{i = l}^{mid} \sum \limits_{j = mid + 1}^{r} \frac{p_ip_j}{2 ^ {mid - i + 1} \times 2 ^ {r - mid}}\)
= \(\Large \sum \limits_{i = l}^{mid} \sum \limits_{j = mid + 1}^{r} \frac{p_i}{2 ^ {mid - i + 1}} \frac{p_j}{2 ^ {r - mid}}\)
把sigma拆开，变成\(\Large (\sum \limits_{i = l}^{mid}\frac{p_i}{2^{mid - i + 1}})(\sum \limits_{i = mid+1}^{r}\frac{p_i}{2^{r - mid}})\)
于是想到把这三个东西进行维护。我们令
\[\left\{\begin{matrix} f(l, r) = \sum \limits_{i = l}^{mid} \sum \limits_{j = mid + 1}^{r} \frac{p_ip_j}{2 ^ {j - i + 1}} \\ g(l, r) = \sum \limits_{i = l}^{r}\frac{p_i}{2^{r - i + 1}} \\ h(l, r) = \sum \limits_{i = l}^{r}\frac{p_i}{2^{r - i + 1}} \end{matrix}\right. \]然后可以发现
\[ \left\{\begin{matrix} f(l, r) = f(l, mid) + f(mid + 1, r) + h(l, mid)g(mid + 1, r) \\ g(l, r) = g(l, mid) + \frac{g(mid + 1, r)}{2 ^ {mid - l + 1}} \\ h(l, r) = \frac{h(l, mid)}{2 ^ {r - mid}} + h(mid + 1, r) \end{matrix}\right. \]且最终答案为\(f(1, n)\)。
于是直接对于每一次询问我们重新运算就行了，这是\(\mathcal{O}(qn)\)的》
正解
我们可以非常容易的发现很大一部分是重复计算的，于是我们就考虑用数据结构维护。注意，在离散化的时候不要unique，将同一个数留下不同的编号，然后扔到线段树里面维护就行了。这种做法是\(O(n + q\text{log}\ n) + O(n + q)\)的，可以通过此题。
code
using mint = georgeyucjr::modint1000000007;
constexpr int N = 3e5 + 5;
int n, q, a[N], p[N], b[N * 2], val[N];
unordered_map<int, int> cnt;
mint ipw2[N];
mint Iv2 = mint(2).inv();
struct Node {
int len;
mint ans, lv, rv;
} seg[N << 3];
Node operator+(const Node&x, const Node&y) {
Node res;
res.len = x.len + y.len;
res.lv = x.lv + y.lv * ipw2[x.len];
res.rv = x.rv * ipw2[y.len] + y.rv;
res.ans = x.ans + y.ans + x.rv * y.lv;
return res;
}
void pushup(int index) {
seg[index] = seg[lson] + seg[rson];
}
void build(int index, int l, int r) {
if (l == r) return ;
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(index);
}
void change(int index, int l, int r, int qpos, int t) {
if (l == r) {
assert(l == qpos);
seg[index].ans = 0;
if (t > 0) {
++seg[index].len;
} else {
--seg[index].len;
}
seg[index].lv += t * Iv2;
seg[index].rv += t * Iv2;
return ;
} int mid = (l + r) >> 1;
if (qpos <= mid)
change(lson, l, mid, qpos, t);
else if (qpos > mid)
change(rson, mid + 1, r, qpos, t);
else assert(false);
pushup(index);
}
signed main() {
ipw2[0] = 1, ipw2[1] = Iv2;
rep(i, 2, N - 5) ipw2[i] = ipw2[i - 1] * Iv2;
read(n);
rep(i, 1, n) read(a[i]), b[i] = a[i];
read(q);
rep(i, 1, q, pos, v) {
read(pos, v);
b[i + n] = v;
p[i] = pos;
val[i] = v;
}
// 注意不要习惯加unique了，要将同value的不同的数给区分开
sort(b + 1, b + n + q + 1);
rep(i, 1, n)
a[i] = lower_bound(b + 1, b + n + q + 1, a[i]) - b + (++cnt[a[i]]) - 1;
rep(i, 1, q)
val[i] = lower_bound(b + 1, b + n + q + 1, val[i]) - b + (++cnt[val[i]]) - 1;
rep(i, 1, n)
change(1, 1, n + q, a[i], b[a[i]]);
writeln(seg[1].ans.val());
rep(i, 1, q) {
change(1, 1, n + q, a[p[i]], -b[a[p[i]]]);
change(1, 1, n + q, a[p[i]] = val[i], b[val[i]]);
writeln(seg[1].ans.val());
}
#if defined(LOCAL) && !defined(CPH)
std::cerr << "Spend Time : " << clock() * 1. / CLOCKS_PER_SEC * 1e3 << " ms \n";
#endif
return flush(), 0;
}
完整代码在code
标签：frac,val,limits,int,sum,mid,sol,CF1316F From： https://www.cnblogs.com/georgeyucjr/p/18397115