凸包習題總結
在平面上能包含所有給定點的最小凸多邊形叫做凸包
一般的題目通常只會讓你維護上凸殼或下凸殼
斜率優化DP是最常考察的題型
一、P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二維凸包
分析
凸包的模板題
首先我們找出縱坐標最小的點，如果有多個點的縱坐標都是最小的則取其中橫坐標最小的
最後找到的這個點一定在我們要維護的凸包上
對於剩下的點，按照它與選出的點形成的直線的極角從小到大排序
極角是從 \(x\) 軸正半軸逆時針旋轉到向量方向所需要的角度，向量 \((x,y)\) 的極角為 \(atan2(y,x)\)，弧度制
在這道題也可以用叉積判斷
叉積的公式是 \(u \times v=x_u \times y_v−x_v \times y_u=−(v \times u)\)
若 \(a×b=0\) 則 \(a\) 與 \(b\) 共線(可以反向)
若 \(a×b>0\) 則 \(b\) 在 \(a\) 逆時針方向
若 \(a×b<0\)則 \(b\) 在 \(a\) 順時針方向
排好序後從前向後掃
如果即將入棧的元素與棧頂兩個元素所構成了一個類似於凹殼的東西
那麼顯然處於頂點的那個點一定不在這個點集的凸包上，所以把它彈出棧，新點入棧
程式碼
#include<cstdio>
#include<cmath>
#include<algorithm>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e5+5;
const double eps=1e-10;
struct Node{
double x,y;
Node(){}
Node(rg double aa,rg double bb){
x=aa,y=bb;
}
friend Node operator -(const Node& A,const Node& B){
return Node(A.x-B.x,A.y-B.y);
}
friend double operator ^(const Node& A,const Node& B){
return A.x*B.y-B.x*A.y;
}
}p[maxn],sta[maxn];
int n,tp;
double getdis(rg Node aa,rg Node bb){
return sqrt((aa.x-bb.x)*(aa.x-bb.x)+(aa.y-bb.y)*(aa.y-bb.y));
}
bool cmp(rg Node aa,rg Node bb){
rg double nans=(aa-p[1])^(bb-p[1]);
if(nans>eps) return 1;
else if(std::fabs(nans)<=eps) return getdis(aa,p[1])<getdis(bb,p[1]);
else return 0;
}
int main(){
n=read();
for(rg int i=1;i<=n;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
if(p[i].y<p[1].y || (p[i].y==p[1].y && p[i].x<p[1].x)) std::swap(p[1],p[i]);
}
std::sort(p+2,p+1+n,cmp);
for(rg int i=1;i<=n;i++){
while(tp>1 && ((p[i]-sta[tp])^(sta[tp]-sta[tp-1]))>eps) tp--;
sta[++tp]=p[i];
}
sta[tp+1]=sta[1];
double nans=0;
for(rg int i=1;i<=tp;i++){
nans+=getdis(sta[i],sta[i+1]);
}
printf("%.2f\n",nans);
return 0;
}
二、P1452 [USACO03FALL]Beauty Contest G /【模板】旋轉卡殼
分析
大致總結一下旋轉卡殼的步驟：
第一步：求出點的凸包
第二步：從最靠近左下方的點開始逆時針依次枚舉所有的邊（求凸包的時候已經記錄在一個棧裡面了）
第三部：繼承上一次尋找時的結果，繼續逆時針尋找最遠的點（這裡用面積來判斷是否更遠）
程式碼
#include<cstdio>
#include<cmath>
#include<algorithm>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e6+5;
const double eps=1e-10;
struct Node{
double x,y;
Node(){}
Node(rg double aa,rg double bb){
x=aa,y=bb;
}
friend Node operator -(const Node& A,const Node& B){
return Node(A.x-B.x,A.y-B.y);
}
friend double operator ^(const Node& A,const Node& B){
return A.x*B.y-B.x*A.y;
}
}p[maxn],sta[maxn];
int n,tp;
double getdis(rg Node aa,rg Node bb){
return (aa.x-bb.x)*(aa.x-bb.x)+(aa.y-bb.y)*(aa.y-bb.y);
}
bool cmp(rg Node aa,rg Node bb){
rg double nans=(aa-p[1])^(bb-p[1]);
if(nans>eps) return 1;
else if(std::fabs(nans)<=eps) return getdis(aa,p[1])<getdis(bb,p[1]);
else return 0;
}
int main(){
n=read();
for(rg int i=1;i<=n;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
if(p[i].y<p[1].y || (p[i].y==p[1].y && p[i].x<p[1].x)) std::swap(p[1],p[i]);
}
std::sort(p+2,p+1+n,cmp);
for(rg int i=1;i<=n;i++){
while(tp>1 && ((p[i]-sta[tp])^(sta[tp]-sta[tp-1]))>eps) tp--;
sta[++tp]=p[i];
}
sta[tp+1]=sta[1];
rg double nans=0;
for(rg int i=1,j=1;i<=tp;i++){
while(((sta[j]-sta[i])^(sta[j]-sta[i+1]))<((sta[j+1]-sta[i])^(sta[j+1]-sta[i+1]))) j=j+1>tp?j+1-tp:j+1;
nans=std::max(nans,std::max(getdis(sta[i],sta[j]),getdis(sta[i+1],sta[j])));
}
printf("%.0f\n",nans);
return 0;
}
三、陶陶的難題II
分析
求 \(\frac{y_i+q_j}{x_i+p_j}\) 的最大值
很顯然的一個 \(01\) 分數規劃的問題
令 \(\frac{y_i+q_j}{x_i+p_j} \geq mids\)
因為都是正數，所以可以直接把分母乘過去
即 \((x_i+p_j)mids \leq (y_i+q_j)\)
化簡後可以得到 \(y_i-x_imids+q_i-p_imids \geq 0\)
左半部分和右半部分的形式其實是一樣的
問題就轉化成了如果求 \(y_i-x_imids\) 的最大值
設 \(y_i-x_imids=ans\)
則 \(y_i=x_imids+ans\)
本質上就是把平面中若干個坐標為 \((x,y)\) 的點帶入一條斜率為 \(mids\) 的直線中，求截距的最大值
所以維護上凸殼，每次查詢時在凸殼上查找第一個斜率小於 \(mids\) 的位置
該位置的點截距是最大的
如果用斜率維護凸殼，要特判斜率不存在的情況
程式碼
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=6e4+5;
typedef double db;
const db eps=1e-7;
int h[maxn],tot=1,n,m;
struct asd{
int to,nxt;
}b[maxn];
void ad(rg int aa,rg int bb){
b[tot].to=bb;
b[tot].nxt=h[aa];
h[aa]=tot++;
}
db x[maxn],y[maxn],p[maxn],q[maxn];
int son[maxn],siz[maxn],fa[maxn],dep[maxn];
void dfs1(rg int now,rg int lat){
fa[now]=lat;
siz[now]=1;
dep[now]=dep[lat]+1;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==lat) continue;
dfs1(u,now);
siz[now]+=siz[u];
if(son[now]==0 || siz[u]>siz[son[now]]) son[now]=u;
}
}
int tp[maxn],dfn[maxn],dfnc,rk[maxn];
void dfs2(rg int now,rg int top){
tp[now]=top;
dfn[now]=++dfnc;
rk[dfnc]=now;
if(son[now]) dfs2(son[now],top);
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==fa[now] || u==son[now]) continue;
dfs2(u,u);
}
}
struct Node{
double x,y;
Node(){}
Node(rg double aa,rg double bb){
x=aa,y=bb;
}
};
struct trr{
int l,r;
std::vector<Node> ans1,ans2;
}tr[maxn<<2];
Node sta[maxn],que[maxn];
int ncnt=0,head,tail;
double xl(rg Node aa,rg Node bb){
if(std::fabs(bb.x-aa.x)<eps){
if(std::fabs(bb.y-aa.y)<eps) return 0;
else if(bb.y>aa.y) return 1e8;
else return -1e8;
}
return (bb.y-aa.y)/(bb.x-aa.x);
}
void push_up1(rg int da){
rg int cnt0=0,cnt1=0,tot0=tr[da<<1].ans1.size(),tot1=tr[da<<1|1].ans1.size();
ncnt=0;
while(cnt0<tot0 || cnt1<tot1){
if(cnt0==tot0) sta[++ncnt]=tr[da<<1|1].ans1[cnt1++];
else if(cnt1==tot1) sta[++ncnt]=tr[da<<1].ans1[cnt0++];
else if(tr[da<<1].ans1[cnt0].x<tr[da<<1|1].ans1[cnt1].x || (tr[da<<1].ans1[cnt0].x==tr[da<<1|1].ans1[cnt1].x && tr[da<<1].ans1[cnt0].y<tr[da<<1|1].ans1[cnt1].y)) sta[++ncnt]=tr[da<<1].ans1[cnt0++];
else sta[++ncnt]=tr[da<<1|1].ans1[cnt1++];
}
head=1,tail=0;
for(rg int i=1;i<=ncnt;i++){
while(tail>1 && xl(que[tail],sta[i])>xl(que[tail-1],que[tail])) tail--;
que[++tail]=sta[i];
}
for(rg int i=head;i<=tail;i++) tr[da].ans1.push_back(que[i]);
}
void push_up2(rg int da){
rg int cnt0=0,cnt1=0,tot0=tr[da<<1].ans2.size(),tot1=tr[da<<1|1].ans2.size();
ncnt=0;
while(cnt0<tot0 || cnt1<tot1){
if(cnt0==tot0) sta[++ncnt]=tr[da<<1|1].ans2[cnt1++];
else if(cnt1==tot1) sta[++ncnt]=tr[da<<1].ans2[cnt0++];
else if(tr[da<<1].ans2[cnt0].x<tr[da<<1|1].ans2[cnt1].x || (tr[da<<1].ans2[cnt0].x==tr[da<<1|1].ans2[cnt1].x && tr[da<<1].ans2[cnt0].y<tr[da<<1|1].ans2[cnt1].y)) sta[++ncnt]=tr[da<<1].ans2[cnt0++];
else sta[++ncnt]=tr[da<<1|1].ans2[cnt1++];
}
head=1,tail=0;
for(rg int i=1;i<=ncnt;i++){
while(tail>1 && xl(que[tail],sta[i])>xl(que[tail-1],que[tail])) tail--;
que[++tail]=sta[i];
}
for(rg int i=head;i<=tail;i++) tr[da].ans2.push_back(que[i]);
}
void build(rg int da,rg int l,rg int r){
tr[da].l=l,tr[da].r=r;
if(tr[da].l==tr[da].r){
tr[da].ans1.push_back(Node(x[rk[l]],y[rk[l]]));
tr[da].ans2.push_back(Node(p[rk[l]],q[rk[l]]));
return;
}
rg int mids=(l+r)>>1;
build(da<<1,l,mids);
build(da<<1|1,mids+1,r);
push_up1(da);
push_up2(da);
}
double getans1(rg int da,rg double nx){
rg int l=1,r=tr[da].ans1.size(),mids;
while(l<r){
mids=(l+r)>>1;
if(xl(tr[da].ans1[mids-1],tr[da].ans1[mids])<=nx) r=mids;
else l=mids+1;
}
l--;
return tr[da].ans1[l].y-tr[da].ans1[l].x*nx;
}
double cx1(rg int da,rg int l,rg int r,rg double nx){
if(tr[da].l>=l && tr[da].r<=r){
return getans1(da,nx);
}
rg int mids=(tr[da].l+tr[da].r)>>1;
rg double nans=-1e8;
if(l<=mids) nans=std::max(nans,cx1(da<<1,l,r,nx));
if(r>mids) nans=std::max(nans,cx1(da<<1|1,l,r,nx));
return nans;
}
double getans2(rg int da,rg double nx){
rg int l=1,r=tr[da].ans2.size(),mids;
while(l<r){
mids=(l+r)>>1;
if(xl(tr[da].ans2[mids-1],tr[da].ans2[mids])<=nx) r=mids;
else l=mids+1;
}
l--;
return tr[da].ans2[l].y-tr[da].ans2[l].x*nx;
}
double cx2(rg int da,rg int l,rg int r,rg double nx){
if(tr[da].l>=l && tr[da].r<=r){
return getans2(da,nx);
}
rg int mids=(tr[da].l+tr[da].r)>>1;
rg double nans=-1e8;
if(l<=mids) nans=std::max(nans,cx2(da<<1,l,r,nx));
if(r>mids) nans=std::max(nans,cx2(da<<1|1,l,r,nx));
return nans;
}
bool trcx(rg int xx,rg int yy,rg double nx){
rg double nans1=-1e8,nans2=-1e8;
while(tp[xx]!=tp[yy]){
if(dep[tp[xx]]<dep[tp[yy]]) std::swap(xx,yy);
nans1=std::max(nans1,cx1(1,dfn[tp[xx]],dfn[xx],nx));
nans2=std::max(nans2,cx2(1,dfn[tp[xx]],dfn[xx],nx));
xx=fa[tp[xx]];
}
if(dep[xx]<dep[yy]) std::swap(xx,yy);
nans1=std::max(nans1,cx1(1,dfn[yy],dfn[xx],nx));
nans2=std::max(nans2,cx2(1,dfn[yy],dfn[xx],nx));
return nans1+nans2>=eps;
}
double solve(rg int xx,rg int yy){
rg double l=-1e8,r=1e8,mids;
for(rg int i=1;i<=40;i++){
mids=(l+r)/2.0;
if(trcx(xx,yy,mids)) l=mids;
else r=mids;
}
return mids;
}
int main(){
memset(h,-1,sizeof(h));
n=read();
for(rg int i=1;i<=n;i++) scanf("%lf",&x[i]);
for(rg int i=1;i<=n;i++) scanf("%lf",&y[i]);
for(rg int i=1;i<=n;i++) scanf("%lf",&p[i]);
for(rg int i=1;i<=n;i++) scanf("%lf",&q[i]);
rg int aa,bb;
for(rg int i=2;i<=n;i++){
aa=read(),bb=read();
ad(aa,bb);
ad(bb,aa);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
m=read();
for(rg int i=1;i<=m;i++){
aa=read(),bb=read();
printf("%.4f\n",solve(aa,bb));
}
return 0;
}
四、P4192 旅行規劃
分析
轉化一下題意
區間加等差數列，查詢區間最大值
如果是單點查詢的話，可以在線段樹上打一個標記，邊查詢邊下放
但是區間查詢的話需要整棵樹下放標記，複雜度太高
考慮萬能的分塊做法
因為等差數列加等差數列還是還是一個等差數列
所以對每一個塊維護等差數列的首項 \(beg\) 以及公差 \(d\)
這樣，一個塊內所有點的值都可以寫成與下標相關的一次函數的形式
即 \(ans[i]=i \times d+sum[i]\)
\(sum[i]=ans[i]-i \times d\)
其中 \(sum[i]\) 為上一次重構後 \(i\) 處前綴和的值
對於整個塊的首項，我們先不去考慮，最後把它加上即可
這樣，我們就可以把下標 \(i\) 看成橫坐標，把 \(sum[i]\) 看成縱坐標，把 \(-d\) 看成斜率
如果是對整個塊進行修改，那麼橫縱坐標都是不變的
變化的只是斜率
因此可以維護一個上凸殼
在上凸殼中二分查找使截距 \(ans[i]\) 最大的點
如果是對塊的一部分進行修改或查詢，我們就把這個塊進行暴力重構，重新建一個凸包
如果塊長是 \(\sqrt{n}\) 的話
複雜度就是 \(m\sqrt{n}log\sqrt{n}\)
程式碼
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e5+5;
typedef double db;
const db eps=1e-18;
struct Node{
int x;
long long y;
Node(){}
Node(rg int aa,rg long long bb){
x=aa,y=bb;
}
friend bool operator < (const Node& A,const Node& B){
if(A.x==B.x) return A.y<B.y;
else return A.x<B.x;
}
};
int shuyu[maxn],blo,n,m,l[maxn],r[maxn],tp,tail;
std::vector<Node> ans[maxn];
Node sta[maxn],que[maxn];
long long beg[maxn],sum[maxn],d[maxn];
inline double xl(rg Node aa,rg Node bb){
if(std::fabs((double)bb.x-(double)aa.x)<eps){
if(std::fabs((double)bb.y-(double)aa.y)<eps) return 0;
else if(bb.y>aa.y) return 1e18;
else return -1e18;
}
return ((double)bb.y-(double)aa.y)/((double)bb.x-(double)aa.x);
}
void build(rg int id){
if(d[id]){
for(rg int i=l[id];i<=r[id];i++) sum[i]+=1LL*d[id]*(i-l[id]+1);
d[id]=0;
}
if(beg[id]){
for(rg int i=l[id];i<=r[id];i++) sum[i]+=beg[id];
beg[id]=0;
}
tp=tail=0;
ans[id].clear();
for(rg int i=l[id];i<=r[id];i++) sta[++tp]=Node(i-l[id]+1,sum[i]);
std::sort(sta+1,sta+tp+1);
for(rg int i=1;i<=tp;i++){
while(tail>1 && xl(que[tail],sta[i])>=xl(que[tail-1],que[tail])) tail--;
que[++tail]=sta[i];
}
for(rg int i=1;i<=tail;i++) ans[id].push_back(que[i]);
}
void xg(rg int nl,rg int nr,rg int val){
for(rg int i=nl;i<=std::min(r[shuyu[nl]],nr);i++){
sum[i]+=1LL*val*(i-nl+1);
}
for(rg int i=nr+1;i<=r[shuyu[nr]];i++){
sum[i]+=1LL*val*(nr-nl+1);
}
for(rg int i=shuyu[nr]+1;i<=shuyu[n];i++){
beg[i]+=1LL*val*(nr-nl+1);
}
build(shuyu[nl]);
if(shuyu[nl]==shuyu[nr]) return;
for(rg int i=l[shuyu[nr]];i<=nr;i++){
sum[i]+=1LL*val*(i-nl+1);
}
build(shuyu[nr]);
for(rg int i=shuyu[nl]+1;i<=shuyu[nr]-1;i++){
beg[i]+=1LL*(l[i]-nl)*val;
d[i]+=val;
}
}
long long qjcx(rg int id){
rg int nl=1,nr=ans[id].size(),mids;
rg double nans=-1.0*d[id];
while(nl<nr){
mids=(nl+nr)>>1;
if(xl(ans[id][mids-1],ans[id][mids])<=nans) nr=mids;
else nl=mids+1;
}
nl--;
return (long long)ans[id][nl].y+(long long)d[id]*ans[id][nl].x+(long long)beg[id];
}
long long cx(rg int nl,rg int nr){
build(shuyu[nl]);
rg long long nans=-0x3f3f3f3f3f3f3f3f;
for(rg int i=nl;i<=std::min(r[shuyu[nl]],nr);i++) nans=std::max(nans,sum[i]);
if(shuyu[nl]==shuyu[nr]) return nans;
build(shuyu[nr]);
for(rg int i=l[shuyu[nr]];i<=nr;i++) nans=std::max(nans,sum[i]);
for(rg int i=shuyu[nl]+1;i<=shuyu[nr]-1;i++){
nans=std::max(nans,qjcx(i));
}
return nans;
}
int main(){
memset(l,0x3f,sizeof(l));
n=read();
blo=sqrt(n);
for(rg int i=1;i<=n;i++) shuyu[i]=(i-1)/blo+1;
for(rg int i=1;i<=n;i++) sum[i]=read();
for(rg int i=1;i<=n;i++) sum[i]+=sum[i-1];
for(rg int i=1;i<=n;i++){
l[shuyu[i]]=std::min(l[shuyu[i]],i);
r[shuyu[i]]=std::max(r[shuyu[i]],i);
}
for(rg int i=1;i<=shuyu[n];i++) build(i);
m=read();
rg int aa,bb,cc,dd;
for(rg int i=1;i<=m;i++){
aa=read(),bb=read(),cc=read();
if(aa==0){
dd=read();
xg(bb,cc,dd);
} else {
printf("%lld\n",cx(bb,cc));
}
}
return 0;
}
五、P3309 [SDOI2014]向量集
分析
求 \(ax+by\) 的最大值
如果沒有加點操作，就是線段樹上維護凸包的裸題
設 \(ans=ax+by\)
則 \(by=ans-ax\)
\(y=-\frac{a}{b}x+\frac{ans}{b}\)
若 \(b<0\) 就是求截距的最小值，維護一個下凸殼即可
若 \(b>0\) 則是求截距的最大值，維護一個上凸殼即可
對於加點操作，我們記錄一下線段樹每個區間所代表的節點已經加入了多少向量
如果向量的個數和區間的長度相等，就構建凸包
因為每一個節點只會構建一次凸包，所以複雜度是正確的
程式碼
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=4e5+5;
typedef long double db;
const db eps=1e-7;
int n;
char s[maxn];
db x[maxn],y[maxn];
struct Node{
double x,y;
Node(){}
Node(rg double aa,rg double bb){
x=aa,y=bb;
}
};
struct trr{
int l,r,siz;
std::vector<Node> ans1,ans2;
}tr[maxn<<2];
Node sta[maxn],que[maxn];
int ncnt=0,head,tail;
double xl(rg Node aa,rg Node bb){
if(std::fabs(bb.x-aa.x)<eps){
if(std::fabs(bb.y-aa.y)<eps) return 0;
else if(bb.y>aa.y) return 1e18;
else return -1e18;
}
return (bb.y-aa.y)/(bb.x-aa.x);
}
void push_up1(rg int da){
rg int cnt0=0,cnt1=0,tot0=tr[da<<1].ans1.size(),tot1=tr[da<<1|1].ans1.size();
ncnt=0;
while(cnt0<tot0 || cnt1<tot1){
if(cnt0==tot0) sta[++ncnt]=tr[da<<1|1].ans1[cnt1++];
else if(cnt1==tot1) sta[++ncnt]=tr[da<<1].ans1[cnt0++];
else if(tr[da<<1].ans1[cnt0].x<tr[da<<1|1].ans1[cnt1].x || (tr[da<<1].ans1[cnt0].x==tr[da<<1|1].ans1[cnt1].x && tr[da<<1].ans1[cnt0].y<tr[da<<1|1].ans1[cnt1].y)) sta[++ncnt]=tr[da<<1].ans1[cnt0++];
else sta[++ncnt]=tr[da<<1|1].ans1[cnt1++];
}
head=1,tail=0;
for(rg int i=1;i<=ncnt;i++){
while(tail>1 && xl(que[tail],sta[i])>=xl(que[tail-1],que[tail])) tail--;
que[++tail]=sta[i];
}
for(rg int i=head;i<=tail;i++) tr[da].ans1.push_back(que[i]);
}
void push_up2(rg int da){
rg int cnt0=0,cnt1=0,tot0=tr[da<<1].ans2.size(),tot1=tr[da<<1|1].ans2.size();
ncnt=0;
while(cnt0<tot0 || cnt1<tot1){
if(cnt0==tot0) sta[++ncnt]=tr[da<<1|1].ans2[cnt1++];
else if(cnt1==tot1) sta[++ncnt]=tr[da<<1].ans2[cnt0++];
else if(tr[da<<1].ans2[cnt0].x<tr[da<<1|1].ans2[cnt1].x || (tr[da<<1].ans2[cnt0].x==tr[da<<1|1].ans2[cnt1].x && tr[da<<1].ans2[cnt0].y<tr[da<<1|1].ans2[cnt1].y)) sta[++ncnt]=tr[da<<1].ans2[cnt0++];
else sta[++ncnt]=tr[da<<1|1].ans2[cnt1++];
}
head=1,tail=0;
for(rg int i=1;i<=ncnt;i++){
while(tail>1 && xl(que[tail],sta[i])<=xl(que[tail-1],que[tail])) tail--;
que[++tail]=sta[i];
}
for(rg int i=head;i<=tail;i++) tr[da].ans2.push_back(que[i]);
}
void build(rg int da,rg int l,rg int r){
tr[da].l=l,tr[da].r=r;
if(tr[da].l==tr[da].r) return;
rg int mids=(l+r)>>1;
build(da<<1,l,mids);
build(da<<1|1,mids+1,r);
}
void updat(rg int da,rg int wz,rg double x,rg double y){
if(tr[da].l==tr[da].r){
tr[da].ans1.push_back(Node(x,y));
tr[da].ans2.push_back(Node(x,y));
tr[da].siz++;
return;
}
rg int mids=(tr[da].l+tr[da].r)>>1;
if(wz<=mids) updat(da<<1,wz,x,y);
else updat(da<<1|1,wz,x,y);
tr[da].siz++;
if(tr[da].siz==tr[da].r-tr[da].l+1){
push_up1(da);
push_up2(da);
}
}
int aa,bb,cc,dd;
long long getans1(rg int da,rg double nx){
rg int l=1,r=tr[da].ans1.size(),mids;
while(l<r){
mids=(l+r)>>1;
if(xl(tr[da].ans1[mids-1],tr[da].ans1[mids])<=nx) r=mids;
else l=mids+1;
}
l--;
return 1LL*tr[da].ans1[l].x*cc+1LL*tr[da].ans1[l].y*dd;
}
long long cx1(rg int da,rg int l,rg int r,rg double nx){
if(tr[da].l>=l && tr[da].r<=r){
return getans1(da,nx);
}
rg int mids=(tr[da].l+tr[da].r)>>1;
rg long long nans=-0x7f7f7f7f7f7f7f7f;
if(l<=mids) nans=std::max(nans,cx1(da<<1,l,r,nx));
if(r>mids) nans=std::max(nans,cx1(da<<1|1,l,r,nx));
return nans;
}
long long getans2(rg int da,rg double nx){
rg int l=1,r=tr[da].ans2.size(),mids;
while(l<r){
mids=(l+r)>>1;
if(xl(tr[da].ans2[mids-1],tr[da].ans2[mids])<=nx) l=mids+1;
else r=mids;
}
l--;
return 1LL*tr[da].ans2[l].x*cc+1LL*tr[da].ans2[l].y*dd;
}
long long cx2(rg int da,rg int l,rg int r,rg double nx){
if(tr[da].l>=l && tr[da].r<=r){
return getans2(da,nx);
}
rg int mids=(tr[da].l+tr[da].r)>>1;
rg long long nans=-0x7f7f7f7f7f7f7f7f;
if(l<=mids) nans=std::max(nans,cx2(da<<1,l,r,nx));
if(r>mids) nans=std::max(nans,cx2(da<<1|1,l,r,nx));
return nans;
}
bool jud=0;
int cnt;
long long latans;
int get(rg int now){
return now^(latans&0x7fffffff);
}
int main(){
n=read();
scanf("%s",s+1);
build(1,1,n);
if(s[1]!='E') jud=1;
for(rg int i=1;i<=n;i++){
scanf("%s",s+1);
if(s[1]=='A'){
aa=read(),bb=read();
if(jud) aa=get(aa),bb=get(bb);
updat(1,++cnt,aa,bb);
} else {
cc=read(),dd=read(),aa=read(),bb=read();
if(jud) aa=get(aa),bb=get(bb),cc=get(cc),dd=get(dd);
if(dd<0) latans=cx2(1,aa,bb,-(db)cc/dd);
else latans=cx1(1,aa,bb,-(db)cc/dd);
printf("%lld\n",latans);
}
}
return 0;
}
六、P2521 [HAOI2011]防線修建
分析
動態維護凸包
因為題目中只有刪點操作而且沒有強制在線
所以可以倒序處理，將刪點操作轉變為加點操作
加點時，在平衡樹中找到該點橫坐標的前驅後繼
把不合法的在平衡樹中刪掉即可
程式碼
#include<cstdio>
#include<algorithm>
#include<set>
#include<cmath>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=2e5+5;
const double eps=1e-8;
struct Node{
double x,y;
Node(){}
Node(rg double aa,rg double bb){
x=aa,y=bb;
}
friend bool operator < (rg const Node& A,rg const Node& B){
if(A.x==B.x) return A.y<B.y;
return A.x<B.x;
}
}b[maxn],cp;
int n,m,q,jlx[maxn],jly[maxn];
double ans[maxn],nans;
bool vis[maxn];
std::set<Node> s;
#define sit std::set<Node>::iterator
double getdis(rg Node aa,rg Node bb){
return sqrt((aa.x-bb.x)*(aa.x-bb.x)+(aa.y-bb.y)*(aa.y-bb.y));
}
double xl(rg Node aa,rg Node bb){
if(std::fabs(bb.x-aa.x)<eps){
if(std::fabs(bb.y-aa.y)<eps) return 0;
else if(bb.y>aa.y) return 1e8;
else return -1e8;
}
return (bb.y-aa.y)/(bb.x-aa.x);
}
void ad(rg Node now){
rg sit itl,itr=s.lower_bound(now),tmp;
itl=itr;
--itl;
if(xl(now,*itr)>=xl(*itl,now)) return;
nans-=getdis(*itl,*itr);
while(itr!=s.end()){
tmp=itr;
++itr;
if(itr==s.end() || xl(*tmp,*itr)<xl(now,*tmp)) break;
nans-=getdis(*itr,*tmp);
s.erase(tmp);
}
while(itl!=s.begin()){
tmp=itl;
--itl;
if(xl(*tmp,now)<xl(*itl,*tmp)) break;
nans-=getdis(*itl,*tmp);
s.erase(tmp);
}
s.insert(now);
itl=itr=s.lower_bound(now);
--itl,++itr;
nans+=getdis(*itl,now);
nans+=getdis(*itr,now);
}
int main(){
n=read(),cp.x=read(),cp.y=read();
m=read();
for(rg int i=1;i<=m;i++){
b[i].x=read(),b[i].y=read();
}
q=read();
for(rg int i=1;i<=q;i++){
jlx[i]=read();
if(jlx[i]==1){
jly[i]=read();
vis[jly[i]]=1;
}
}
s.insert(Node(0,0));
s.insert(Node(n,0));
s.insert(cp);
nans=getdis(Node(0,0),cp)+getdis(Node(n,0),cp);
for(rg int i=1;i<=m;i++){
if(!vis[i]) ad(b[i]);
}
for(rg int i=q;i>=1;i--){
if(jlx[i]==2) ans[i]=nans;
else ad(b[jly[i]]);
}
for(rg int i=1;i<=q;i++){
if(jlx[i]==2) printf("%.2f\n",ans[i]);
}
return 0;
}
七、P4027 [NOI2007] 貨幣兌換
分析
如果我們在第 \(i\) 天買入紀念券第 \(j\) 天賣出紀念券有利可圖
那麼我們一定會在第 \(i\) 天花完所有的錢
因此可以求出在第 \(i\) 天花完錢在第 \(j\) 天得到的兩種金券數 \(x_j=\frac{f_jR_j}{a_jR_j+b_j}\) 和 \(y_j=\frac{f_j}{a_jR_j+b_j}\)
然後得到狀態轉移程：\(f_i=x_ja_i+y_jb_i\)
將方程稍微變形成直線斜截式方程
\(y_j=-\frac{a_ix_j}{b_i}+\frac{f_i}{b_i}\)
一個可以進行斜率優化的式子
但是我們會發現這道題的橫坐標和斜率不是單調遞增的
所以要用 \(CDQ\) 分治解決
對於左半部分按照橫坐標 \(x\) 從小到大排序
對於右半部分按照斜率從小到大排序
先處理左半部分的 \(dp\) 值
用得到的結果去更新右半部分的 \(dp\)值
然後再遞歸右半部分
程式碼
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define rg register
const int maxn=1e5+5;
const double eps=1e-8;
int n,s;
struct asd{
double a,b,rat,k,x,y;
int id;
}q[maxn],tmp[maxn];
double f[maxn];
double xl(rg int i,rg int j){
if(std::fabs(q[j].x-q[i].x)<eps){
if(std::fabs(q[j].y-q[i].y)<eps) return 0;
else if(q[j].y>q[i].y) return 1e18;
else return -1e18;
}
return (q[j].y-q[i].y)/(q[j].x-q[i].x);
}
bool cmp(asd aa,asd bb){
return aa.k>bb.k;
}
int que[maxn];
void solve(rg int l,rg int r){
if(l==r){
f[q[l].id]=std::max(f[q[l].id],f[q[l].id-1]);
q[l].y=f[l]/(q[l].a*q[l].rat+q[l].b);
q[l].x=q[l].y*q[l].rat;
return;
}
rg int mids=(l+r)>>1,head=l-1,tail=mids;
for(rg int i=l;i<=r;i++){
if(q[i].id<=mids) tmp[++head]=q[i];
else tmp[++tail]=q[i];
}
for(rg int i=l;i<=r;i++) q[i]=tmp[i];
solve(l,mids);
head=1,tail=0;
for(rg int i=l;i<=mids;i++){
while(tail>1 && xl(que[tail],i)>=xl(que[tail-1],que[tail])) tail--;
que[++tail]=i;
}
for(rg int i=mids+1;i<=r;i++){
while(head<tail && xl(que[head],que[head+1])>=q[i].k) head++;
f[q[i].id]=std::max(f[q[i].id],q[que[head]].y*q[i].b+q[que[head]].x*q[i].a);
}
solve(mids+1,r);
head=l,tail=mids+1;
for(rg int i=l;i<=r;i++){
if(tail>r || (head<=mids && q[head].x<=q[tail].x)) tmp[i]=q[head++];
else tmp[i]=q[tail++];
}
for(rg int i=l;i<=r;i++) q[i]=tmp[i];
}
int main(){
scanf("%d%d",&n,&s);
for(rg int i=1;i<=n;i++){
scanf("%lf%lf%lf",&q[i].a,&q[i].b,&q[i].rat);
q[i].id=i,q[i].k=-q[i].a/q[i].b;
}
f[0]=s;
std::sort(q+1,q+1+n,cmp);
solve(1,n);
printf("%.3f\n",f[n]);
return 0;
}
八、P2305 [NOI2014] 購票
分析
上一道題的強化版
把序列上的問題搬到了樹上
解決方法也由 \(CDQ\) 分治變成了點分治
\(DP\) 方程顯然：\(f_i=min(f_j+(dis_i-dis_j) \times p_i+q_i)\)
\(dis\) 是根到每個點的距離
這個式子可以斜率優化
但是暴力建凸包肯定不行
考慮用點分治，順序是
\(1\)、處理當前子樹
\(2\)、找當前子樹的重心
\(3\)、一起分治重心和根節點
\(4\)、得到根節點到子樹重心之間鏈的答案
\(5\)、用這個答案來更新重心其他子樹的 \(ans\)
\(6\)、繼續分治重心的其他子樹
程式碼
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define rg register
const int maxn=2e5+5;
int h[maxn],tot=1,n,t,fa[maxn],p[maxn],maxsiz[maxn];
struct asd{
int to,nxt;
}b[maxn<<1];
void ad(rg int aa,rg int bb){
b[tot].to=bb;
b[tot].nxt=h[aa];
h[aa]=tot++;
}
long long dis[maxn],f[maxn],s[maxn],lv[maxn],q[maxn];
void dfs(rg int now){
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==fa[now]) continue;
dis[u]=dis[now]+s[u];
dfs(u);
}
}
int rt,totsiz,siz[maxn];
bool vis[maxn];
void getroot(rg int now){
maxsiz[now]=0,siz[now]=1;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(vis[u] || u==fa[now]) continue;
getroot(u);
siz[now]+=siz[u];
maxsiz[now]=std::max(maxsiz[now],siz[u]);
}
maxsiz[now]=std::max(maxsiz[now],totsiz-siz[now]);
if(maxsiz[now]<maxsiz[rt]) rt=now;
}
double xl(rg int i,rg int j){
return ((double)f[i]-(double)f[j])/((double)dis[i]-(double)dis[j]);
}
bool cmp(rg int aa,rg int bb){
return dis[aa]-lv[aa]>dis[bb]-lv[bb];
}
int sta[maxn],tp,sta2[maxn],tp2;
int ef(rg double now){
rg int l=1,r=tp,mids;
while(l<r){
mids=(l+r)>>1;
if(xl(sta[mids],sta[mids+1])<=now) r=mids;
else l=mids+1;
}
return sta[l];
}
void dfs2(rg int now,rg int lat){
sta2[++tp2]=now;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(!vis[u] && u!=lat) dfs2(u,now);
}
}
void solve(rg int now){
rt=0;
getroot(now);
vis[rt]=1;
rg int nrt=rt;
if(now!=nrt){
totsiz=siz[now]-siz[nrt];
solve(now);
rg int jl=nrt,cs=0;
tp=tp2=0;
dfs2(nrt,0);
std::sort(sta2+1,sta2+1+tp2,cmp);
for(rg int i=1;i<=tp2;i++){
while(jl!=fa[now] && dis[sta2[i]]-dis[jl]<=lv[sta2[i]]){
while(tp>1 && xl(jl,sta[tp])>=xl(sta[tp],sta[tp-1])) tp--;
sta[++tp]=jl;
jl=fa[jl];
}
if(tp){
cs=ef((double)p[sta2[i]]);
f[sta2[i]]=std::min(f[sta2[i]],f[cs]+1LL*dis[sta2[i]]*p[sta2[i]]-1LL*dis[cs]*p[sta2[i]]+1LL*q[sta2[i]]);
}
}
} else {
tp=tp2=0;
dfs2(nrt,0);
}
for(rg int i=1;i<=tp2;i++){
if(dis[sta2[i]]-dis[nrt]<=lv[sta2[i]]){
f[sta2[i]]=std::min(f[sta2[i]],f[nrt]+1LL*dis[sta2[i]]*p[sta2[i]]-1LL*dis[nrt]*p[sta2[i]]+1LL*q[sta2[i]]);
}
}
for(rg int i=h[nrt];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(!vis[u]){
totsiz=siz[u];
solve(u);
}
}
}
int main(){
memset(h,-1,sizeof(h));
memset(f,0x3f,sizeof(f));
scanf("%d%d",&n,&t);
for(rg int i=2;i<=n;i++){
scanf("%d%lld%d%lld%lld",&fa[i],&s[i],&p[i],&q[i],&lv[i]);
ad(i,fa[i]);
ad(fa[i],i);
}
f[1]=0;
dfs(1);
totsiz=n,maxsiz[0]=0x3f3f3f3f;
solve(1);
for(rg int i=2;i<=n;i++) printf("%lld\n",f[i]);
return 0;
}
