题目传送门
题目大意：
从 \(n\) 个喷泉中选择两个，使两座喷泉美丽值总和最大且消耗金币和钻石分别不超过 \(c\) 和 \(d\)，求最大美丽值。
题目分析：
先钦定选一个喷泉，那么设剩余的金币及钻石数为 \(c'\) 和 \(d'\)，那么选的第二个喷泉要么是要花费金币且花费数不大于 \(c'\)，要么是花费钻石且花费数不大于 \(d'\)，并且使美丽值最大。这种问题可以开两个树状数组来实现。在插入时根据花费类型插入第一个或第二个树状数组中，查询时取两个树状数组返回结果的 \(\max\)，即为答案。
但这里有一个棘手的问题：选定的喷泉不能被再次选择。所以我们要对插入和查询操作进行修改，每个结点要储存前二大的数及编号，这样在查询时，如果最大的数的编号正好等于第一次选择喷泉的编号，则对储存的第二个数取 \(\max\)，问题就能完美解决了。
细节：由于不能只选择一个喷泉，树状数组初始最大值和次大值都要设成极小值。答案初始值为 \(0\)。
时间复杂度 \(\mathcal{O}(n \log n)\)。
Code:
#include <iostream>
#include <algorithm>
#include <vector>
#define lowbit(k) k&(-k)
#define int long long
using namespace std;
int t,n,c,d,A,B;
int tr[200005][2],tr2[200005][2],id[200005][2],id2[200005][2];
struct node
{int x,y,id;char z;
}a[300005];
void add(int opt,int x,int k,int lol)
{while(x <= 200000){if(opt == 1)//插入第一个树状数组{//tr x,0表示最大值，tr x,1表示次大值if(k >= tr[x][0])tr[x][1] = tr[x][0],id[x][1] = id[x][0],tr[x][0] = k,id[x][0] = lol;else if(k > tr[x][1])tr[x][1] = k,id[x][1] = lol;}else //插入第二个树状数组{if(k >= tr2[x][0])tr2[x][1] = tr2[x][0],id2[x][1] = id2[x][0],tr2[x][0] = k,id2[x][0] = lol;else if(k > tr2[x][1])tr2[x][1] = k,id2[x][1] = lol;}x += lowbit(x);}
}
int query(int opt,int x,int ban)//ban:第一个选择喷泉编号
{int su = -1e9;while(x){if(opt == 1){if(id[x][0] == ban)su = max(su,tr[x][1]);else su = max(su,tr[x][0]);}else{if(id2[x][0] == ban)su = max(su,tr2[x][1]);else su = max(su,tr2[x][0]);}x -= lowbit(x); }return su;
}
signed main()
{cin >> n >> c >> d;int ans = 0;for(int i = 1;i <= 200000;i ++)tr[i][0] = tr[i][1] = tr2[i][0] = tr2[i][1] = -1e9;for(int i = 1;i <= n;i ++){cin >> a[i].x >> a[i].y >> a[i].z,a[i].id = i;swap(a[i].x,a[i].y);//与输入不同，这里代码ai.x表示价格，ai.y表示美丽值if(a[i].z == 'C')add(1,a[i].x,a[i].y,i);else add(2,a[i].x,a[i].y,i);}for(int i = 1;i <= n;i ++){if(a[i].z == 'C' && a[i].x > c)continue ;if(a[i].z == 'D' && a[i].x > d)continue ;if(a[i].z == 'C')c -= a[i].x;else d -= a[i].x;ans = max(ans,a[i].y + max(query(1,c,a[i].id),query(2,d,a[i].id)));if(a[i].z == 'C')c += a[i].x;else d += a[i].x;}cout << ans;
}