傳送門
文章目錄
題意：
給你nnn個點(xi,yi)(x_i,y_i)(xi?,yi?)，每個點有個價值cic_ici?，現在你可以框一個正方形，要求左下角和右上角的坐標(x,y)(x,y)(x,y)必須x=yx=yx=y，也就是說必須在x=yx=yx=y這條直線上。現在你可以框一個正方形，被正方形框到的點算入總價值，求能得到的最大的總價值。總價值=被框的點的價值?-?正方形的長度。
思路：
在二維平面畫了很多都沒找到規律，看了題解才知道，這個題有一個很巧妙的轉換，設正方形左下角坐標(x,x)(x,x)(x,x)，右上角坐標(y,y)(y,y)(y,y)，對于(xi,yi)(x_i,y_i)(xi?,yi?)如果他能被這個正方形包含在內部，那么必須滿足x<=min(xi,yi)<=max(xi,yi)<=yx<=min(x_i,y_i)<=max(x_i,y_i)<=yx<=min(xi?,yi?)<=max(xi?,yi?)<=y。看到這個式子，很明顯它可以將每個點轉換成一個區間的形式，即[min(xi,yi),max(xi,yi)][min(x_i,y_i),max(x_i,y_i)][min(xi?,yi?),max(xi?,yi?)]。
現在我們重新描述以下這個問題，給你若干個區間，每個區間有一個價值，你需要覆蓋一段區間，使得覆蓋到的區間的價值?-?區間長度最大。當然這里覆蓋是必須完全覆蓋。
轉換成這個問題，就比較容易做了，這里介紹一種線段樹的做法。
首先需要發現一個性質，那就是我們選的區間起點一定是某個區間的起點，終點一定是某個區間的終點。這個比較顯然。
那么我們將左端點按從小到大排序，讓后倒著掃，每次都將當前左端點相等的區間都加入，即將[yi,1e9][y_i,1e9][yi?,1e9]都加上cic_ici?。這樣可保證以左端點為起點能求解出最佳答案。
以上操作顯然可仍線段樹里面，現在我們問題就轉換成了如何求出來tree(xi,1e9)max?(r?xi)tree(x_i,1e9)_{max}-(r-x_i)tree(xi?,1e9)max??(r?xi?)，前面一部分就是線段樹區間最大值的查詢，對于后面，由于我們枚舉的xix_ixi?，所以xix_ixi?已經知道了，我們可將其移動一下變成xi+tree(xi,1e9)max?rx_i+tree(x_i,1e9)_{max}-rxi?+tree(xi?,1e9)max??r，那么rrr怎么辦呢？我們可以在建線段樹的時候將初始值置為其rrr即可，查詢的時候需要加上左端點。
讓后可以離散化一下比較好些，當然也可以動態開點？
復雜度O(nlogn)O(nlogn)O(nlogn)
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<random>
#include<cassert>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].l+tr[u].r)>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const LL inf
=0x3f3f3f3f3f3f3f3f;
const double eps
=1e-6;int n
,se
;
struct node {int X
,Y
,c
;bool operator < (const node
&x
) const {return x
.X
>X
;}
}p
[N
];
vector
<int>v
;
struct Node {int l
,r
;LL now
,mx
,lazy
,id
;
}tr
[N
<<2];int find(int x
) {return lower_bound(v
.begin(),v
.end(),x
)-v
.begin()+1;
}void pushup(int u
) {if(tr
[L
].mx
>tr
[R
].mx
) {tr
[u
].mx
=tr
[L
].mx
;tr
[u
].id
=tr
[L
].id
;} else {tr
[u
].mx
=tr
[R
].mx
;tr
[u
].id
=tr
[R
].id
;}
}void pushdown(int u
) {LL lazy
=tr
[u
].lazy
; tr
[u
].lazy
=0;tr
[L
].lazy
+=lazy
; tr
[L
].mx
+=lazy
;tr
[R
].lazy
+=lazy
; tr
[R
].mx
+=lazy
;
}void build(int u
,int l
,int r
) {tr
[u
]={l
,r
,0,0,0,0};if(l
==r
) {tr
[u
].mx
=-v
[l
-1];tr
[u
].id
=v
[l
-1];return ;}build(L
,l
,Mid
); build(R
,Mid
+1,r
);pushup(u
);
}void change(int u
,int l
,int r
,int c
) {if(tr
[u
].l
>=l
&&tr
[u
].r
<=r
) {tr
[u
].mx
+=c
; tr
[u
].lazy
+=c
;return;}pushdown(u
);if(l
<=Mid
) change(L
,l
,r
,c
);if(r
>Mid
) change(R
,l
,r
,c
);pushup(u
);
}pair
<LL
,int> query(int u
,int l
,int r
) {if(tr
[u
].l
>=l
&&tr
[u
].r
<=r
) return {tr
[u
].mx
,tr
[u
].id
};pushdown(u
);pair
<LL
,int> ans
={-inf
,0};if(l
<=Mid
) ans
=max(ans
,query(L
,l
,r
));if(r
>Mid
) ans
=max(ans
,query(R
,l
,r
));return ans
;
}int main()
{
LL ans
=0;int l
=mod
,r
=mod
;scanf("%d",&n
);for(int i
=1;i
<=n
;i
++) {scanf("%d%d%d",&p
[i
].X
,&p
[i
].Y
,&p
[i
].c
);if(p
[i
].X
>p
[i
].Y
) swap(p
[i
].X
,p
[i
].Y
);v
.pb(p
[i
].X
); v
.pb(p
[i
].Y
);}sort(v
.begin(),v
.end()); v
.erase(unique(v
.begin(),v
.end()),v
.end());sort(p
+1,p
+1+n
); se
=v
.size();for(int i
=1;i
<=n
;i
++) p
[i
].X
=find(p
[i
].X
),p
[i
].Y
=find(p
[i
].Y
);build(1,1,se
);for(int i
=n
;i
>=1;i
--) {int xx
=p
[i
].X
;while(i
>=1&&p
[i
].X
==xx
) change(1,p
[i
].Y
,se
,p
[i
].c
),i
--; i
++;pair
<LL
,int> now
=query(1,p
[i
].X
,se
);now
.X
+=v
[p
[i
].X
-1];if(now
.X
>ans
) {ans
=now
.X
;l
=v
[p
[i
].X
-1],r
=now
.Y
;}}printf("%lld\n%d %d %d %d\n",ans
,l
,l
,r
,r
);return 0;
}
總結
以上是生活随笔為你收集整理的Educational Codeforces Round 73 (Rated for Div. 2) F. Choose a Square 线段树 + 二维转一维的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
