Points Division(线段树+DP)2019牛客暑期多校训练营(第一场)

摘要:
https://blog.csdn.net/qq_41194925/article/details/97079075需要注意的一点是,对于枚举点,我们计算B集,因此dp=max(1~i)+bi,必须是bi。

题意: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
",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 }

免责声明:文章转载自《Points Division(线段树+DP)2019牛客暑期多校训练营(第一场)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇线性基求交(2019牛客国庆集训派对day4)Resistors in Parallel(找规律+大数)下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

动态规划

53. 最大子序和 难度简单1716 给定一个整数数组nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释:连续子数组[4,-1,2,1] 的和最大,为6。 进阶: 如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分...

[线段树]HDU-1754板子题入门ver

HDU-1754 线段树数组请开到四倍 众所周知数组开小会导致re tle wa等一系列问题orz 板子就是板子,数组从零开始或是从一开始都没什么问题,就是2*root+1还是2*root+2的问题。query(q)里的范围不要搞反了,是询问范围包括当前节点的范围。 总之线段树是入门了(吧 解析board:线段树是一棵叶子节点为具体数据(1st,2n...

P3372 【模板】线段树 1

初识懒标记。。。 #include<iostream> #include<cstdio> using namespace std; #define LL long long const int N = 100010; struct Node{ int l, r; LL sum; LL add; // l...

P3588 【[POI2015]PUS】(线段树优化建边)

P3588 【[POI2015]PUS】 终于有个能让我一遍过的题了,写篇题解纪念一下给定长度为n的序列和其中部分已知的数,还有m个大小关系:区间([l,r])中,有k个给定的数比剩下的(r-l+1-k)个数都大求是否有解,有解给出任意一个合法方案按大小关系,从大的数向小的数连边直接建图肯定不行,考虑用线段树优化,如果你不会线段树优化建边,点这里对于每个([...

2014 summer 知识点总结1之线段树

HDU 1166 【题意】: n个阵营一字排开,每个初始有a[i]个人。现有两种操作: Q a b 查询[a,b]之间总人数并输出 A/S a b 在a号位添加/删除b个人 【分析】:最基本的单点更新和区间查询,维护节点信息sum[o] 【代码】: 1 #include <iostream> 2 #include <string.h&g...

HDU 5696 ——区间的价值——————【线段树、快排思想】

区间的价值 Time Limit: 10000/5000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 662Accepted Submission(s): 329 Problem Description 我们定义“区间的价值”为一段区间的最大值*最...