Bzoj2149拆迁队:cdq分治 凸包

时间:2022-07-07 08:03:54

国际惯例的题面:
Bzoj2149拆迁队:cdq分治 凸包
我们考虑大力DP。
首先重新定义代价为:1e13*选择数量-(总高度+总补偿)。这样我们只需要一个long long就能维护。
然后重新定义高度为heighti - i,这样我们能选择高度相同的点,同时可以把无论如何也不会被选择的点扔掉(这样他们的高度<0)。
之后就是转移,我们枚举i前面的被选择的点j,我们要满足的东西有:hj<=hi。
考虑我们再次选择一个点会产生怎样的代价,显然最终的答案一定是一个阶梯状的东西,所以我们选择了i之后之后所有点的高度相对于仅选择j都会上升(hi-hj)。
于是我们就可以转移了,fi=max{fj+(hi-hj)*(n-i+1)}(hj<=hi)+cost[i],cost[i]为单点价值减去选i的补偿代价。于是你可以写对拍用的n^2暴力了。
仔细观察这个转移方程,显然是一个可斜率优化的方程,我们可以把hi当成x,把fi当成j,把(n-i+1)当成a,把1当成b,这样最优答案就是ax+by的形式了。
因为hi不满足单调性,所以我们需要set维护凸包
考虑到我们还有hj<=hi的限制,所以需要再套一层cdq分治......
注意:
cdq分治在排序的时候不能只排单一关键字,需要做双关键字排序,否则会导致一些能更新的东西无法更新。
然后发现你这么写并不能AC,因为常数太大......
代码:

