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
/* ***********************************************
Author :111qqz
Created Time :2017年05月12日 星期五 20时20分57秒
File Name :code/codeforces/413/CC.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E5+7;
7int n,c,d;
8int t[N] ; //for BIT
9vector<pair<int,int> >v[2];
10//总的思路是，维护每个代价(或者小于该代价）所对的美丽度的最大值
11//用bit维护一个前缀max
12//
13//
1int lowbit( int x)
2{
3 return x&(-x);
4}
5void update( int x,int delta)
6{
7 for ( int i = x ; i < N ; i+=lowbit(i)) t[i] = max(t[i],delta);
8}
9int query( int x)
10{
11 int ret = 0 ;
12 for ( int i = x ; i>=1 ; i-=lowbit(i))
13 ret = max(ret,t[i]);
14 return ret;
15}
1int main()
2{
3#ifndef ONLINE_JUDGE
4 freopen("code/in.txt","r",stdin);
5#endif
6 scanf("%d%d%d",&n,&c,&d);
7 for ( int i = 1 ; i <= n ; i++)
8 {
9 int bea,cost;
10 char opt[3];
11 scanf("%d%d",&bea,&cost);
12 scanf("%s",opt);
13 int id = opt[0]-'C';
14 v[id].PB(MP(cost,bea));
15 }
sort(v[0].begin(),v[0].end());
sort(v[1].begin(),v[1].end()); //按照cost 排序
1 //CD
2 int ans1,ans2;
3 ans1=ans2=0;
4 int siz0 = v[0].size();
5 for ( int i = 0 ; i < siz0 ; i++)
6 {
7 if (v[0][i].fst>c) break;
8 ans1 = max(ans1,v[0][i].sec);
9 }
10 int siz1 = v[1].size();
11 for ( int i = 0 ; i < siz1 ; i++)
12 {
13 if (v[1][i].fst>d) break;
14 ans2 = max(ans2,v[1][i].sec);
15 }
16 int ans = 0 ;
17 if (ans1&&ans2) ans = ans1+ans2;
1 //CC
2 ms(t,0);
3 for ( int i = 0 ; i < siz0 ; i++)
4 {
5 if (v[0][i].fst>c) break;
6 if (i)
7 {
8 int tmp = query(c-v[0][i].fst); //我们不关心另一个取哪个，
9 //只关心剩下的c-v[0][i].fst的coins能取到的最大美丽度。。bit维护一下。。。
10 if (tmp) ans = max(ans,tmp+v[0][i].sec) ; //只有bit的返回值大于0时，才表示可以取。。
11 }
12 update(v[0][i].fst,v[0][i].sec);
13 }
1 //DD
2 ms(t,0);
3 for ( int i = 0 ; i < siz1 ; i++ )
4 {
5 if (v[1][i].fst>d) break;
6 if (i)
7 {
8 int tmp = query(d-v[1][i].fst);
9 if (tmp) ans = max(ans,tmp+v[1][i].sec);
10 }
11 update(v[1][i].fst,v[1][i].sec);
12 }
13 printf("%d\n",ans);
14#ifndef ONLINE_JUDGE
15 fclose(stdin);
16#endif
17 return 0;
18}