# 2 solutions

• @ 2023-11-19 21:39:56
#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef struct Function_tag {
ll k;
ll b;

Function_tag(){}

Function_tag(ll k_, ll b_){
k = k_;
b = b_;
}

inline ull calc(int x){
return (ull)k * x + b;
}
} Function;

int cnt[300007], a[300007], b[300007], c[300007], d[300007], e[300007];
ll l[300007];
Function f[300007], g[300007], h[300007];

Function operator +(const Function a, const Function b){
return Function(a.k + b.k, a.b + b.b);
}

Function operator +=(Function &a, const Function b){
return a = a + b;
}

Function operator -(const Function a, const Function b){
return Function(a.k - b.k, a.b - b.b);
}

Function operator -=(Function &a, const Function b){
return a = a - b;
}

int ans = 0;
char ch = getchar();
while (ch < '0' || ch > '9'){
ch = getchar();
}
while (ch >= '0' && ch <= '9'){
ans = ans * 10 + (ch ^ 48);
ch = getchar();
}
return ans;
}

int main(){
l[++x] = 1;
for (register int i = 1; i <= n; i++){
cnt[p]++;
}
for (register int i = 1; i <= m; i++){
}
for (register int i = 1; i <= m; i++){
}
for (register int i = 1; i <= m; i++){
}
for (register int i = 1; i <= m; i++){
}
for (register int i = 1; i <= m; i++){
}
for (register int i = 1; i <= m; i++){
if (cnt[i] > 0){
ll pos;
f[i].k = d[i];
f[i].b = (ll)a[i] * cnt[i];
g[i].k = e[i];
g[i].b = b[i] + (ll)c[i] * cnt[i];
pos = (f[i].b - g[i].b) / (g[i].k - f[i].k) + 1;
if (pos >= 1) l[++x] = pos;
}
}
sort(l + 1, l + x + 1);
x = unique(l + 1, l + x + 1) - l - 1;
for (register int i = 1; i <= m; i++){
if (cnt[i] > 0){
ll pos1 = (f[i].b - g[i].b) / (g[i].k - f[i].k) + 1;
if (pos1 <= 0){
h[1] += f[i];
} else {
int pos2 = lower_bound(l + 1, l + x + 1, pos1) - l;
h[1] += g[i];
h[pos2] -= g[i];
h[pos2] += f[i];
}
}
}
for (register int i = 1; i <= x; i++){
h[i] += h[i - 1];
}
for (register int i = 1; i <= q; i++){
cout << h[upper_bound(l + 1, l + x + 1, k) - l - 1].calc(k) << endl;
}
return 0;
}


• @ 2023-6-10 22:51:24

说句闲话，这个 idea 是我在中考前背政治时想到的。

首先注意到每个知识点独立，则我们分别算出每个知识点对应的答案后加起来即可。下面我们考虑某个知识点 $i$ 的情况。

$cnt_i$ 表示 $a_j = i$$j$ 数量，则有：

• 不标注：$a_i cnt_i + k d_i$
• 标注：$b_i + c_i cnt_i + k e_i$

注意 $cnt_i = 0$ 者的贡献不会计入答案。

于是答案为 $\displaystyle\sum_{i = 1}^m [cnt_i > 0] \min(a_i cnt_i + k d_i, b_i + c_i cnt_i + k e_i)$。但直接计算是 $O(nq)$ 的，显然不能通过。

注意到每个 $i$ 对应的贡献为两个关于 $k$ 的一次函数，考虑找出一个分界点 $x_0$ 使得 $\forall k \leq x_0$$\min$ 会取到标注的情况且 $\forall k > x_0$$\min$ 会取到不标注的情况。

对所有分界点离散化后差分求出每个离散化区间内的答案的一次项和常数项，每次询问时代入回答即可。时间复杂度为 $O(n + (m + q) \log m)$

记得开 unsigned long long，不然会 WA on #10。

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef struct Function_tag {
ll k;
ll b;

Function_tag(){}

Function_tag(ll k_, ll b_){
k = k_;
b = b_;
}

inline ull calc(int x){
return (ull)k * x + b;
}
} Function;

int cnt[300007], a[300007], b[300007], c[300007], d[300007], e[300007];
ll l[300007];
Function f[300007], g[300007], h[300007];

Function operator +(const Function a, const Function b){
return Function(a.k + b.k, a.b + b.b);
}

Function operator +=(Function &a, const Function b){
return a = a + b;
}

Function operator -(const Function a, const Function b){
return Function(a.k - b.k, a.b - b.b);
}

Function operator -=(Function &a, const Function b){
return a = a - b;
}

int ans = 0;
char ch = getchar();
while (ch < '0' || ch > '9'){
ch = getchar();
}
while (ch >= '0' && ch <= '9'){
ans = ans * 10 + (ch ^ 48);
ch = getchar();
}
return ans;
}

int main(){
l[++x] = 1;
for (register int i = 1; i <= n; i++){
cnt[p]++;
}
for (register int i = 1; i <= m; i++){
}
for (register int i = 1; i <= m; i++){
}
for (register int i = 1; i <= m; i++){
}
for (register int i = 1; i <= m; i++){
}
for (register int i = 1; i <= m; i++){
}
for (register int i = 1; i <= m; i++){
if (cnt[i] > 0){
ll pos;
f[i].k = d[i];
f[i].b = (ll)a[i] * cnt[i];
g[i].k = e[i];
g[i].b = b[i] + (ll)c[i] * cnt[i];
pos = (f[i].b - g[i].b) / (g[i].k - f[i].k) + 1;
if (pos >= 1) l[++x] = pos;
}
}
sort(l + 1, l + x + 1);
x = unique(l + 1, l + x + 1) - l - 1;
for (register int i = 1; i <= m; i++){
if (cnt[i] > 0){
ll pos1 = (f[i].b - g[i].b) / (g[i].k - f[i].k) + 1;
if (pos1 <= 0){
h[1] += f[i];
} else {
int pos2 = lower_bound(l + 1, l + x + 1, pos1) - l;
h[1] += g[i];
h[pos2] -= g[i];
h[pos2] += f[i];
}
}
}
for (register int i = 1; i <= x; i++){
h[i] += h[i - 1];
}
for (register int i = 1; i <= q; i++){
cout << h[upper_bound(l + 1, l + x + 1, k) - l - 1].calc(k) << endl;
}
return 0;
}

• 1

# Information

ID
279
Time
1000ms
Memory
512MiB
Difficulty
7
Tags
(None)
# Submissions
44
Accepted
11