Bzoj2149拆迁队:cdq分治 凸包Bzoj2149拆迁队:cdq分治 凸包
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<set>
  6 #include<cmath>
  7 #include<vector>
  8 #define debug cout
  9 typedef long long int lli;
 10 using namespace std;
 11 const int maxn=1e5+1e2;
 12 const lli mul = 1e13+1e10;
 13 
 14 namespace Convex {
 15     int cmp; // 0 compare x , 1 compare slope .
 16     struct Point {
 17         lli x,y;
 18         long double slop;
 19         friend bool operator < (const Point &a,const Point &b) {
 20             if( !cmp ) return a.x != b.x ? a.x < b.x : a.y < b.y;
 21             return a.slop > b.slop;
 22         }
 23         friend Point operator - (const Point &a,const Point &b) {
 24             return (Point){a.x-b.x,a.y-b.y};
 25         }
 26         friend long double operator * (const Point &a,const Point &b) {
 27             return (long double)a.x * b.y - (long double)b.x * a.y;
 28         }
 29         inline lli calc(lli a,lli b) const {
 30             return a * x + b * y;
 31         }
 32     };
 33     set<Point> st;
 34     
 35     inline void Pop_right(set<Point>::iterator nxt,const Point &p) {
 36         set<Point>::iterator lst;
 37         while(1) {
 38             nxt = st.lower_bound(p);
 39             lst = nxt , ++nxt;
 40             if( nxt == st.end() ) return;
 41             if( lst->x == p.x ) {
 42                 if( p.y > lst->y ) st.erase(lst);
 43                 else break;
 44             }
 45             else {
 46                 if( (*lst-p) * (*nxt-*lst) < 0 ) return;
 47                 st.erase(lst);
 48             }
 49         }
 50     }
 51     inline void Pop_left(set<Point>::iterator prv,const Point &p) {
 52         set<Point>::iterator lst;
 53         prv = st.lower_bound(p) , --prv;
 54         if( prv == st.begin() && prv->x == p.x ) return void(st.erase(prv));
 55         while(prv!=st.begin()) {
 56             prv = st.lower_bound(p) , --prv;
 57             lst = prv , --prv;
 58             if( p.x == lst->x ) {
 59                 if( p.y > lst->y ) st.erase(lst);
 60                 else break;
 61                 continue;
 62             }
 63             else {
 64                 if( (*lst-*prv) * (p-*lst) < 0 ) break;
 65                 st.erase(lst);
 66             }
 67         }
 68     }
 69     inline bool fail(const Point &p) {
 70         set<Point>::iterator it = st.lower_bound((Point){p.x,0,0});
 71         if( it != st.end() && it->x == p.x ) {
 72             if( it->y >= p.y ) return 1; // p is useless at all .
 73             else return 0; // p must be on convex .
 74         }
 75         if( it != st.end() && it != st.begin() ) {
 76             set<Point>::iterator prv = it; --prv;
 77             if( ( p - *prv ) * (*it - p ) > 0  ) return 1;
 78         }
 79         return 0;
 80     }
 81     inline void insert(const Point &p) {
 82         cmp = 0;
 83         if( fail(p) ) return;
 84         set<Point>::iterator prv,nxt,lst=st.lower_bound(p);
 85         if(lst!=st.begin()) Pop_left(--lst,p);
 86         lst=st.lower_bound(p);
 87         if(lst!=st.end()) Pop_right(lst,p);
 88         st.insert(p) , lst = st.find(p);
 89         if(lst!=st.begin()) {
 90             prv = lst , --prv;
 91             Point x = *prv;
 92             x.slop = (long double)( p.y - x.y ) / ( p.x - x.x );
 93             st.erase(prv) , st.insert(x);
 94         }
 95         nxt = lst = st.find(p) , ++nxt;
 96         if(nxt!=st.end()) {
 97             Point x = p , n = *nxt;
 98             x.slop = (long double)( n.y - x.y ) / ( n.x - x.x );
 99             st.erase(lst) , st.insert(x);
100         } else {
101             Point x = p;
102             x.slop = -1e18;
103             st.erase(lst) , st.insert(x);
104         }
105     }
106     inline lli query(const lli &k) {
107         cmp = 1;
108         set<Point>::iterator it = st.lower_bound((Point){0,0,(long double)-k}); // it can't be st.end() if st isn't empty .
109         if( it==st.end() ) return 0;
110         lli ret = it->calc(k,1);
111         if( it != st.begin() ) {
112             --it;
113             ret = max( ret , it->calc(k,1) );
114         }
115         ++it; if( ++it!=st.end() ) ret = max( ret , it->calc(k,1) );
116         return ret;
117     }
118     inline void clear() {
119         st.clear() , cmp = 0;
120     }
121 }
122 
123 lli ina[maxn],inb[maxn],f[maxn],cst[maxn],ans,add; // f[id] .
124 bool isl[maxn];
125 int n;
126 
127 int cmp; // 0 compare height , 1 compare id .
128 struct Node {
129     lli hei,id;
130     friend bool operator < (const Node &a,const Node &b) {
131         if( cmp ) return a.id != b.id ? a.id < b.id : a.hei < b.hei;
132         else return a.hei != b.hei ? a.hei < b.hei : a.id < b.id;
133     }
134 }ns[maxn];
135 
136 vector<Node> vec;
137 
138 inline void solve(vector<Node> &vec) {
139     if( vec.size() <= 1 ) {
140         if( vec.size() ) f[vec[0].id] = max( f[vec[0].id] , cst[vec[0].id] );
141         return;
142     }
143     vector<Node> vl,vr;
144     const unsigned mid = vec.size() >> 1;
145     for(unsigned i=0;i<mid;i++) vl.push_back(vec[i]);
146     for(unsigned i=mid;i<vec.size();i++) vr.push_back(vec[i]);
147     solve(vl);
148     for(unsigned i=0;i<vl.size();i++) isl[vl[i].id] = 1;
149     for(unsigned i=0;i<vr.size();i++) isl[vr[i].id] = 0;
150     cmp = 1 , sort(vec.begin(),vec.end()) , Convex::clear();
151     for(unsigned i=0;i<vec.size();i++) {
152         if( isl[vec[i].id] ) {
153             Convex::insert((Convex::Point){vec[i].hei,f[vec[i].id],0});
154         } else {
155             f[vec[i].id] = max( f[vec[i].id] , cst[vec[i].id] + Convex::query(n-vec[i].id+1));
156         }
157     }
158     solve(vr);
159 }
160 
161 int main() {
162     static lli sel,lst;
163     scanf("%d",&n) , add = (lli) n * ( n + 1 ) >> 1;
164     for(int i=1;i<=n;i++) scanf("%lld",ina+i) , ina[i] -= i;
165     for(int i=1;i<=n;i++) {
166         scanf("%lld",inb+i);
167         if( ina[i] >= 0 ) {
168             cst[i] = mul - inb[i] - ina[i] * ( n - i + 1 ) ,
169             vec.push_back((Node){ina[i],i});
170         }
171     }
172     cmp = 0 , sort(vec.begin(),vec.end());
173     solve(vec);
174     for(int i=1;i<=n;i++) ans = max( ans , f[i] );
175     ans -= add;
176     sel = ( ans + mul ) / mul;
177     lst = mul * sel - ans;
178     printf("%lld %lld\n",sel,lst);
179     return 0;
180 }
View Code

另外这个东西其实不用平衡树维护凸包,如果你外层分治位置,内层分治height的话,height就会有序,这样只需要写一个普通凸包就好了......
在BZOJ上只有这样才能AC......//QAQ
代码:

