题意：https://ac.nowcoder.com/acm/contest/881/I

给你n个平面上的点，每个点有a、b两个权值，现在让你划分成两个区域（要求所有A集合里的点不能在任何B集合里的点的右下方）。

求MAX（Sigma ai+Sigma bi）。

思路：

dp+线段树。

https://blog.csdn.net/qq_41194925/article/details/97079075

就是有一个要注意的地方：对于枚举的点我们算的是B集合所以dp【i】=max（1~i）+bi，这里必须是bi。

  1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0);
  2 #include <cstdio>//sprintf islower isupper
  3 #include <cstdlib>//malloc  exit strcat itoa system("cls")
  4 #include <iostream>//pair
  5 #include <fstream>//freopen("C:\\Users\\13606\\Desktop\\草稿.txt","r",stdin);
  6 #include <bitset>
  7 //#include <map>
  8 //#include<unordered_map>
  9 #include <vector>
 10 #include <stack>
 11 #include <set>
 12 #include <string.h>//strstr substr
 13 #include <string>
 14 #include <time.h>//srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9;
 15 #include <cmath>
 16 #include <deque>
 17 #include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less
 18 #include <vector>//emplace_back
 19 //#include <math.h>
 20 //#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor
 21 #include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)
 22 using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation
 23 //******************
 24 int abss(int a);
 25 int lowbit(int n);
 26 int Del_bit_1(int n);
 27 int maxx(int a,int b);
 28 int minn(int a,int b);
 29 double fabss(double a);
 30 void swapp(int &a,int &b);
 31 clock_t __STRAT,__END;
 32 double __TOTALTIME;
 33 void _MS(){__STRAT=clock();}
 34 void _ME(){__END=clock();__TOTALTIME=(double)(__END-__STRAT)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;}
 35 //***********************
 36 #define rint register int
 37 #define fo(a,b,c) for(rint a=b;a<=c;++a)
 38 #define fr(a,b,c) for(rint a=b;a>=c;--a)
 39 #define mem(a,b) memset(a,b,sizeof(a))
 40 #define pr printf
 41 #define sc scanf
 42 #define ls rt<<1
 43 #define rs rt<<1|1
 44 typedef long long ll;
 45 //#define int ll
 46 const double E=2.718281828;
 47 const double PI=acos(-1.0);
 48 //const ll INF=(1LL<<60);
 49 const int inf=(1<<30);
 50 const double ESP=1e-9;
 51 const int mod=(int)1e9+7;
 52 const int N=(int)1e6+10;
 53 
 54 struct node
 55 {
 56     int x,y,va,vb;
 57     friend bool operator<(node a,node b)
 58     {
 59         if(a.x==b.x)
 60             return a.y>b.y;
 61         return a.x<b.x;
 62     }
 63 }a[N];
 64 int temp[N];
 65 int LS(int n)
 66 {
 67     int m=0;
 68     for(int i=1;i<=n;++i)
 69         temp[++m]=a[i].y;
 70     sort(temp+1,temp+1+m);
 71     m=unique(temp+1,temp+1+m)-temp-1;
 72     for(int i=1;i<=n;++i)
 73         a[i].y=lower_bound(temp+1,temp+1+m,a[i].y)-temp;
 74     return m;
 75 }
 76 
 77 ll add[N<<2],max_[N<<2];
 78 
 79 void up(int rt,int l,int r)
 80 {
 81     max_[rt]=max(max_[rt<<1],max_[rt<<1|1]);
 82 }
 83 
 84 void dn(int rt)
 85 {
 86     if(add[rt]!=0)
 87     {
 88         add[ls]+=add[rt];
 89         add[rs]+=add[rt];
 90         max_[rt<<1]+=add[rt];
 91         max_[rt<<1|1]+=add[rt];
 92         add[rt]=0;
 93     }
 94 }
 95 
 96 void Build(int l,int r,int rt)
 97 {
 98     max_[rt]=0;
 99     add[rt]=0;
100     if(l==r)
101     {
102         return;
103     }
104     int mid=(l+r)>>1;
105 
106     Build(l,mid,rt<<1);
107     Build(mid+1,r,rt<<1|1);
108     up(rt,l,r);
109 }
110 
111 void update_dot(int pos,ll V,int l,int r,int rt)
112 {
113     if(l==r)
114     {
115         max_[rt]=V;
116         return;
117     }
118 
119     int mid=(l+r)>>1;
120     dn(rt);
121     if(pos<=mid)
122         update_dot(pos,V,l,mid,rt<<1);
123     else
124         update_dot(pos,V,mid+1,r,rt<<1|1);
125     up(rt,l,r);
126 }
127 void update_qu(int L,int R,int V,int l,int r,int rt)
128 {
129     if(L>R)return;
130     if(L<=l&&r<=R)
131     {
132         max_[rt]+=V;
133         add[rt]+=V;
134         return;
135     }
136 
137     int mid=(l+r)>>1;
138     dn(rt);
139     if(L<=mid)
140         update_qu(L,R,V,l,mid,rt<<1);
141     if(R>mid)
142         update_qu(L,R,V,mid+1,r,rt<<1|1);
143     up(rt,l,r);
144 }
145 ll Query(int L,int R,int l,int r,int rt)
146 {
147     if(L<=l&&r<=R)    return max_[rt];
148     int mid=(l+r)>>1;
149     ll res=0;
150     dn(rt);
151     if(L<=mid)
152         res=max(res,Query(L,R,l,mid,rt<<1));
153     if(R>mid)
154         res=max(res,Query(L,R,mid+1,r,rt<<1|1));
155     return res;
156 }
157 void check(int pos,int l,int r,int rt)
158 {
159     if(l==r)
160     {
161         cout<<max_[rt]<<' ';
162         return ;
163     }
164     int mid=(l+r)>>1;
165 
166     dn(rt);
167     if(pos<=mid)
168         check(pos,l,mid,rt<<1);
169     else
170         check(pos,mid+1,r,rt<<1|1);
171 }
172 
173 signed main()
174 {
175     int n;
176     while(~sc("%d",&n))
177     {
178         for(int i=1;i<=n;++i)
179         {
180             int q,w,e,r;
181             sc("%d%d%d%d",&q,&w,&e,&r);
182             a[i]={q,w,e,r};
183         }
184         int tot=LS(n);
185         sort(a+1,a+1+n);
186         Build(0,tot,1);
187         for(int i=1;i<=n;++i)
188         {
189         //    a[i].y++;
190             ll max__=Query(0,a[i].y+1,0,tot,1);
191             update_dot(a[i].y,max__+a[i].vb,0,tot,1);
192             update_qu(0,a[i].y-1,a[i].va,0,tot,1);
193             update_qu(a[i].y+1,tot,a[i].vb,0,tot,1);
194     //        for(int j=0;j<=tot;++j)
195     //            check(j,0,tot,1);
196     //        cout<<endl;
197         }
198         pr("%lld\n",max_[1]);
199     }
200     return 0;
201 }
202 
203 /**************************************************************************************/
204 
205 int maxx(int a,int b)
206 {
207     return a>b?a:b;
208 }
209 
210 void swapp(int &a,int &b)
211 {
212     a^=b^=a^=b;
213 }
214 
215 int lowbit(int n)
216 {
217     return n&(-n);
218 }
219 
220 int Del_bit_1(int n)
221 {
222     return n&(n-1);
223 }
224 
225 int abss(int a)
226 {
227     return a>0?a:-a;
228 }
229 
230 double fabss(double a)
231 {
232     return a>0?a:-a;
233 }
234 
235 int minn(int a,int b)
236 {
237     return a<b?a:b;
238 }