n<=105,0<=li<=ri<=109,0<=si<=109
E[f(i)] = ∑rij=lisi∗E[pi] 正着考虑是不太容易的，考虑其它对E[p_i]的贡献。 1.设有j < i, aj<=ai 就可以有贡献 ai−aj+１rj−lj+1 。 2.设有j>i, aj<ai
下列描述以1为准。 现在不具体考虑 aj 的值，而是从大体上考虑，j对a的值取[ lj..rj ]的贡献是一个等差数列，对[ rj+1 ..max]的贡献都是1.
于是打一棵动态权值线段树来维护就好了。 2同理。
注意贡献的意义是一个数前面有多少个，而排名是从1开始算的，所以要加1.
线段树加上一个等差数列： 打tag，s表示这个区间的首项，t表示公差，合并时都加起来。下传时右区间的s’=s+t*左区间的大小。
Code：
#include<cstdio> #include<cstring> #define ll long long #define fo(i, x, y) for(ll i = x; i <= y; i ++) #define fd(i, x, y) for(ll i = x; i >= y; i --) using namespace std; const ll N = 100005, mo = 1e9 + 7; const ll ni_2 = 5e8 + 4; const ll M = 1e9; ll n, ni[N]; ll s[N], l[N], r[N], ans[N]; struct tree { ll l, r; ll s, t, w; }t[10000000]; ll tot; ll ksm(ll x, ll y) { ll s = 1; while(y) { if(y & 1) s = (s * x) % mo; x = (x * x) % mo; y >>= 1; } return s; } void add(ll i, ll x, ll s, ll tt) { ll p = (s + tt * (x - 1) % mo) % mo; t[i].w += (s + p) * x % mo * ni_2 % mo; t[i].w %= mo; } void down(ll i, ll x, ll y) { ll m = (x + y) / 2; t[t[i].l].s += t[i].s; t[t[i].r].s += t[i].s + t[i].t * (m - x + 1) % mo; t[t[i].l].t += t[i].t; t[t[i].r].t += t[i].t; t[t[i].l].s %= mo; t[t[i].r].s %= mo; t[t[i].l].t %= mo; t[t[i].r].t %= mo; add(t[i].l, m - x + 1, t[i].s, t[i].t); add(t[i].r, y - m, (t[i].s + t[i].t * (m - x + 1) % mo) % mo, t[i].t); t[i].s = 0; t[i].t = 0; } void change(ll i, ll x, ll y, ll l, ll r, ll s, ll tt) { if(l > r) return; if(x == l && y == r) { add(i, y - x + 1, s, tt); t[i].s += s; t[i].t += tt; return; } ll m = (x + y) / 2; if(t[i].l == 0) t[i].l = ++ tot; if(t[i].r == 0) t[i].r = ++ tot; down(i, x, y); if(r <= m) change(t[i].l, x, m, l, r, s, tt); else if(l > m) change(t[i].r, m + 1, y, l, r, s, tt); else change(t[i].l, x, m, l, m, s, tt), change(t[i].r, m + 1, y, m + 1, r, (s + tt * (m - l + 1)) % mo, tt); t[i].w = (t[t[i].l].w + t[t[i].r].w) % mo; } ll find(ll i, ll x, ll y, ll l, ll r) { if(l > r) return 0; if(x == l && y == r) return t[i].w; ll m = (x + y) / 2; if(t[i].l == 0) t[i].l = ++ tot; if(t[i].r == 0) t[i].r = ++ tot; down(i, x, y); if(r <= m) return find(t[i].l, x, m, l, r); else if(l > m) return find(t[i].r, m + 1, y, l, r); else return (find(t[i].l, x, m, l, m) + find(t[i].r, m + 1, y, m + 1, r)) % mo; } int main() { freopen("sort.in", "r", stdin); freopen("sort.out", "w", stdout); scanf("%lld", &n); fo(i, 1, n) scanf("%lld %lld %lld", &s[i], &l[i], &r[i]); fo(i, 1, n) ni[i] = ksm(r[i] - l[i] + 1, mo - 2); tot = 1; fo(i, 1, n) { ans[i] += find(1, 0, M, l[i], r[i]); change(1, 0, M, l[i], r[i], ni[i], ni[i]); change(1, 0, M, r[i] + 1, M, 1, 0); } memset(t, 0, sizeof(t)); tot = 1; fd(i, n, 1) { ans[i] += find(1, 0, M, l[i], r[i]); ans[i] = ans[i] * ni[i] % mo + 1; change(1, 0, M, l[i] + 1, r[i] + 1, ni[i], ni[i]); change(1, 0, M, r[i] + 2, M, 1, 0); } ll as = 0; fo(i, 1, n) as = (as + s[i] * ans[i] % mo) % mo; printf("%lld", as); }