题目
题目描述
有 \(A\)、\(B\) 两类物品。
paper 打算每类各选 \(k\) 个（\(k\) 可自由决定，可取 \(0\)）一起捐出。捐赠的总贡献为所选物品的价值总和。
初始时 paper 没有物品，但是 paper 可以通过一些操作改变物品的数量，一共进行了 \(m\) 次操作，分为三种类型：
- 增加或减少若干个价值相同的 \(A\) 类物品。
- 增加或减少若干个价值相同的 \(B\) 类物品。
- 询问当前能获得的最大捐赠总贡献。
请你帮助 paper 处理这些操作。
保证在减少操作中物品个数一定充足。
输入格式
第一行有一个整数，表示操作的总数 \(m\)。
接下来 \(m\) 行，每行表示一次操作，首先有一个整数 \(op\)。
- 若 \(op\) 为 \(1\)，则后面有两个整数 \(x, y\)。若 \(y \ge 0\) 则表示增加 \(y\) 个价值为 \(x\) 的 \(A\) 类物品，否则表示减少 \(-y\) 个。
- 若 \(op\) 为 \(2\)，则后面有两个整数 \(x, y\)。若 \(y \ge 0\) 则表示增加 \(y\) 个价值为 \(x\) 的 \(B\) 类物品，否则表示减少 \(-y\) 个。
- 若 \(op\) 为 \(3\)，代表询问目前最大可能贡献。
输出格式
对于每一个 \(op = 3\)，输出此时的最大贡献。
输入输出样例 #1
输入 #1
5
1 2 3
2 -1 3
3
1 2 -2
3
输出 #1
3
1
说明/提示
本题采用捆绑测试。
- Subtask 0（10 points）：\(m \le 200\)。
- Subtask 1（30 points）：\(m \le 5000\)。
- Subtask 2（20 points）：\(y = 1\)。
- Subtask 3（40 points）：无特殊限制。
对于所有测试数据，\(1\le m\le10^6,-10^6 \le x,y\le 10^6\)。
思路链
观察题目->看出我对于A和B类物品一定要满足能选大的就选大的->然后又发现他这个选k个的函数是一个凸的单峰最大值函数->考虑三分->三分TLE->考虑这个凸的单峰最大值函数会在第一个A类物品加B类物品为负数时开始降低->二分最后一个和不为负数的位置->AC。
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
char *SSSS, *TTTT;
char pori[1 << 22];
#define gc() (SSSS == TTTT && (TTTT = (SSSS = pori) + fread(pori, 1, 1 << 22, stdin)), SSSS == TTTT ? EOF : *SSSS++)
using namespace std;
inline ll read()
{ll x = 0, f = 1;char ch = gc();while (ch < '0' || ch > '9'){if (ch == '-'){f = -1;}ch = gc();}while (ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + ch - '0';ch = gc();}return x * f;
}
struct node
{int lc, rc;ll tot, cnt;
} tr1[2000005], tr2[2000005];
int tot1 = 0, tot2 = 0;
inline void pushup1(int p)
{tr1[p].tot = tr1[tr1[p].lc].tot + tr1[tr1[p].rc].tot;tr1[p].cnt = tr1[tr1[p].lc].cnt + tr1[tr1[p].rc].cnt;
}
inline void pushup2(int p)
{tr2[p].tot = tr2[tr2[p].lc].tot + tr2[tr2[p].rc].tot;tr2[p].cnt = tr2[tr2[p].lc].cnt + tr2[tr2[p].rc].cnt;
}
void add1(int &rt, int l, int r, ll x, ll d)
{if (!rt){rt = ++tot1;}if (l == r){tr1[rt].tot += d * x;tr1[rt].cnt += d;return;}ll mid = (l + r) >> 1;if (x <= mid){add1(tr1[rt].lc, l, mid, x, d);}else{add1(tr1[rt].rc, mid + 1, r, x, d);}pushup1(rt);
}
void add2(int &rt, int l, int r, ll x, ll d)
{if (!rt){rt = ++tot2;}if (l == r){tr2[rt].tot += d * x;tr2[rt].cnt += d;return;}int mid = (l + r) >> 1;if (x <= mid){add2(tr2[rt].lc, l, mid, x, d);}else{add2(tr2[rt].rc, mid + 1, r, x, d);}pushup2(rt);
}
ll qry1(int rt, int l, int r, ll k)
{if (!k){return 0;}if (!rt){return 0;}// cout << l << " " << r << "\n";if (l == r){return l;}int mid = (l + r) >> 1;// cout << rt << " " << tr1[rt].cnt << " " << tr1[tr1[rt].rc].cnt << " " << k << "\n";if (tr1[tr1[rt].rc].cnt >= k){return qry1(tr1[rt].rc, mid + 1, r, k);}else{return qry1(tr1[rt].lc, l, mid, k - tr1[tr1[rt].rc].cnt);}
}
ll qry2(int rt, int l, int r, ll k)
{if (!k){return 0;}if (!rt){return 0;}if (l == r){return l;}int mid = (l + r) >> 1;if (tr2[tr2[rt].rc].cnt >= k){return qry2(tr2[rt].rc, mid + 1, r, k);}else{return qry2(tr2[rt].lc, l, mid, k - tr2[tr2[rt].rc].cnt);}
}
ll query1(int rt, int l, int r, ll k)
{if (!k){return 0;}if (!rt){return 0;}if (tr1[rt].cnt == k){return tr1[rt].tot;}// cout << l << " " << r << "\n";if (l == r){return l * k;}int mid = (l + r) >> 1;// cout << rt << " " << tr1[rt].cnt << " " << tr1[tr1[rt].rc].cnt << " " << k << "\n";if (tr1[tr1[rt].rc].cnt >= k){return query1(tr1[rt].rc, mid + 1, r, k);}else{return query1(tr1[rt].lc, l, mid, k - tr1[tr1[rt].rc].cnt) + tr1[tr1[rt].rc].tot;}
}
ll query2(int rt, int l, int r, ll k)
{if (!k){return 0;}if (!rt){return 0;}if (tr2[rt].cnt == k){return tr2[rt].tot;}if (l == r){return l * k;}int mid = (l + r) >> 1;if (tr2[tr2[rt].rc].cnt >= k){return query2(tr2[rt].rc, mid + 1, r, k);}else{return query2(tr2[rt].lc, l, mid, k - tr2[tr2[rt].rc].cnt) + tr2[tr2[rt].rc].tot;}
}
int main()
{// freopen("ex_donate2.in","r",stdin);// freopen("donate.out","w",stdout);ll _ = read();ll lc = 0, rc = 0;int rt1 = 0, rt2 = 0;const int L = -1000000, R = 1000000;while (_--){int op = read();if (op == 1){int x = read(), y = read();lc += y;add1(rt1, L, R, x, y);// cout<<"**"<<tr1[rt1].tot<<"\n";}else if (op == 2){int x = read(), y = read();rc += y;add2(rt2, L, R, x, y);// cout << "***" << tr2[rt2].tot << "\n";}else{ll mn = min(lc, rc);ll l = 0, r = mn, ans = 0;// cout << mn << "\n";// cout << query2(rt2,-1000000,1000000, 2) << "\n";while (l <= r){// cout<<l<<" "<<r<<"\n";ll mid = (l + r) >> 1;if (qry1(rt1, L, R, mid) + qry2(rt2, L, R, mid) < 0){r = mid - 1;}else{l = mid + 1;ans = mid;}}// assert(l <= r);// cout << l << " " << r << "\n";// ll ans = 0;// ans = max(ans, query1(rt1, L, R, l) + query2(rt2, L, R, l));// ans = max(ans, query1(rt1, L, R, r) + query2(rt2, L, R, r));printf("%lld\n", query1(rt1, L, R, ans) + query2(rt2, L, R, ans));}}// cout<<tot1<<" "<<tot2<<"\n";return 0;
}
/*
5
1 -655 849
2 -604 508
2 861 599
2 720 186
3
*/