网站管理登录系统,北京网站域名备案查询,商城app有哪些,杭州网页设计公司招聘题目链接#xff1a;BZOJ 洛谷\(O(n^2)\)DP很好写#xff0c;对于当前的i从之前满足条件的j中选一个最大值,\(dp[i]d[j]1\) for(int j1; ji; j)if(a[j]minv[i]maxv[j]a[i])//序列只会变换一次 dp[i]max{dp[j]1}; 转移要满足两个条件#xff1a;\(a[j]…题目链接BZOJ 洛谷\(O(n^2)\)DP很好写对于当前的i从之前满足条件的j中选一个最大值,\(dp[i]d[j]1\) for(int j1; ji; j)if(a[j]minv[i]maxv[j]a[i])//序列只会变换一次 dp[i]max{dp[j]1}; 转移要满足两个条件\(a[j]minv[i]\ \\\ maxv[j]a[i]\) 一个二维偏序问题CDQ、树套树都可以。 拿\(minv[x]\)和\(a[y]\)作为两个坐标轴\(dp[j]\)表示其上一点\((A[j],maxv[j])\). 这样就成了一个二维平面可以向其中插入一些点dp[i]询问一个矩形区域(也是一段前缀)中某点最大值 线段树套线段树 树状数组套线段树都可做 复杂度\(O(nlog^2n)\) 后者时间还可以树状数组套线段树 //企图二维树状数组 但动态开点的话 中间一段没有的区间会中断y方向的Query..
#includecstdio
#includecctype
#includealgorithm
#define gc() getchar()
#define now node[rt]
#define lson l,m,node[rt].ls
#define rson m1,r,node[rt].rs
#define lb(x) ((x)-(x))
const int N1e55;int n,m,A[N],minv[N],maxv[N],MaxV,MaxA;
namespace Tree_2D
{struct Seg_Tree{struct Node{int maxv,ls,rs;}node[N6];//还要再小点。。不然BZOJ上依旧MLE inline int new_Node(){static int cnt0;return cnt;}void Insert(int l,int r,int rt,int p,int v){if(!rt) rt new_Node();now.maxv std::max(now.maxv, v);if(lr){int mlr1;if(pm) Insert(lson,p,v);else Insert(rson,p,v);}}int Query(int l,int r,int rt,int L,int R){if(!rt) return 0;if(Ll rR) return now.maxv;int mlr1;if(Lm)if(mR) return std::max(Query(lson,L,R),Query(rson,L,R));else return Query(lson,L,R);return Query(rson,L,R);}}t;struct Bit{int root[N];void Insert(int p,int y,int v){while(pMaxV)t.Insert(1,MaxA,root[p],y,v), plb(p);}int Query(int p,int y){int res0;while(p)resstd::max(res,t.Query(1,MaxA,root[p],1,y)), p-lb(p);return res;}}t2D;
}
#undef now
inline int read()
{int now0;register char cgc();for(;!isdigit(c);cgc());for(;isdigit(c);nownow*10c-0,cgc());return now;
}int main()
{nread(),mread();for(int i1; in; i)maxv[i]minv[i]A[i]read(), MaxAstd::max(MaxA,A[i]);for(int x,y,i1; im; i)xread(), yread(), maxv[x]std::max(maxv[x],y), minv[x]std::min(minv[x],y);for(int i1; in; i) MaxVstd::max(MaxV,maxv[i]);int ans0;for(int v,i1; in; i){v Tree_2D::t2D.Query(minv[i],A[i]) 1;Tree_2D::t2D.Insert(A[i],maxv[i],v);ansstd::max(ans,v);}printf(%d,ans);return 0;
} 二维线段树 /*
BZOJ上直接MLE...洛谷P4093 4508ms(比Bit套Segtree慢3倍) 293.33MB
空间消耗比较大 写指针吧。。
*/
#includecstdio
#includecctype
#includealgorithm
#define gc() getchar()
#define lson l,m,rt-ls
#define rson m1,r,rt-rs
const int N1e55;int n,m,A[N],maxv[N],minv[N],MaxA,MaxV;
namespace Seg_Tree2D
{struct Node{int maxv;Node *ls,*rs;Node(): maxv(0),ls(NULL),rs(NULL) { }}pool[N7];//(logN)^2256(2^8) 开得小点吧要不空间会炸 struct Node2D{Node *root;Node2D *ls,*rs;Node2D(): root(NULL),ls(NULL),rs(NULL) { }}pool2D[N1],*root;inline Node *new_Node(){static int cnt0;return pool[cnt];}inline Node2D *new_Node2D(){static int cnt0;return pool2D[cnt];}Node2D *Build(int l,int r){Node2D *rt new_Node2D();if(lr){int mlr1;rt-ls Build(l,m);rt-rs Build(m1,r);}return rt;}int Query(int l,int r,Node *rt,int L,int R){if(!rt) return 0;if(Ll rR) return rt-maxv;int mlr1;if(Lm)if(mR) return std::max(Query(lson,L,R),Query(rson,L,R));else return Query(lson,L,R);return Query(rson,L,R);}int Query2D(int l,int r,Node2D *rt,int L,int R,int y1,int y2){if(Ll rR) return Query(1,MaxA,rt-root,y1,y2);int mlr1;if(Lm)if(mR) return std::max(Query2D(lson,L,R,y1,y2),Query2D(rson,L,R,y1,y2));else return Query2D(lson,L,R,y1,y2);return Query2D(rson,L,R,y1,y2);}void Insert(int l,int r,Node *rt,int p,int v){if(!rt) rt new_Node();//!rt-maxv std::max(rt-maxv, v);if(lr){int mlr1;if(pm) Insert(lson,p,v);else Insert(rson,p,v);}}void Insert2D(int l,int r,Node2D *rt,int p,int y,int v){Insert(1, MaxA, rt-root, y, v);if(lr){int mlr1;if(pm) Insert2D(lson,p,y,v);else Insert2D(rson,p,y,v);}}void Init(){root Build(1,MaxV);}int Query_Max(int l,int r,int y1,int y2){return Query2D(1,MaxV,root,l,r,y1,y2);}void Insert_Node(int x,int y,int v){Insert2D(1,MaxV,root,x,y,v);}
}
inline int read()
{int now0;register char cgc();for(;!isdigit(c);cgc());for(;isdigit(c);nownow*10c-0,cgc());return now;
}int main()
{nread(),mread();for(int i1; in; i)maxv[i]minv[i]A[i]read(), MaxAstd::max(MaxA,A[i]);for(int x,y,i1; im; i)xread(), yread(), maxv[x]std::max(maxv[x],y), minv[x]std::min(minv[x],y);for(int i1; in; i) MaxVstd::max(MaxV,maxv[i]);Seg_Tree2D::Init();int ans0;for(int v,i1; in; i){v Seg_Tree2D::Query_Max(1,minv[i],1,A[i]) 1;Seg_Tree2D::Insert_Node(A[i],maxv[i],v);ansstd::max(ans,v);}printf(%d,ans);return 0;
} 转载于:https://www.cnblogs.com/SovietPower/p/8440693.html
