传送门
Luogu
解题思路
当只有第三类操作时，我们显然先进行val较大的操作，这是显然的。
那么就考虑把所有的操作都转变为第三类操作。
第一类操作，显然很容易变为第二类操作：单点维护最大的最终结果，然后改为加法就好了。
问题在于第二类操作如何转换。
其实也是贪心，我们对于同一个位置的第二类操作，优先进行val值较大的，把较小的分母留给较大的分子使得答案最优。
细节注意事项
- 实现起来有点繁琐。
参考代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#define rg register
using namespace std;
template < typename T > inline void read(T& s) {
s = 0; int f = 0; char c = getchar();
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();
s = f ? -s : s;
}
typedef long long LL;
const int _ = 100010;
int n, m, k, n1, n2, n3, x[_];
struct node{ int t, id, x; LL fz, fm; }t1[_], t2[_], t3[_], ans[_];
inline bool cmp1(const node& a, const node& b) { return a.x == b.x ? a.fz < b.fz : a.x < b.x; }
inline bool cmp2(const node& a, const node& b) { return a.x == b.x ? a.fz > b.fz : a.x < b.x; }
inline bool cmp3(const node& a, const node& b) { return a.fz * b.fm > b.fz * a.fm; }
inline bool cmp4(const node& a, const node& b) { return a.t < b.t; }
int main() {
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
#endif
read(n), read(m), read(k);
for (rg int i = 1; i <= n; ++i) read(x[i]);
for (rg int t, xi, val, i = 1; i <= m; ++i) {
read(t), read(xi), read(val);
if (t == 1 && val > x[xi]) t1[++n1] = (node) { t, i, xi, val, 1 };
if (t == 2) t2[++n2] = (node) { t, i, xi, val, 1 };
if (t == 3) t3[++n3] = (node) { t, i, xi, val, 1 };
}
sort(t1 + 1, t1 + n1 + 1, cmp1);
int qwq = 0;
for (rg int i = 1; i <= n1; ++i)
if (t1[i].x != t1[i + 1].x) t1[++qwq] = t1[i];
n1 = qwq;
for (rg int i = 1; i <= n1; ++i)
t1[i].fz -= x[t1[i].x], t2[++n2] = t1[i];
sort(t2 + 1, t2 + n2 + 1, cmp2);
LL sum = 0;
for (rg int i = 1; i <= n2; ++i) {
if (t2[i].x != t2[i - 1].x) sum = x[t2[i].x];
t2[i].fm = sum, sum += t2[i].fz;
}
for (rg int i = 1; i <= n3; ++i) --t3[i].fz;
for (rg int i = 1; i <= n2; ++i) t3[++n3] = t2[i];
sort(t3 + 1, t3 + n3 + 1, cmp3);
int cnt = min(n3, k);
for (rg int i = 1; i <= cnt; ++i) ans[i] = t3[i];
printf("%d
", cnt);
sort(ans + 1, ans + cnt + 1, cmp4);
for (rg int i = 1; i <= cnt; ++i)
printf("%d%c", ans[i].id, "
"[i == cnt]);
return 0;
}
完结撒花 (qwq)