NOIP2023模拟13联测34 B.competition

本文主要是介绍NOIP2023模拟13联测34 B.competition，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

NOIP2023模拟13联测34 B.competition

文章目录

NOIP2023模拟13联测34 B.competition
- 题目大意
- 思路
- code

题目大意

现在有 $n$ 个区间 $l_i , r_i]$ ，现在问你选取若干的连续的区间的区间并的大小的和。

思路

设 $pre_{i , j}$ 表示前 $i - 1$ 个区间内，包含点 $j$ 的最靠右的数是多少。

可以发现答案就是
$\sum_{i = 1}^n (r_i - l_i +1) * i * (n - i + 1) - pre_{i , j} * (n - i +1)$
也就是这个区间被记入答案的次数乘上区间的大小再减去重复的次数

可以用一棵线段树维护加离散化来维护。

先统计答案，然后用线段树更新 $p re$

要卡常

code

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e6 + 5;
const LL mod = 1e9 + 7; 
int n , m , re1;
LL l[N] , r[N] , re[N << 2] , tr[N << 4] , lzy[N << 4] , ans;
unordered_map<LL , int> id;
inline void pushdown (int p , int l , int r) {if (!lzy[p]) return;int mid = l + r >> 1;tr[p << 1] = (re[mid + 1] - re[l] + mod) % mod * lzy[p] % mod;tr[p << 1 | 1] = (re[r + 1] - re[mid + 1] + mod) % mod * lzy[p] % mod;lzy[p << 1] = lzy[p << 1 | 1] = lzy[p];lzy[p] = 0;
}
inline LL Mod (LL x) { return x >= mod ? x - mod : x; }
inline LL qc (int p , int l , int r , int L , int R , LL x) {if (L <= l && R >= r) {LL z = tr[p];tr[p] = (re[r + 1] - re[l]) % mod * x;lzy[p] = x;return z;}else {int mid = l + r >> 1;LL z = 0;pushdown (p , l , r);if (L <= mid) z += qc (p << 1 , l , mid , L , R , x);if (mid < R) z += qc (p << 1 | 1 , mid + 1 , r , L , R , x);tr[p] = tr[p << 1] + tr[p << 1 | 1];return z;}
}
inline LL ksm (LL x , LL y) {LL z = 1;while (y) {if (y & 1) z = z * x % mod;y >>= 1;x = x * x % mod;}return z;
}
LL read () {LL val = 0;char ch = getchar ();while (ch < '0' || ch > '9') ch = getchar ();while (ch >= '0' && ch <= '9') {val = val * 10 + (ch - '0');ch = getchar ();}return val;
}
int main () {freopen ("competition.in" , "r" , stdin);freopen ("competition.out" , "w" , stdout); n = read () , m = read ();for (int i = 1 ; i <= n ; i ++) {l[i] = read () , r[i] = read ();re[++re1] = l[i];re[++re1] = r[i] + 1;}sort (re + 1 , re + re1 + 1);m = unique(re + 1 , re + re1 + 1) - re - 1;for (int i = 1 ; i <= m ; i ++) id[re[i]] = i;for (int i = 1 ; i <= n ; i ++)ans = (ans + qc (1 , 1 , m - 1 , id[l[i]] , id[r[i] + 1] - 1 , i) % mod * (n - i + 1)) % mod;ans = Mod (-ans + mod);for (int i = 1 ; i <= n ; i ++) ans = (ans + (r[i] - l[i] + 1) % mod * i % mod * (n - i + 1)) % mod;printf ("%lld" , ans * ksm ((1ll * n * (n + 1) / 2) % mod , mod - 2) % mod);return 0;
}