考虑每一个东西对答案的贡献，即这个东西取的概率乘以前面比它大的东西不取的概率。 即 直接暴力计算的复杂度为O(n2)不能接受。我们可以将d从大到小排序，用树状数组维护1 - pi的前缀积。每次插入前查询在它前面比他大的概率的乘积。 （因为从大到小插入了，所以树状数组里面的插入的都是d比他大的。） 由于维护的是乘积，所以我们树状数组要初始化成1。 代码如下： #include <bits/stdc++.h> typedef long long ll; const int mod = 119 << 23 | 1; ll Pow(ll...

这题……做法很多吧。据说莫队玄学多交几次就AC了。 题目要我们查询两个区间的不同的数的个数。我们先考虑一个区间内的做法。 这是一个经典的问题？（自行百度） 在线做法的话，只需要用可持久化线段树维护前个数中每个数最后一次出现的下标。 这样在扫一边的时候，如果某个数在前面出现过，就只要把前面的那个删掉，加上这个就好。 代码如下： for (int i = 1; i <= n; i++) { int v = a[i]; if (~last[v]) { int t = update(last[v], root[i - 1],...