ST算法 ST算法是一个在线算法，它可以在O(nlogn)时间内进行预处理，然后在O(1)的时间内回答每个查询，假设现在的数组为arr[] = {1,3,6,7,4,2,5,9}，算法步骤如下： 一、...ST算法板子题，用java的同学要注意的就是把你所有会的输入输出优化全用上，不然会TLE 2333.... import java.io.InputStreamReader; import java.util.Scanner
ST算法是基于倍增的动态规划算法。
ST表 ST表的功能很简单 它是解决RMQ问题(区间最值问题)的一种强有力的工具 它可以做到O(nlogn)预处理，O(1)查询最值 算法 ST表是利用的是倍增的思想 拿最大值来说 我们用Max[i][
ST 表是个好东西，虽然前些天 ldq 学长已经讲完啦，但是那天他讲了那么多，让智商受限的我完全没有全部接受，选择性的扔掉了一部分（其实不舍的扔，记不住QAQ）。...ST 表最简单的应用就是查询区间最大值（或着最小值，这里以最大值为例），它（单纯 ST 表自己）需要你先修改之后（如果有修改要求），得到一个确切数组之后，经过 O ( nlogn ) 的预处理，然后就可以做到...ST 表的预处理操作： 对于一个有 n 个数的 a [ n ] ，如果需要用一个二维数组 f [ n ] [ t ] ，其中 n 是指的用这 n 个数，t 是指的 n 最大是 2 的多少次幂，...不能一个个的去枚举吧，那样的话，还不如用线段树（我是这么想得H_H），当然啦，这个问题在 ST 表被想出来的时候就解决啦，那就是递推得到，先看一下代码（不理解没关系，慢慢看）。...ST 表在预处理时采用倍增和DP思想。 ST 表查询操作： 关于查询操作，想一想怎么样子可以做到 O ( 1 ) 查询的呢。
st_split::= ST_SPLIT "(" input "," blade ")"Copied!ST_SPLIT函数用于返回input几何对象被blade几何对象切割之后产生的几何对象。...示例SELECT st_astext(st_split(st_geomfromtext('linestring(1 1, 3 3)'), st_geomfromtext('point(2 2)')),...(st_split(st_geomfromtext('linestring(1 1, 4 4)'), st_geomfromtext('multipoint(2 2, 3 3)')), 0) split...(st_split(st_geomfromtext('linestring(1 1, 4 4)'), st_geomfromtext('polygon((0 0, 0 2, 2 2, 2 0, 0 0)...(st_split(st_geomfromtext('polygon((0 0, 0 2, 2 2, 2 0, 0 0))'), st_geomfromtext('linestring(1 -1, 1
st_extent::= ST_EXTENT "(" geomFiled ")"ST_EXTENT函数的功能是返回一个包围一组geometry的二维边界框，是一个聚合函数，返回类型是BOX2D。...geometry通用表达式，其值必须为有效的ST_GEOMETRY类型的数据。本函数遵守如下规则：当输入的一组geometry全部为NULL或全部为EMPTY时，该函数返回NULL。...创建表DROP TABLE IF EXISTS geom;CREATE TABLE geom(id INT, col_geom GEOMETRY);INSERT INTO geom VALUES(1, ST_GEOMFROMTEXT...('POINT(1 2)'));INSERT INTO geom VALUES(1, ST_GEOMFROMTEXT('LINESTRING(3 4, 5 2)'));-- 2.创建BOX2D的输出函数...box.ymin || ' ' || box.ymax || ')';RETURN res;END;/ -- 3.通过聚合函数对表中的GEOMETRY进行聚合SELECT BOX2D_OUT(ST_EXTENT
st_relate::= ST_RELATE "(" geometry1 "," geometry2 [ "," boundaryNodeRule ] ")"Copied!...示例（单机HEAP表）--ST_GEOMFROMTEXT函数会根据给定的WKT和SRID返回一个ST_GEOMETRY数据SELECT ST_Relate(ST_GeomFromText('LINESTRING...(2 2, 1 1, 3 3)'), ST_GeomFromText('LINESTRING(3 5, 2 2, 3 3)')) FROM DUAL;ST_RELATE(ST_GEOMFRO...(ST_GeomFromText('POINT(1 2)'), ST_GeomFromText('LINESTRING(3 5, 2 2, 3 3)')) FROM DUAL;ST_RELATE(ST_GEOMFRO...(ST_GeomFromText('POLYGON((2 2, 2 4, 4 4, 4 2, 2 2))'), NULL) FROM DUAL;ST_RELATE(ST_GEOMFRO
st_distance::= ST_DISTANCE "(" geometry1 "," geometry2 ")"Copied!...示例（单机HEAP表）SELECT ST_Distance(ST_GeomFromText('linestring(-72.1523 42.6343, -72.4524 42.2872)', 4326)...---------------- 0SELECT ST_Distance(ST_Point(-72.1235, 42.3521, 4326), ST_GeomFromText...(ST_Point(-72.1235, 42.3521, 4326), ST_GeomFromText('polygon((-72.1260 42.45, -72.123 42.1546, -72.12...(ST_GeomFromText('linestring(-72.1235 42.3521, -72.1523 42.6343)', 4326), ST_GeomFromText('linestring
st_length::= ST_LENGTH "(" geometry ")"ST_LENGTH函数根据输入的geometry，返回对应的长度数据。...geometry通用表达式，其值必须为有效的ST_GEOMETRY类型的数据，遵循如下规则：geometry是LINESTRING、MULTILINESTRING或GEOMETRY COLLECTION...示例（单机HEAP表）SELECT ST_Length(ST_GeomFromText('linestring(-72.1235 42.3521, -72.1523 42.6343)', 4326))...res FROM dual; RES----------- 3.144E+004SELECT ST_Length(ST_GeomFromText('linestring(5000 6789
st_geomfromgeojson::= ST_GEOMFROMGEOJSON "(" geojson ")"ST_GEOMFROMGEOJSON函数根据输入的geojson，返回该geojson对应的...ST_GEOMETRY类型数据。...示例（单机HEAP表）-- emptySELECT ST_AsText(ST_GeomFromGeoJSON('{"type":"Point","coordinates":[]}')) res FROM...(ST_GeomFromGeoJSON(ST_AsGeoJSON(ST_GeomFromText('POINT(1 1)')))) res FROM DUAL;RES...(ST_GeomFromGeoJSON('{"type":"GeometryCollection","geometries":[{"type":"Point","coordinates":[100.0,0.0
st_issimple::= ST_ISSIMPLE "(" geometry ")"Copied!...ST_ISSIMPLE函数根据输入的geometry，返回该geometry是否简单，如该geometry符合简单定义，则返回TRUE，否则返回FALSE。...有效定义可参考ST_ISVALID函数描述。MULTIPOLYGON：其中所有元素均为简单时，该数据为简单；否则不为简单。...示例（单机HEAP表）SELECT ST_IsSimple(ST_GeomFromText('POLYGON((1 2, 3 4, 5 6, 1 2))')) res FROM DUAL;RES----...---------------- falseSELECT ST_IsSimple(ST_GeomFromText('POLYGON((1 2, 3 3, 5 6, 1 2))')) res FROM DUAL
st_covers::= ST_COVERS "(" geometry1 "," geometry2 ")"ST_COVERS函数的功能是判断geometry1是否覆盖geometry2，即如果geometry2...geometry通用表达式，其值必须为有效的ST_GEOMETRY类型的数据。输入的geometry1和geometry2须具有相同的空间参考系标识号（SRID）。...示例（单机HEAP表）--ST_GEOMFROMTEXT函数会根据给定的WKT和SRID返回一个ST_GEOMETRY数据SELECT ST_Covers(ST_GeomFromText('POLYGON...true SELECT ST_Covers(ST_GeomFromText('POINT...- false SELECT ST_Covers(ST_GeomFromText('POLYGON((2 2, 2 4, 4 4, 4 2, 2 2))'), NULL) res
st_dwithin::= ST_DWITHIN "(" geometry1 "," geometry2 "," distance ")"ST_DWITHIN函数的功能是判断geometry1与geometry2...geometry通用表达式，其值必须为有效的ST_GEOMETRY类型的数据。输入的geometry1和geometry2须具有相同的空间参考系标识号（SRID）。...示例--返回两个geometry之间的距离SELECT ST_Distance(ST_GeomFromText('POINT(0 0)'), ST_GeomFromText('POINT(3 4)'))...res FROM DUAL;RES----------- 5.0E+000--两个geometry之间的距离在指定的distinct内SELECT ST_DWithin(ST_GeomFromText...--两个geometry之间的距离不在指定的distinct内SELECT ST_DWithin(ST_GeomFromText('POINT(0 0)'), ST_GeomFromText('POINT
::= ST_GEOMCOLLFROMTEXT "(" wkt [ "," srid ] ")"Copied!...ST_GEOMCOLLFROMTEXT函数根据给定的wkt（Well-Known Text）和srid返回一个ST_GEOMETRY类型数据，如果传入的WKT不是GEOMETRYCOLLECTION，则返回...入参wkt和srid的规格与ST_GEOMFROMTEXT函数相同。当输入的参数存在NULL时，函数返回NULL，空串作为NULL处理。...示例（单机HEAP表）SELECT ST_AsText(ST_GeomCollFromText('GEOMETRYCOLLECTION EMPTY')) res FROM DUAL;RES-------...(ST_GeomCollFromText('GEOMETRYCOLLECTION(POINT(1 2), LINESTRING(1 3, 4 1))'), 0) res FROM DUAL;RES---
st_overlaps::= ST_OVERLAPS "(" geometry1 "," geometry2 ")"ST_OVERLAPS函数的功能是判断两个Geometry相交并具有相同的维度，但彼此之间不完全包含...geometry通用表达式，其值必须为有效的ST_GEOMETRY类型的数据。输入的geometry1和geometry2须具有相同的空间参考系标识号（SRID）。...示例（单机HEAP表）--ST_GEOMFROMTEXT函数会根据给定的WKT和SRID返回一个ST_GEOMETRY数据SELECT ST_Overlaps(ST_GeomFromText('LINESTRING...(2 2, 1 1, 3 3)'), ST_GeomFromText('LINESTRING(3 5, 2 2, 3 3)')) res FROM DUAL;RES ------------------...-- true SELECT ST_Overlaps(ST_GeomFromText('LINESTRING(2 2, 1 1, 3 3)'), ST_GeomFromText
st_makepoint::= ST_MAKEPOINT "(" x "," y [ "," z [ "," m ] ] ")"ST_MAKEPOINT函数根据输入的x、y和可选的z和m，返回对应坐标的...示例（单机HEAP表）SELECT ST_AsText(ST_MakePoint(1, 2), 0) res FROM DUAL;RES...---------------------------- POINT (1 2) SELECT ST_AsText...(ST_MakePoint(1, 2, 3), 0) res FROM DUAL;RES -----------------...(ST_MakePoint(1, 2, 3, 4), 0) res FROM DUAL;RES --------------
[N][N];//st[i][j]=gcd(i ~ i+(1<<j)-1) int main(){ int n,m,l,r; scanf("%d%d",&n,&m); for(int i=1;i...[2]=1; for(int i=3;i<=n;i++){ Log[i]=Log[i/2]+1; } //单个元素的最大公约数是自己 for(int i=1;i<=n;i++){ st...[i][0]=a[i]; } //预处理 ST表 for(int j=1;(1<<j)<=n;j++){ for(int i=1;i+((1<<j)-1)<=n;i++){ st[i][...j]=gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]); } } while(m--){ scanf("%d%d",&l,&r); int len=r-l+1;...int Lg=Log[len]; //求区间内的最大公约数 printf("%d\n",gcd(st[l][Lg],st[r-(1<<Lg)+1][Lg])); } return 0;
st_multi::= ST_Multi "(" geometry ")"ST_MULTI函数用于返回输入的Geometry对象所对应的Geometry Collection类型。...geometry通用表达式，其值必须为有效的ST_GEOMETRY类型的数据。...(st_multi(st_geomfromText('point(0 0)', 4326)), 0) multi FROM dual;MULTI-----------------------------...-----------------------------------MULTIPOINT (0 0)SELECT st_astext(st_multi(st_geomfromText('linestring...---------------------------------------------MULTIPOINT (0 0, 1 1)SELECT st_astext(st_multi(st_geomfromText
st_linefromtext::= ST_LINEFROMTEXT "(" wkt [ "," srid ] ")"ST_LINEFROMTEXT函数根据给定的wkt（Well-Known Text）...和srid返回一个ST_GEOMETRY类型数据，如果传入的WKT不是LINESTRING，则返回NULL。...入参wkt和srid的规格与ST_GEOMFROMTEXT函数相同。当输入的参数存在NULL时，函数返回NULL，空串作为NULL处理。...示例（单机HEAP表）SELECT ST_AsText(ST_LineFromText('LINESTRING EMPTY')) res FROM DUAL;RES-------------------...(ST_LineFromText('LINESTRING(1 1, 3 1)'), 0) res FROM DUAL;RES---------------------------------------
::= ST_GEOMFROMEWKB "(" ewkb ")"ST_GEOMFROMEWKB函数根据给定的ewkb（Extended Well-Known Binary）返回一个ST_GEOMETRY...输入的ewkb如果前面的字符已经构成了一个有效的ST_GEOMETRY类型数据，并且后面还有其他有效字符，则只会生成前面的有效的ST_GEOMETRY类型数据。...示例（单机HEAP表）SELECT ST_AsText(ST_GeomFromEwkb('0101000020E6100000000000000000F03F0000000000000040')) res...---------------------------- POINT (1.000000000000000 2.000000000000000) SELECT ST_Srid...(ST_GeomFromEwkb('0101000020E6100000000000000000F03F0000000000000040')) res FROM DUAL; RES --
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储