Bzoj2149拆迁队:cdq分治 凸包Bzoj2149拆迁队:cdq分治 凸包
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<vector>
  6 #define debug cout
  7 typedef long long int lli;
  8 typedef long double ldb;
  9 using namespace std;
 10 const int maxn=1e5+1e2;
 11 const lli mul = 1e13 + 1e10;
 12 
 13 
 14 struct Convex {
 15     struct Point {
 16         lli x,y;
 17         friend Point operator - (const Point &a,const Point &b) {
 18             return (Point){a.x-b.x,a.y-b.y};
 19         }
 20         friend ldb operator * (const Point &a,const Point &b) {
 21             return (ldb)a.x*b.y - (ldb)a.y*b.x;
 22         }
 23         friend lli operator ^ (const Point &a,const Point &b) {
 24             return a.x * b.x + a.y * b.y;
 25         }
 26     }ps[maxn];
 27     int top;
 28     inline void push(const Point &p) {
 29         while( top > 1 ) {
 30             if( p.x == ps[top].x && p.y > ps[top].y ) --top;
 31             else if( ( ps[top] - ps[top-1] ) * ( p - ps[top] ) > 0 ) --top;
 32             else break;
 33         }
 34         if( top == 1 && p.x == ps[top].x && p.y > ps[top].y ) --top;
 35         if( !top || p.x != ps[top].x ) ps[++top] = p;
 36     }
 37     inline lli query(const Point &p) {
 38         int l = 1 , r = top , lmid , rmid;
 39         while( r > l + 2 ) {
 40             lmid = ( l + l + r ) / 3 , rmid = ( l + r + r ) / 3;
 41             if( ( p ^ ps[lmid] ) < ( p ^ ps[rmid] ) ) l = lmid;
 42             else r = rmid;
 43         }
 44         lli ret = 0;
 45         for(int i=l;i<=r;i++) ret = max( ret , p ^ ps[i] );
 46         return ret;
 47     }
 48     inline void clear() {
 49         top = 0;
 50     }
 51 }con;
 52 
 53 lli ina[maxn],inb[maxn],f[maxn],cst[maxn],ans,add; // f[id] .
 54 bool isl[maxn];
 55 int n;
 56  
 57 int cmp; // 0 compare height , 1 compare id .
 58 struct Node {
 59     lli hei,id;
 60     friend bool operator < (const Node &a,const Node &b) {
 61         if( cmp ) return a.id != b.id ? a.id < b.id : a.hei < b.hei;
 62         else return a.hei != b.hei ? a.hei < b.hei : a.id < b.id;
 63     }
 64 }ns[maxn];
 65  
 66 vector<Node> vec;
 67  
 68 inline void solve(vector<Node> &vec) {
 69     if( vec.size() <= 1 ) {
 70         if( vec.size() ) f[vec[0].id] = max( f[vec[0].id] , cst[vec[0].id] );
 71         return;
 72     }
 73     vector<Node> vl,vr;
 74     const unsigned mid = vec.size() >> 1;
 75     for(unsigned i=0;i<mid;i++) vl.push_back(vec[i]);
 76     for(unsigned i=mid;i<vec.size();i++) vr.push_back(vec[i]);
 77     solve(vl);
 78     for(unsigned i=0;i<vl.size();i++) isl[vl[i].id] = 1;
 79     for(unsigned i=0;i<vr.size();i++) isl[vr[i].id] = 0;
 80     cmp = 0 , sort(vec.begin(),vec.end()) , con.clear();
 81     for(unsigned i=0;i<vec.size();i++) {
 82         if( isl[vec[i].id] ) {
 83             con.push((Convex::Point){vec[i].hei,f[vec[i].id]});
 84         } else {
 85             f[vec[i].id] = max( f[vec[i].id] , cst[vec[i].id] + con.query((Convex::Point){n-vec[i].id+1,1}));
 86         }
 87     }
 88     solve(vr);
 89 }
 90  
 91 int main() {
 92     static lli sel,lst;
 93     scanf("%d",&n) , add = (lli) n * ( n + 1 ) >> 1;
 94     for(int i=1;i<=n;i++) scanf("%lld",ina+i) , ina[i] -= i;
 95     for(int i=1;i<=n;i++) {
 96         scanf("%lld",inb+i);
 97         if( ina[i] >= 0 ) {
 98             cst[i] = mul - inb[i] - ina[i] * ( n - i + 1 ) ,
 99             vec.push_back((Node){ina[i],i});
100         }
101     }
102     cmp = 1 , sort(vec.begin(),vec.end());
103     solve(vec);
104     for(int i=1;i<=n;i++) ans = max( ans , f[i] );
105     ans -= add;
106     sel = ( ans + mul ) / mul;
107     lst = mul * sel - ans;
108     printf("%lld %lld\n",sel,lst);
109     return 0;
110 }
View Code