给别人建网站工作行吗,阿克苏网站建设咨询,重庆网站制作教程,大专毕业设计网站传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你nnn个点(xi,yi)(x_i,y_i)(xi,yi)#xff0c;每个点有个价值cic_ici#xff0c;现在你可以框一个正方形#xff0c;要求左下角和右上角的坐标(x,y)(x,y)(x,y)必须xyxyxy#xff0c;也就是说必须…传送门
文章目录题意思路题意
给你nnn个点(xi,yi)(x_i,y_i)(xi,yi)每个点有个价值cic_ici现在你可以框一个正方形要求左下角和右上角的坐标(x,y)(x,y)(x,y)必须xyxyxy也就是说必须在xyxyxy这条直线上。现在你可以框一个正方形被正方形框到的点算入总价值求能得到的最大的总价值。总价值被框的点的价值−-−正方形的长度。
思路
在二维平面画了很多都没找到规律看了题解才知道这个题有一个很巧妙的转换设正方形左下角坐标(x,x)(x,x)(x,x)右上角坐标(y,y)(y,y)(y,y)对于(xi,yi)(x_i,y_i)(xi,yi)如果他能被这个正方形包含在内部那么必须满足xmin(xi,yi)max(xi,yi)yxmin(x_i,y_i)max(x_i,y_i)yxmin(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已经知道了我们可将其移动一下变成xitree(xi,1e9)max−rx_itree(x_i,1e9)_{max}-rxitree(xi,1e9)max−r那么rrr怎么办呢我们可以在建线段树的时候将初始值置为其rrr即可查询的时候需要加上左端点。 让后可以离散化一下比较好些当然也可以动态开点 复杂度O(nlogn)O(nlogn)O(nlogn)
// Problem: F. Choose a Square
// Contest: Codeforces - Educational Codeforces Round 73 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1221/problem/F
// Memory Limit: 256 MB
// Time Limit: 6000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const LL inf0x3f3f3f3f3f3f3f3f;
const double eps1e-6;int n,se;
struct node {int X,Y,c;bool operator (const node x) const {return x.XX;}
}p[N];
vectorintv;
struct Node {int l,r;LL now,mx,lazy,id;
}tr[N2];int find(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()1;
}void pushup(int u) {if(tr[L].mxtr[R].mx) {tr[u].mxtr[L].mx;tr[u].idtr[L].id;} else {tr[u].mxtr[R].mx;tr[u].idtr[R].id;}
}void pushdown(int u) {LL lazytr[u].lazy; tr[u].lazy0;tr[L].lazylazy; tr[L].mxlazy;tr[R].lazylazy; tr[R].mxlazy;
}void build(int u,int l,int r) {tr[u]{l,r,0,0,0,0};if(lr) {tr[u].mx-v[l-1];tr[u].idv[l-1];return ;}build(L,l,Mid); build(R,Mid1,r);pushup(u);
}void change(int u,int l,int r,int c) {if(tr[u].lltr[u].rr) {tr[u].mxc; tr[u].lazyc;return;}pushdown(u);if(lMid) change(L,l,r,c);if(rMid) change(R,l,r,c);pushup(u);
}pairLL,int query(int u,int l,int r) {if(tr[u].lltr[u].rr) return {tr[u].mx,tr[u].id};pushdown(u);pairLL,int ans{-inf,0};if(lMid) ansmax(ans,query(L,l,r));if(rMid) ansmax(ans,query(R,l,r));return ans;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);LL ans0;int lmod,rmod;scanf(%d,n);for(int i1;in;i) {scanf(%d%d%d,p[i].X,p[i].Y,p[i].c);if(p[i].Xp[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(p1,p1n); sev.size();for(int i1;in;i) p[i].Xfind(p[i].X),p[i].Yfind(p[i].Y);build(1,1,se);for(int in;i1;i--) {int xxp[i].X;while(i1p[i].Xxx) change(1,p[i].Y,se,p[i].c),i--; i;pairLL,int nowquery(1,p[i].X,se);now.Xv[p[i].X-1];if(now.Xans) {ansnow.X;lv[p[i].X-1],rnow.Y;}}printf(%lld\n%d %d %d %d\n,ans,l,l,r,r);return 0;
}
/**/
