题目描述
小 Z 终于迎来了自己的大学生活最后的时刻，他决定用自己的积蓄来一场说走就走的毕业旅行，并且不玩的开心不上班。然而，他很快就发现这个决定并非那么简单。由于是暑假，假期人多，他既不想错过旅行的最佳时期，又不想在人群中挣扎，预测旅游热门城市的拥挤时段，就像是一道难题摆在他的面前。
在浏览了一堆旅游网站和社交媒体后，小 Z 发现了一个可以帮助他制定完美旅行计划的手机应用程序。这个应用程序基于人工智能算法，预测了旅游热门城市在不同时段的拥挤程度，为旅行者提供了精准的建议。
小 Z 选出来想要旅行的 \(n\) 个城市（城市编号为 \(1 \sim n\)），由于现在交通非常发达，可以认为这些城市之间互相都可以连通，小 Z 每天只会在一个不拥挤的城市停留，第二天他可以选择去任意一个不拥挤的城市并一整天留在那里（当然，也可以继续留在原本的城市，如果原本的城市不拥挤的话），然后他选择这 \(n\) 个城市，出发日期 \(S\) 和返回日 \(T\) 期（可以理解为小 Z 的旅游日期为第 \([S, T]\) 天），应用程序根据这些信息，开始生成一份详细的报告，其中包括了 \(m\) 条信息，每条信息包含三个数 \(x\)，\(l\)，\(r\)，在第 \([l, r]\) 天是小 Z 选出来的第 \(x\) 个城市是拥挤的，通过这份报告，小 Z 了解到了不同城市的拥挤时段，并制定了避开高峰期的旅行计划。有了这个应用程序的帮助，小 Z 可以尝试制定一份完美的旅行计划，开启了一场避开人群的毕业旅行。
由于小 Z 非常懒，不逛完所有城市也无所谓，现在小 Z 想知道他能够实现错峰毕业旅行的方案有多少种（注意小 Z 可以从任意一个城市开始毕业旅行，我们认为两个方案是不同的当且仅当至少存在一天两个方案小 Z 所处的城市不同），由于这个方案数很大，他只想知道方案数对 \(10^9 + 7\) 取模以后的结果。
分析
考试的时候不会离散化，只能打暴力了。（说来惭愧，其实这种要离散化区间的题目，去年就做过一道，不过由于那道题范围较小，空间限制也比较宽，不离散化也可以过，所以这种离散化我直到现在才学会，而事实上，这是一个很简单的知识点。）
先讲讲 \(50\) 分做法（事实上，数组开大一点是可以拿 \(70\) 分的）。发现对于某一天，如果当天有 \(x\) 座城市是拥挤的，那么这一天有 \(n - x\) 座城市是可以待的，当天的方案数就是 \(n - x\)，把每一天的方案数乘起来就好了。\(0 \le S \le T \le 10^9\)，但是部分数据 \(T - S \le 5000\)，因此将 \([S, T]\) 平移到 \([1, T - S + 1]\)，再将信息中的 \(l, r\) 也平移一下，即可得到相当可观的暴力分。
然后再讲满分做法。对于 \(100 \%\) 的数据，\(T - S \le 10^9\)，考虑离散化。对于区间的离散化，有一个问题，就是如果直接对端点离散化，那么对本就相邻的区间没有影响，而原本不相邻的区间，离散化后两个区间就挨在一起了，这样子显然是不正确的。要解决这个问题，我们考虑‘插空’，对于区间 \([l, r]\)，我们除了将 \(l, r\) 离散化，还将 \(l - 1, r + 1\) 也一并离散化，这样，原本不相邻的区间离散后中间就会有间隔，而原本相邻的区间则仍然挨在一起。
\(50\) 分做法中已经说了每一天的方案数是怎么来的，那么进一步观察可以发现：现一段时间城市的拥挤情况 \(x\) 不变，经过这一段时间 \(t\) 后方案数变化其实是乘上 \(x^t\)。
我们可以通过线段树来处理，离散化之后建立线段树，对于每条信息，直接区间加法即可。读完信息之后，我们再通过和建树一样的方法把所有叶子节点，也就是单点的信息提出来，然后带入上面的式子即可。
然后还有一点细节，就是离散化之后，每个信息 \([l, r]\) 会产生四个值，再算上 \(S, T\)，最多会有 \(4m + 2\) 个数。本题空间有限，线段树必须动态开点，并且不能无脑给所有变量开 long long。
代码
- \(50\) 分（事实上有 \(70\) 分）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const ll maxn = 5005;
const ll maxm = 1e7 + 5;
ll n, m, S, T;
ll delta, ans;
ll busy[maxm];
signed main() {
freopen("travel.in", "r", stdin);
freopen("travel.out", "w", stdout);
scanf("%lld%lld%lld%lld", &n, &m, &S, &T);
delta = S - 1;
S -= delta, T -= delta;
for (ll i = 1; i <= m; i++) {
ll x, l, r;
scanf("%lld%lld%lld", &x, &l, &r);
l -= delta, r -= delta;
for (ll j = l; j <= r; j++) {
busy[j] = (busy[j] + 1) % mod;
}
}
ans = 1;
for (ll i = S; i <= T; i++) {
ans = ans * (n - busy[i] + mod) % mod;
}
printf("%lld", ans);
return 0;
}
- \(100\) 分
#include <bits/stdc++.h>
using namespace std;
namespace QuickIO {
// 快读快写
template<typename T> inline void read(T &x) {
x = 0; signed op = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') op = -1;
for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
x *= op;
}
template<typename T, typename ...Args> inline void read(T &x, Args &...rest) {
read(x), read(rest...);
}
template<typename T> void write(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template<> void write<char>(char x) {
putchar(x);
}
template<typename T, typename ...Args> void write(T x, Args ...rest) {
write(x), write(rest...);
}
}
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 5005;
const int maxm = 4e6 + 5;
int n, m, S, T;
struct SegmentTree {
int lson, rson;
ll val, tag;
} tree[maxm << 1];
struct Info {
int l, r;
} info[maxm];
ll dis[maxm], uncrowded[maxm];
int range;
inline ll quickpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
inline void pushup(int root) {
tree[root].val = tree[tree[root].lson].val + tree[tree[root].rson].val;
}
inline void pushdown(int root, int l, int r) {
if (!tree[root].tag) return;
int mid = (l + r) >> 1;
tree[tree[root].lson].val = (tree[tree[root].lson].val + tree[root].tag * (mid - l + 1) % mod) % mod;
tree[tree[root].rson].val = (tree[tree[root].rson].val + tree[root].tag * (r - mid) % mod) % mod;
tree[tree[root].lson].tag = (tree[tree[root].lson].tag + tree[root].tag) % mod;
tree[tree[root].rson].tag = (tree[tree[root].rson].tag + tree[root].tag) % mod;
tree[root].tag = 0;
}
int idcnt, rootid;
void build(int &root, int l, int r) {
if (!root) root = ++idcnt;
if (l == r) return;
int mid = (l + r) >> 1;
build(tree[root].lson, l, mid);
build(tree[root].rson, mid + 1, r);
}
void update(int &root, int l, int r, ll val, int nowl, int nowr) {
if (!root) root = ++idcnt;
if (nowl >= l && nowr <= r) {
tree[root].val += val * (nowr - nowl + 1);
tree[root].tag += val;
return;
}
pushdown(root, nowl, nowr);
int mid = (nowl + nowr) >> 1;
if (mid >= l) update(tree[root].lson, l, r, val, nowl, mid);
if (mid < r) update(tree[root].rson, l, r, val, mid + 1, nowr);
pushup(root);
}
void convertTreeToSequence(int root, int l, int r) {
if (!root) return;
if (l == r) {
uncrowded[l] = tree[root].val;
return;
}
pushdown(root, l, r);
int mid = (l + r) >> 1;
convertTreeToSequence(tree[root].lson, l, mid);
convertTreeToSequence(tree[root].rson, mid + 1, r);
}
signed main() {
freopen("travel.in", "r", stdin);
freopen("travel.out", "w", stdout);
QuickIO::read(n, m, S, T);
dis[++dis[0]] = S, dis[++dis[0]] = T;
for (int i = 1; i <= m; i++) {
QuickIO::read(info[i].l, info[i].l, info[i].r);
dis[++dis[0]] = info[i].l - 1;
dis[++dis[0]] = info[i].l;
dis[++dis[0]] = info[i].r;
dis[++dis[0]] = info[i].r + 1;
}
sort(dis + 1, dis + 1 + dis[0]);
range = unique(dis + 1, dis + 1 + dis[0]) - dis - 1;
build(rootid, 1, range);
for (int i = 1; i <= m; i++) {
info[i].l = lower_bound(dis + 1, dis + 1 + range, info[i].l) - dis;
info[i].r = lower_bound(dis + 1, dis + 1 + range, info[i].r) - dis;
update(rootid, info[i].l, info[i].r, 1, 1, range);
}
convertTreeToSequence(rootid, 1, range);
S = lower_bound(dis + 1, dis + 1 + range, S) - dis;
T = lower_bound(dis + 1, dis + 1 + range, T) - dis;
ll ans = 1;
for (int i = S; i <= T; i++) {
uncrowded[i] = n - uncrowded[i];
}
for (int i = S; i < T; i++) {
ans = (ans * uncrowded[i]) % mod;
int freeCity = min(uncrowded[i], uncrowded[i + 1]);
int period = dis[i + 1] - dis[i] - 1;
if (freeCity && period) {
ans = (ans * quickpow(freeCity, period)) % mod;
}
}
ans = (ans * uncrowded[T]) % mod;
QuickIO::write(ans);
return 0;
}