codeforces #413 C. Fountains （BIT维护前缀max）
题意：有２种货币，分别为C和D.给出n种资源的代价和美丽度，每种资源只能用其中一种资源购买。现在拥有货币C的数量是c,拥有货币D的数量是d.然后恰好买２个资源，问最大美丽度，不能的话输出０．
思路：首先显然三种情况。。。CC，CD,DD.
CD直接扫一遍。。重点是CC和DD
一开始思路错掉了。。全程写two pointer wa4…一直调。。
最后恍然大悟。。发现two pointer非常错啊。。。
其实正解也很简单？
先去跑步了orz
只要想办法维护每个代价的最大美丽度就好了(更准确得说，是维护小于等于某代价的最大美丽度)
直接BIT搞。维护一个前缀max…好像很稳啊？
不过我竟然对于BIT能维护前缀max吃了一惊？
以往都是用线段树来做这个操作的…想想大概是。。我把BIT的函数起名叫"Sum"的锅。。。
看起来就只能求Sum。。。。233333
1/* ***********************************************
2Author :111qqz
3Created Time :2017年05月12日 星期五 20时20分57秒
4File Name :code/codeforces/413/CC.cpp
5 ************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=1E5+7;
35int n,c,d;
36int t[N] ; //for BIT
37vector<pair<int,int> >v[2];
38//总的思路是，维护每个代价(或者小于该代价）所对的美丽度的最大值
39//用bit维护一个前缀max
40//
41//
42
43int lowbit( int x)
44{
45 return x&(-x);
46}
47void update( int x,int delta)
48{
49 for ( int i = x ; i < N ; i+=lowbit(i)) t[i] = max(t[i],delta);
50}
51int query( int x)
52{
53 int ret = 0 ;
54 for ( int i = x ; i>=1 ; i-=lowbit(i))
55 ret = max(ret,t[i]);
56 return ret;
57}
58
59int main()
60{
61#ifndef ONLINE_JUDGE
62 freopen("code/in.txt","r",stdin);
63#endif
64 scanf("%d%d%d",&n,&c,&d);
65 for ( int i = 1 ; i <= n ; i++)
66 {
67 int bea,cost;
68 char opt[3];
69 scanf("%d%d",&bea,&cost);
70 scanf("%s",opt);
71 int id = opt[0]-'C';
72 v[id].PB(MP(cost,bea));
73 }
74
75 sort(v[0].begin(),v[0].end());
76 sort(v[1].begin(),v[1].end()); //按照cost 排序
77
78 //CD
79 int ans1,ans2;
80 ans1=ans2=0;
81 int siz0 = v[0].size();
82 for ( int i = 0 ; i < siz0 ; i++)
83 {
84 if (v[0][i].fst>c) break;
85 ans1 = max(ans1,v[0][i].sec);
86 }
87 int siz1 = v[1].size();
88 for ( int i = 0 ; i < siz1 ; i++)
89 {
90 if (v[1][i].fst>d) break;
91 ans2 = max(ans2,v[1][i].sec);
92 }
93 int ans = 0 ;
94 if (ans1&&ans2) ans = ans1+ans2;
95
96
97 //CC
98 ms(t,0);
99 for ( int i = 0 ; i < siz0 ; i++)
100 {
101 if (v[0][i].fst>c) break;
102 if (i)
103 {
104 int tmp = query(c-v[0][i].fst); //我们不关心另一个取哪个，
105 //只关心剩下的c-v[0][i].fst的coins能取到的最大美丽度。。bit维护一下。。。
106 if (tmp) ans = max(ans,tmp+v[0][i].sec) ; //只有bit的返回值大于0时，才表示可以取。。
107 }
108 update(v[0][i].fst,v[0][i].sec);
109 }
110
111 //DD
112 ms(t,0);
113 for ( int i = 0 ; i < siz1 ; i++ )
114 {
115 if (v[1][i].fst>d) break;
116 if (i)
117 {
118 int tmp = query(d-v[1][i].fst);
119 if (tmp) ans = max(ans,tmp+v[1][i].sec);
120 }
121 update(v[1][i].fst,v[1][i].sec);
122 }
123 printf("%d\n",ans);
124#ifndef ONLINE_JUDGE
125 fclose(stdin);
126#endif
127 return 0;
128}