分数：\(100 + 50 + 0 + 0 = 150\)
神秘计数赛，使我的 rating \(+8\)。
T1
这道题很糖，但架不住我更糖。
如果暴力枚举所有子矩形，时间复杂度是 \(O(n^4)\) 的，肯定会 T 飞。
首先，与其直接计算有多少个五彩斑斓的子矩阵，不如去求有多少个“黯淡无光”的子矩阵 —— 也就是四个顶点颜色都相同的子矩阵，然后用总子矩阵数减去黯淡无光的子矩阵数，得到最终答案。
考虑如下情况：
（省略号代指无关数字）
第 \(1\) 列的两个 \(1\) 可以和第 \(1, 2, 3, 4\) 列的两个 \(1\) 组成黯淡无光的子矩阵；第 \(2\) 列的也可以和第 \(2, 3, 4\) 列的组成……以此类推，假如钦定两行，它们有 \(n\) 列中上下两行的颜色相同，就会产生 \(1 + 2 + \cdots + n = \frac{(1 + n)n}{2}\) 个黯淡无光子矩阵。
综上，我们可以在图中遍历两行，然后对这两行的元素从左到右扫描，如果碰到两行颜色相同，就计算答案（既可以边扫描边计算，也可以扫描一行后再根据公式计算，以下代码用的是前者）。扫描完一行不要忘记清空计数器。
总时间复杂度 \(O(n^3)\)。
#include <bits/stdc++.h>
#define int long long
const int N = 410;
int n, m, a[N][N], ans, cnt[N * N];signed main() {freopen("colorful.in", "r", stdin);freopen("colorful.out", "w", stdout);std::ios::sync_with_stdio(false); std::cin.tie(0);std::cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {std::cin >> a[i][j];ans += i * j;}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {for (int k = 1; k <= m; k++) {if (a[i][k] == a[j][k]) {cnt[a[i][k]]++;ans -= cnt[a[i][k]];}}for (int k = 1; k <= m; k++) {if (a[i][k] == a[j][k]) {cnt[a[i][k]] = 0;}}}}std::cout << ans << '\n';return 0;
}
T2
致敬传奇比 T1 简单的 T2。
首先很容易看出输入数据中的 \(x\) 是没有任何用的，因为相同城市的拥堵时段没有重叠的部分。
另外，如果这道题的数据范围为 \(0 \le S \le T \le 10^6\)，就变成彻头彻尾的唐题了，只需要简单地差分一下即可。因此，本题的关键就在于离散化。离散之后按照正常方法进行差分，最后统计答案时，要乘方上每个离散化后的时间段所代表的天数。
当然，如果这么说，这道题看起来还是不难。但我觉得本题难在一些细节，它们使我在场上抓狂：
- 不要只将拥堵时段的首尾加入离散数组，也要将 \(S\) 和 \(T\) 加入。
- 将 \(r\) 加入离散数组时要 \(+1\)。不要问我怎么知道的，自己画画图就懂了。
- 进行差分时不要像往常一样
diff[infos[i].r+1]++，而要diff[infos[i].r]++。也可以通过画图理解。
总时间复杂度 \(m \log m\)。
#include <bits/stdc++.h>
#define int long long
const int N = 2e6+10, MOD = 1e9+7;
struct Info {int x, l, r;
} infos[(int)1e6+10];
int n, m, s, t;
int a[N], dayCnt[N], diff[N], ans = 1;
std::vector<int> mp;inline int qpow(int a, int b) {int res = 1;while (b) {if (b & 1) res = res * a % MOD;a = a * a % MOD;b >>= 1;}return res % MOD;
}signed main() {freopen("ex_travel3.in", "r", stdin);freopen("travel3.out", "w", stdout);std::ios::sync_with_stdio(false); std::cin.tie(0);std::cin >> n >> m >> s >> t;mp.push_back(-1);for (int i = 1; i <= m; i++) {std::cin >> infos[i].x >> infos[i].l >> infos[i].r;infos[i].l = infos[i].l - s + 1;infos[i].r = infos[i].r - s + 1;infos[i].r++;mp.push_back(infos[i].l), mp.push_back(infos[i].r);}mp.push_back(t - s + 2);mp.push_back(1);std::sort(mp.begin() + 1, mp.end());auto it = std::unique(mp.begin(), mp.end());mp.erase(it, mp.end());for (int i = 1; i < mp.size() - 1; i++) {dayCnt[i] = mp[i + 1] - mp[i];}for (int i = 1; i <= m; i++) {infos[i].l = std::lower_bound(mp.begin(), mp.end(), infos[i].l) - mp.begin();infos[i].r = std::lower_bound(mp.begin(), mp.end(), infos[i].r) - mp.begin();}int day = std::lower_bound(mp.begin(), mp.end(), t-s+2) - mp.begin();diff[1] = n;for (int i = 1; i <= m; i++) {diff[infos[i].l]--;diff[infos[i].r]++;}for (int i = 1; i <= day- 1; i++) {diff[i] += diff[i-1];if (diff[i] < 0) diff[i] = 0;}for (int i = 1; i <= day - 1; i++) {ans *= qpow(diff[i], dayCnt[i]);ans %= MOD;}std::cout << ans % MOD << '\n';return 0;
}