题解 | #构造矩形#

E.构造矩形

由于注意力不足以强到推出题解的写法，于是悟出了一种差分的写法（误）。

假设有一条线段位于，则可以得知在位置的线段可以和它构成个的矩形，以此类推，每向右一格，能构成矩形的数量就减1。

而还有一种情况是矩形与y轴平行的边为长边的情况，需要满足,此时在位置的线段可以和它构成个的矩形,以此类推，每向右一格，能构成矩形的数量就减1。

也就是说，我们确定了每个矩形的左边这条边之后，我们可以知道右边的某一根线段可以作为右边的边构成的矩形的个数，于是我们可以用差分解决。

用两个数组，一个代表这个点可以构成的矩形的变化量，一个是在这个点之后需要减少的矩形数量的变化量。

如果这个点确定有线段，则往最终答案上加上目前能构成的矩形的数量，最后输出即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define testin freopen("testin1.txt", "r", stdin)
#define testout freopen("testout1.txt", "w", stdout)
#define pb push_back
#define NO cout<<"No"<<endl
#define YES cout<<"Yes"<<endl
#define MAYBE cout<<"MAYBE"<<endl
#define endl '\n'
#define ALL(x) x.begin(),x.end()
#define INS(x)inserter(x,x.begin())
using namespace std;
const ll MAXN = 400010;
const ll INF = 0x3f3f3f3f;
const ll mod = 998244353;
ll x[MAXN];
ll cnt[MAXN];//差分数组
ll pos[MAXN];、、
ll plu[MAXN];
void solve() {
	ll n, m, k;
	cin >> n >> m >> k;
	for (int i = 0; i < MAXN; i++) {
		cnt[i] = 0;
		pos[i] = 0;
		plu[i] = 0;
	}
	for (int i = 0; i < n; i++) {
		cin >> x[i];
		pos[x[i]] = 1;
		cnt[x[i] + 1 + k]++;
		cnt[x[i] + m + k + 1]--;
		plu[x[i] + 1 + k] += m;
		if (m - k >= 1) {
			cnt[x[i] + 1]++;
			cnt[x[i] + m - k + 1]--;
			plu[x[i] + 1] += m - k;
		}
	}
	ll ans = 0, minu = 0;
	ll tmp = 0;
	for (int i = 0; i < MAXN; i++) {
		tmp += plu[i];
		minu += cnt[i];
		if (pos[i] == 1)ans += tmp;
		tmp -= minu;
	}
	cout << ans << endl;
	return;
}
int main() {
	//testin;
	//freopen("case1out.txt", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	ll t = 1;
	//cin >> t;
	//scanf("%lld", &t);
	while (t--) {
		solve();
	}
}