P2120 [ZJOI2007] 仓库建设
代码里面的 \(costSum[i]\) 表示 \(i+1\) 到 \(N\) 范围内的所有仓库的零件运到最后一个仓库的花费。
\(partSum[i]\) 表示从 \(1\) 到 \(i\) 范围内的所有仓库零件个数总和。
然后转移就行了。代码昨天放了，今天就不放辣。
P2900 [USACO08MAR] Land Acquisition G
我们会发现有一个是 \(w[j] * y[i]\) 两个一个单调递增另一个单调递减我们这时 \(-(-w[i])*y[i]\) 就行了。
因为这道题重修了一遍斜率优化，以后得用一次函数的截距做题了QAQ，记得把 \(x\) 在坐标轴上的位置变成单调递增的，这样好理解。
但是用一次函数写斜率优化真香QAQ。
知乎
#include <bits/stdc++.h>
typedef long long ll;
int N;
std::pair<ll, ll> value[51000], ttt[51000];
std::stack<int> stack;
ll dp[51000];
class Monotonic_Queue {
public:
int l, r;
std::pair<ll, ll> number[51000];
int id[51000];
Monotonic_Queue() {
l = 1, r = 0;
}
long double Slope(std::pair<ll, ll> &a, std::pair<ll, ll> &b) {
return 1.0 * (b.second - a.second) / (1.0 * (b.first - a.first));
}
void emplace(ll x, ll y, int ID) {
std::pair<ll, ll> temp = std::make_pair(x, y);
while (l + 1 <= r && Slope(number[r - 1], number[r]) >= Slope(number[r], temp))
-- r;
id[++ r] = ID;
number[r] = temp;
}
void pop(long double k) {
while (l + 1 <= r && k >= Slope(number[l], number[l + 1]))
++ l;
}
int front_id() {
return id[l];
}
}queue;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> N;
for (int i = 1; i <= N; ++ i) {
std::cin >> ttt[i].first >> ttt[i].second;
dp[i] = 3e18;
}
std::sort(ttt + 1, ttt + 1 + N);
for (int i = 1; i <= N; ++ i) {
while (stack.size() && ttt[stack.top()].second <= ttt[i].second)
stack.pop();
stack.emplace(i);
}
N = stack.size();
for (int i = stack.size(); i >= 1; -- i) {
value[i] = ttt[stack.top()];
stack.pop();
}
queue.emplace(-value[1].second, 0, 0);
for (int i = 1; i <= N; ++ i) {
long double k = value[i].first;
queue.pop(k);
int id = queue.front_id();
dp[i] = dp[id] + value[id + 1].second * value[i].first;
queue.emplace(-value[i + 1].second, dp[i], i);
}
std::cout << dp[N] << '\n';
return 0;
}
P3810 【模板】三维偏序（陌上花开）
陌上花开，可缓缓归矣。
具体来说就是先以第一关键字排一次序，然后在二分里递归的排第二关键字和第三关键字并排序。
抖音
#include <bits/stdc++.h>
class Array {
public:
int first, second, third;
int id;
bool operator <(const Array &b) const {
if (first != b.first)
return first > b.first;
if (second != b.second)
return second > b.second;
return third > b.third;
}
}array[110000], temp, record[110000];
bool CompareFirst(const Array &a, const Array &b) {
if (a.first != b.first)
return a.first < b.first;
if (a.second != b.second)
return a.second < b.second;
return a.third < b.third;
}
bool CompareSecond(const Array &a, const Array &b) {
if (a.second != b.second)
return a.second < b.second;
return a.third < b.third;
}
int N, K, tempN;
class Binary_Indexed_Tree {
#define lowbit(x) (x & (-x))
public:
int number[210000];
void Add(int position, int val) {
while (position <= 200000) {
number[position] += val;
position += lowbit(position);
}
}
int Query(int position) {
int result = 0;
while (position) {
result += number[position];
position -= lowbit(position);
}
return result;
}
}tree;
int len[110000];
std::map<Array, int> map;
void CDQ(int l, int r) {
if (l == r)
return;
int mid = (l + r) >> 1;
CDQ(l, mid);
CDQ(mid + 1, r);
int i = l, j = mid + 1;
while (i <= mid && j <= r) {
if (array[i].second <= array[j].second) {
tree.Add(array[i].third, map[array[i]]);
i ++;
}
else {
len[array[j].id] += tree.Query(array[j].third);
j ++;
}
}
while (j <= r) {
len[array[j].id] += tree.Query(array[j].third);
j ++;
}
for (int pos = l; pos <= i - 1; ++ pos)
tree.Add(array[pos].third, -map[array[pos]]);
std::inplace_merge(array + l, array + mid + 1, array + r + 1, CompareSecond);
}
int answer[110000];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> tempN >> K;
for (int i = 1; i <= tempN; ++ i) {
std::cin >> temp.first >> temp.second >> temp.third;
if (!map[temp])
array[++ N] = temp;
map[temp] ++;
}
std::stable_sort(array + 1, array + 1 + N, CompareFirst);
for (int i = 1; i <= N; ++ i) {
array[i].id = i;
record[i] = array[i];
}
CDQ(1, N);
for (int i = 1; i <= N; ++ i) {
answer[len[i] + map[record[i]] - 1] += map[record[i]];
}
for (int i = 0; i < tempN; ++ i)
std::cout << answer[i] << '\n';
return 0;
}
/*
4 200000
3 3 1
2 2 1
2 3 3
2 2 1
*/