LG-P4184 [USACO18JAN]Sprinklers P Solution
目录更好的阅读体验戳此进入
题面
$ n \times n $ 的网格图（$ n $个格点，从 $ (0, 0) $ 到 $ (n - 1, n - 1) $），给定 $ n $ 个点的坐标 $ (i, j) $，保证任意两个坐标的横或纵均不相等，每个点会对 $ \forall(x, y), x \in [i, n - 1], y \in [j, n - 1] $ 进行洒水，对 $ \forall(x, y), x \in [0, i], y \in [0, j] $ 进行施肥，要求选出一片矩形，使得其中每个格点都既浇水又施肥，求方案数。
或者也可以描述为，给定 $ n $ 个关键点，要求选一个矩形使得其中左上右下各自至少有一个关键点，求方案数。
$ 1 \le n \le 10^5 $。
Solution
前言：核心思路参考自 这篇Blog，主要是我太弱了，有点没太看懂这个大佬柿子的精妙推导，于是尝试自己推了一遍，用比较低端的方法也成功推到 $ O(n) $ 了，故提供一种更无脑一些的推柿子的方法。
一道奇怪的题，最终可以转化为无脑推柿子。
首先借一个题解区的图（图片来自 这篇Blog）：
不难发现一个妙妙性质，即在第 $ i $ 行里，我们假设可行的矩形的左右端点为 $ [l_i, r_i] $，那么 $ l_i $ 即为在其不在其下面的所有关键点横坐标的最小值，$ r_i $ 为不在其上面的最大值，按照这个规律我们也可以处理出来对于每一列纵坐标可行的最小值 $ up_i $，然后可以写一个 $ O(n^4) $ 的类似二位数点矩形的东西，再化简。前面这里如果还是看不懂可以去翻翻题解区，这里不再重复赘述。令 $ (i, j) $ 为右下端点，$ (x, y) $ 为左上端点，有答案为：
然后我们令 $ sum1_n = \sum_{i = 1}^{n}up_i $，再令 $ sum2_n = \sum_{i = 1}^{n}sum1_i $，有：
\[\begin{aligned} &\sum_{i = 1}^{n}\left( i\left( \dfrac{1}{2}(r_i - l_i)(r_i - l_i + 1) \right) - \sum_{j = l_i}^{r_i} \sum_{y = l_i}^{j - 1}up_y \right) \\ =& \sum_{i = 1}^{n}\left( i\left( \dfrac{1}{2}(r_i - l_i)(r_i - l_i + 1) \right) - \sum_{j = l_i}^{r_i}(sum1_{j - 1} - sum1_{l_i - 1}) \right) \\ =& \sum_{i = 1}^{n}\left( i\left( \dfrac{1}{2}(r_i - l_i)(r_i - l_i + 1) \right) - \sum_{j = l_i}^{r_i}sum1_{j - 1} + (r_i - l_i + 1)sum1_{l_i - 1} \right) \\ =& \sum_{i = 1}^{n}\left( i\left( \dfrac{1}{2}(r_i - l_i)(r_i - l_i + 1) \right) - \sum_{j = l_i - 1}^{r_i - 1}sum1_{j} + (r_i - l_i + 1)sum1_{l_i - 1} \right) \\ =& \sum_{i = 1}^{n}\left( i\left( \dfrac{1}{2}(r_i - l_i)(r_i - l_i + 1) \right) - sum2_{r_i - 1} + sum2_{l_i - 2} + (r_i - l_i + 1)sum1_{l_i - 1} \right) \end{aligned} \]然后就成功从 $ O(n^4) $ 推到 $ O(n) $ 了。
Code
#define _USE_MATH_DEFINES
#include <bits/extc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
using namespace std;
using namespace __gnu_pbds;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define MOD (ll)(1e9 + 7)
#define GetSum1(x) ((x) > 0 ? sum1[x] : 0)
#define GetSum2(x) ((x) > 0 ? sum2[x] : 0)
template< typename T = int >
inline T read(void);
int N;
int y[110000];
int l[110000], r[110000], up[110000];
ll sum1[110000];
ll sum2[110000];
int main(){
N = read();
for(int i = 1; i <= N; ++i){
int rx = read() + 1, ry = read() + 1;
y[rx] = ry;
}l[0] = INT_MAX; r[N + 1] = -1;
for(int i = 1; i <= N; ++i)l[i] = min(l[i - 1], y[i]);
for(int i = N; i >= 1; --i)r[i] = max(r[i + 1], y[i]);
int cur = r[1];
for(int i = 1; i <= N; ++i)while(cur && cur >= l[i])up[cur] = i, --cur;
for(int i = 1; i <= N; ++i)sum1[i] = (sum1[i - 1] + up[i]) % MOD;
for(int i = 1; i <= N; ++i)sum2[i] = (sum2[i - 1] + sum1[i]) % MOD;
ll ans(0);
for(int i = 1; i <= N; ++i){
ans = (ans + ((ll)r[i] - l[i]) * (r[i] - l[i] + 1) / 2ll % MOD * i % MOD) % MOD;
ans = (ans - GetSum2(r[i] - 1) + GetSum2(l[i] - 2) + MOD) % MOD;
ans = (ans + ((ll)r[i] - l[i] + 1) * GetSum1(l[i] - 1) % MOD) % MOD;
}printf("%lld\n", ans);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
short flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
UPD
update-2022_11_03 初稿
标签：LG,right,int,题解,sum,up,sum1,P4184,left From： https://www.cnblogs.com/tsawke/p/16945569.html