ICPC 2017 Latin American Regional F（树状数组）

[题目链接](https://vjudge.net/problem/Gym-101889F) ------------ 树状数组维护最大值 ------------ ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const int M=1e5+5; int n,m,tot; ll c[M],ans; vector<int> vt; map<pair<int,int>,int> mp; struct ask { int b,f;ll d; bool operator <(const ask &a)const { if(b==a.b)return f>a.f; return b<a.b; } }q[M]; inline int getid(int x){return lower_bound(vt.begin(),vt.end(),x)-vt.begin()+1;} inline int lowbit(int x){return x&-x;} void upd(int pos,ll x){for(;pos<=m;pos+=lowbit(pos))c[pos]=max(c[pos],x);} ll que(int pos){ll res=0;for(;pos;pos-=lowbit(pos))res=max(res,c[pos]);return res;} int haxi(pair<int,int> p){if(!mp[p])mp[p]=++tot;return mp[p];} int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { int x,y;ll z;scanf("%d%d%lld",&x,&y,&z); vt.push_back(y); int t=haxi(pair<int,int>(x,y)); q[t].b=x;q[t].f=y;q[t].d+=z; } sort(vt.begin(),vt.end()); vt.erase(unique(vt.begin(),vt.end()),vt.end()); m=vt.size(); sort(q+1,q+1+tot); for(int i=1;i<=tot;i++) { int pos=getid(q[i].f); ll k=que(pos-1)+q[i].d; upd(pos,k); ans=max(ans,k); } printf("%lld\n",ans); return 0; } ```