【NOIP2017模拟A组模拟8.5】带权排序

时间:2021-12-11 09:17:07

Description:

【NOIP2017模拟A组模拟8.5】带权排序
n<=105,0<=li<=ri<=109,0<=si<=109

题解:

E[f(i)] = rij=lisiE[pi]
正着考虑是不太容易的,考虑其它对E[p_i]的贡献。
1.设有j < i, aj<=ai 就可以有贡献 aiaj+rjlj+1
2.设有j>i, aj<ai 就可以有贡献 aiajrjlj+1

下列描述以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);
}