精华内容
下载资源
问答
  • 动态线段树AC代码 http://acm.hdu.edu.cn/showproblem.php?pid=1199 因为昨天做了一道动态线段树的缘故,今天遇到了这题没有限制范围的题就自然而然想到了动态线段树的解法,写完看题解发现原来只要离散化就好了...

    附动态线段树AC代码

    http://acm.hdu.edu.cn/showproblem.php?pid=1199

    因为昨天做了一道动态线段树的缘故,今天遇到了这题没有限制范围的题就自然而然想到了动态线段树的解法,写完看题解发现原来只要离散化就好了(干。。),总结了一下这题和昨天hdu5367的区别在于,虽然都是两题范围超级大的线段树,但是昨天的强制要求在线求解,只能选择空间复杂度更大一些的动态线段树来求解,而今天的这题可以选择离线操作,因而可以采用先读入所有输入,离散化之后建树的方法来操作。下次遇到这样的题还是应当优先考虑离散化。

     

    在一个全部涂黑色的条子上涂上一些白色或黑色的片段,问最大白色片段。

    仅仅从线段树维护节点的角度上来看很简单,维护最大白色片段,左边最大白色片段,右边最大白色片段就好了。

    由于条子的长度长达1-INT_MAX;

    采用离散化,或者像我一样失了智去用动态线段树的方法,也能AC

    #include <map>
    #include <set>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    #define For(i, x, y) for(int i=x; i<=y; i++)  
    #define _For(i, x, y) for(int i=x; i>=y; i--)
    #define Mem(f, x) memset(f, x, sizeof(f))  
    #define Sca(x) scanf("%d", &x)
    #define Scl(x) scanf("%lld",&x);  
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x);  
    #define CLR(u) for(int i = 0; i <= N ; i ++) u[i].clear();
    #define LL long long
    #define ULL unsigned long long  
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second 
    using namespace std;
    typedef vector<int> VI;
    const double eps = 1e-9;
    const int maxn = 2010;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7; 
    inline int read()
    {
        int now=0;register char c=getchar();
        for(;!isdigit(c);c=getchar());
        for(;isdigit(c);now=now*10+c-'0',c=getchar());
        return now;
    }
    int N,M;
    struct Tree{
        LL sum;    //最大连续 
        LL lsum;   //左连续 
        LL rsum;   //右连续 
        int lt;
        int rt;
        int lazy;
        void init(){
            lsum = rsum = sum = lt = rt = 0;
            lazy = -1;
        }
    }tree[maxn * 60];
    int tot;
    void check(int &t){
        if(t) return;
        t = ++tot;
        tree[t].init();
    }
    void add(int &t,LL L,LL R,int v){
        if(v){
            tree[t].sum = tree[t].lsum = tree[t].rsum = R - L + 1;
        }else{
            tree[t].sum = tree[t].lsum = tree[t].rsum = 0;
        }
        tree[t].lazy = v;
    }
    void Pushdown(int& t,LL L,LL R){
        if(tree[t].lazy == -1) return;
        int &lt = tree[t].lt; int &rt = tree[t].rt;
        LL M = (L + R) >> 1;
        check(lt); check(rt);
        add(lt,L,M,tree[t].lazy);
        add(rt,M + 1,R,tree[t].lazy);
        tree[t].lazy = -1;
    }
    void Pushup(int t,LL L,LL R){
        int &ls = tree[t].lt; int &rs = tree[t].rt;
        LL M = (L + R) >> 1; 
        check(ls); check(rs);
        tree[t].sum = max(tree[ls].sum,tree[rs].sum);
        tree[t].sum = max(tree[t].sum,tree[ls].rsum + tree[rs].lsum);
        tree[t].lsum = tree[ls].lsum;
        if(tree[ls].lsum == M - L + 1){
            tree[t].lsum = tree[ls].lsum + tree[rs].lsum;
        } 
        tree[t].rsum = tree[rs].rsum;
        if(tree[rs].rsum == R - M){
            tree[t].rsum = tree[rs].rsum + tree[ls].rsum;
        }
    }
    void update(int &t,int q1,int q2,LL L,LL R,int v){
        check(t);
        if(q1 <= L && R <= q2){
            add(t,L,R,v);
            return;
        }
        Pushdown(t,L,R);
        LL m = (L + R) >> 1;
        if(q1 <= m) update(tree[t].lt,q1,q2,L,m,v);
        if(q2 > m) update(tree[t].rt,q1,q2,m + 1,R,v);
        Pushup(t,L,R);
    }
    LL Left,Right;
    void query(int t,LL L,LL R){
        if(L == R){
            Left = L;
            Right = R;
            return;
        }
        check(tree[t].lt); check(tree[t].rt);
        int ls = tree[t].lt; int rs = tree[t].rt;
        LL M = (L + R) >> 1;
        if(tree[ls].sum == tree[t].sum) query(ls,L,M);
        else if(tree[rs].sum == tree[t].sum) query(rs,M + 1,R);
        else{
            Left = M - tree[ls].rsum + 1;
            Right = M + tree[rs].lsum;
            return;
        }
     
    }
    int main()
    {
        while(~Sca(N)){
            LL L = 1; LL R = 2147483647;
            tot = 0;
            int root = 0;
            update(root,L,R,L,R,0);
            For(i,1,N){
                LL l,r;
                char op[3];
                scanf("%lld%lld%s",&l,&r,&op);
                if(op[0] == 'w'){
                    update(root,l,r,L,R,1);
                }else{
                    update(root,l,r,L,R,0);
                }
            }
            if(!tree[root].sum){
                puts("Oh, my god");
                continue;
            }
            query(root,L,R);
            printf("%lld %lld\n",Left,Right);
        }
        return 0;
    }
     

     

    转载于:https://www.cnblogs.com/Hugh-Locke/p/9499713.html

    展开全文
  • leaflet实现动态线段

    2020-05-14 16:31:44
    } 三、画线 //清楚上一次画的线段 if (gPath) { gMap.removeLayer(gPath); } var longLatList =[[****,****],[*****,****]];//经纬度数组 var antPath = L.polyline.antPath; gPath = antPath(longLatList, { ...

    在这里插入图片描述

    一、引用Leaflet脚本样式,和Leaflet Ant Path 插件

    Leaflet:https://leafletjs.com/download.html
    Leaflet Ant Path:https://github.com/rubenspgcavalcante/leaflet-ant-path

    <link href="~/Scripts/leafletjs/1.4.0/leaflet.css" rel="stylesheet" />
    <script src="~/Scripts/leafletjs/1.4.0/leaflet.js"></script>
    <script src="~/Scripts/leafletjs/1.4.0/leaflet-ant-path.js"></script>
    

    二、地图初始化

     /**
           * 地图初始化
           */
            function mapInit() {
                var amapNormalUrl = '/api/Map/GetMap?type=783085212&zoom={z}&x={x}&y={y}';
                var amapNormalLayer = new L.TileLayer(amapNormalUrl, {
                    minZoom: 1,
                    maxZoom: 18,
                    attribution: ''
                });
    
                var mapCenter = new L.LatLng(****,****);
                gMap = new L.Map('MapContainer', {
                    center: mapCenter,
                    zoom: 16,
                    minZoom: 1,
                    maxZoom: 18,
                    layers: [amapNormalLayer]
                });
            }
    

    三、画线

    //清楚上一次画的线段
    if (gPath) {
                    gMap.removeLayer(gPath);
                }
    var longLatList =[[****,****],[*****,****]];//经纬度数组
                            var antPath = L.polyline.antPath;
                            gPath = antPath(longLatList, {
                                "paused": false,     //暂停  初始化状态
                                "reverse": false,  //方向反转
                                "delay": 3000,    //延迟,数值越大效果越缓慢
                                "dashArray": [10, 20], //间隔样式
                                "weight": 3,    //线宽
                                "opacity": 0.5,  //透明度
                                //"color": "#0000FF", //颜色
                                //"pulseColor": "#FFFFFF"  //块颜色
                            });
                            gPath.addTo(gMap); 
    
                            // 缩放地图到折线所在区域
                            gMap.fitBounds(gPath.getBounds());
                            
    

    有想换工作的同学可以找我内推哦不低于15k(前端,java,测试)

    在这里插入图片描述

    展开全文
  • poj 2528 Mayor's posters(动态线段树) 题目大意: 给定一个 1 ~ 10000000 的区间,然后有N次操作(N ),第i次操作是将 l~r 区间覆盖为i。问最后一共有多少种有颜色。 解题思路: 一开始想到了离散化,但是想了一想...

    传送门:点击打开链接


    题目大意:

    给定一个 1 ~ 10000000 的区间,然后有N次操作(N <= 10000),第i次操作是将 l~r 区间覆盖为i。问最后一共有多少种有颜色。


    解题思路:

    一开始想到了离散化,但是想了一想感觉有点麻烦 然后就问专职搞数据结构的队友。然后他说了 动态线段树。思路如下:

    定义一个ID。然后 根节点1表示掌管1-MAXN颜色的区间。然后每次都是动态的建树。当一个区间的左子区间还不存在时。建立它,并且记录下每个区间的左子区间和右子区间的ID.那么就可以搞了。

    最后再用一个DFS 用SET来记录一共出现了多少种颜色。


    注意:

    当将一个区间的左子区间和右子区间被它更新之后时,一定要把他清零。

    还有那个maxn。开始是未知的。


    #include <set>
    #include <cstdio>
    using namespace std;
    #define maxn 2000000
    int lson[maxn],rson[maxn],color[maxn];
    int cnt,root;
    void build()
    {
        cnt = 2;
        root = 1;
        lson[root] = 0;
        rson[root] = 0;
        color[root] = 0;
    }
    
    void pushdown(int id)
    {
        if(!lson[id])
        {
            lson[id] = cnt++;
            lson[lson[id]] = 0;
            rson[lson[id]] = 0;
            color[lson[id]] = 0;
        }
        if(!rson[id])
        {
            rson[id] = cnt++;
            lson[rson[id]] = 0;
            rson[rson[id]] = 0;
            color[rson[id]] = 0;
        }
        if(color[id])
        {
            color[lson[id]] = color[id];
            color[rson[id]] = color[id];
            color[id] = 0;
        }
    }
    
    void op(int id,int ls,int rs,int l,int r,int c)
    {
        if(ls >= l && rs <= r)
        {
            color[id] = c;
            return;
        }
        pushdown(id);
        int mid = (ls+rs)>>1;
        if(l <= mid) op(lson[id],ls,mid,l,r,c);
        if(mid < r) op(rson[id],mid+1,rs,l,r,c);
    
    }
    set<int > ans;
    
    void dfs(int id)
    {
        if(color[id])
        {
            ans.insert(color[id]);
            return;
        }
        if(lson[id]) dfs(lson[id]);
        if(rson[id]) dfs(rson[id]);
    }
    
    
    int main()
    {
        int T;
        scanf("%d",&T);
        for(int ks = 1;ks <= T;ks++)
        {
            int n;
            scanf("%d",&n);
            ans.clear();
            build();
            for(int i = 1;i <= n;i++)
            {
                int l,r;
                scanf("%d %d",&l,&r);
                op(root,1,10000000,l,r,i);
            }
            dfs(root);
            printf("%d\n",ans.size());
        }
        return 0;
    }
    









    展开全文
  • 在Cesium中绘制动态线段 以下实现方法均属野路子。 理想中,可以扩展polylinegeometry增加一个customdata属性用于提交除位置外的其他顶点数据,类似于下文使用的color 计划实现类似于蚂蚁线的效果,在Cesium中翻看...

    在Cesium中绘制动态线段

    以下实现方法均属野路子。

    理想中,可以扩展polylinegeometry增加一个customdata属性用于提交除位置外的其他顶点数据,类似于下文使用的color

    计划实现类似于蚂蚁线的效果,在Cesium中翻看各种材质,没法发现满足条件的material或Appearance。那么只能自己手工实现了。

    在这里插入图片描述

    基本思路

    • 传递顶点时,附加每个顶点距线段起点的距离,用此距离来实现线段分段
    • shader中对传入的距离取模,即可实现分段绘制不通的颜色

    使用fabric

    查看了fabric的相关资料后,发现fabric只能自定义uniform变量,没有提供接口可以传递额外的顶点数据。Fabric仅是材质,想来不可能通过材质提交新的顶点数据。此路不通,但是可以使用uniform类型的变量

    如何提交除顶点外的其他顶点数据?

    看到PolylineGeometry可以额外提供顶点颜色,此时考虑可以将顶点距离通过每个顶点的color传入到shader中。

    传入的color为归一化后的数据,因此计算距离时,需要将距离归一化到0~1之间。

    最终解决方案

    PolylineColorAppearance + Fabric

    PolylineColorAppearance中提交自己的fragmentShaderSource,此处需要注意,同Material不同,Material中需要重写获取材质方法,但是Appearance中需要完全替换main方法。

    创建Appearance后,将appearance的材质替换为fabric,此时可以通过color获取每个顶点对应的距离。

    此时已经可以分段绘制线段了。

    分段的线要动起来,可以传入Cesium绘制的时间,通过preRender事件可以获取绘制的起始事件,当前时间减起始时间即为已经开始绘制的时间。

    uniform变量如何传递??

    都知道fabric中可以指定uniforms属性来传递额外的变量,而且uniforms中的变量均为cesium生成对应的glsl代码,这一步过程暂不想去改动。将appearance的material修改后,通过调试发现,cesium将一次生成uniforms中的uniform变量的声明,但是会将变量名称做修改,即添加变量的序号作为尾缀,如

    fabric:{
                uniforms:{						//glsl中对应的变量名
                  u_itime:10.0,					//u_itime_0
                  u_trailpercent:0.3,			//u_trailpercent_1
                  u_trailmovespeed:5.0/50.0,	//u_trailmovespeed_2
                }
              }
    

    到这里就没有问题了。。。。。

    shader里实现分段,使用mod即可,拖尾效果使用smoothstep实现,shader代码如下:

    precision highp float;
    
    varying vec4 v_color;
    
    void main(){
        float r=v_color.r-u_itime_0*u_trailmovespeed_2;
        float dist=smoothstep(0.0,u_trailpercent_1,mod(r,u_trailpercent_1));
        //红白混合
        gl_FragColor=mix(vec4(1.0,0.0,0.0,1.0),vec4(1.0),dist);
    }
    

    完整代码,可在sandcastle中运行

    var viewer = new Cesium.Viewer("cesiumContainer");
    var scene = viewer.scene;
    
    var material=new Cesium.Material({
      fabric:{
        uniforms:{
          u_itime:10.0,
          u_trailpercent:0.3,
          u_trailmovespeed:5.0/50.0,
        }
      }
    });
    
    var primitive = new Cesium.Primitive({
      geometryInstances: new Cesium.GeometryInstance({
        geometry: new Cesium.PolylineGeometry({
          positions: Cesium.Cartesian3.fromDegreesArray([
            0.0,
            6.0,
            5.0,
            6.0,
            7.0,
            8.0,
          ]),
          width: 50.0,
          vertexFormat: Cesium.PolylineColorAppearance.VERTEX_FORMAT,
          colorsPerVertex: true,
          colors: [
            new Cesium.Color(0.1,0.0,0.0,1.0), 
            new Cesium.Color(0.7,0.0,0.0,1.0),
            new Cesium.Color(1.0,0.0,0.0,1.0)
          ],
        }),
      }),
      appearance: new Cesium.PolylineColorAppearance({
        translucent: false,
        fragmentShaderSource: `precision highp float;
    
        varying vec4 v_color;
    
        void main(){
          float r=v_color.r-u_itime_0*u_trailmovespeed_2;
          float dist=smoothstep(0.0,u_trailpercent_1,mod(r,u_trailpercent_1));
          gl_FragColor=mix(vec4(1.0,0.0,0.0,1.0),vec4(1.0),dist);
        }
        `,
      }),
    });
    
    primitive.appearance.material=material;
    
    scene.primitives.add(primitive);
    
    scene.preRender.addEventListener(function(s,t){
      let elaspTime=Cesium.JulianDate.now().secondsOfDay-t.secondsOfDay;
      primitive.appearance.material.uniforms.u_itime=elaspTime;
    });
    

    现有问题

    拐角处,被弯折

    图中,中间的白色色带明显未沿线方向,而是有一处弯折,这是由于,cesium将线扩充为面时,是沿顶点法线方向两侧扩充,但是扩充后的两个点对应的线的距离是一样的,但是实际长度不同明显下方拐角处的点要比上放的点的距离要长才符合实际情况,导致颜色变化时不一致。

    在这里插入图片描述

    如果纯用fragmentshader来写是可以避免弯折的情况的,但是目前还不知道如何将完整的canvas绘制到cesium上。对用shahder绘制线感兴趣的,可以参考这篇文章,采用距离场方式绘制线段。

    后续有时间通过理想方式实现一遍。

    PS: 有其他实现方法的欢迎留言

    展开全文
  • · 博主是⑨  · 补充 : 蒟蒻  · 语文老师死得早 ... Delayyy君竟然用splay把数据水过了……Rank 1无压力... 于是就试着写个动态空间的线段树.  在屏屏哥的证明下, 节点的个数是接近于 2n + nlogs - nlog
  • 线段动态问题

    2015-07-17 14:51:29
    如何解决动态范围求和问题,如何简单地了解线段树。 附有模板以及习题
  • 动态开点线段

    千次阅读 2019-10-27 23:54:43
    线段动态开点 在一些计数问题中,线段树用于维护值域(一段权值范围),这样的线段树也称为权值线段树。为了降低空间复杂度,我们可以不建出整棵线段树的结构,而是在最初只建立一个根节点,代表整个区间,当需要...
  • 线段线段

    2018-08-02 20:02:00
    X轴上有N条线段,每条线段包括1个起点和终点。线段的重叠是这样来算的,(10,20)(12,25)的重叠部分为12201220。 给出N条线段的起点和终点,从中选出2条线段,这两条线段的重叠部分是最长的。输出这个最长的距离...
  • 针对未知环境知识表达问题, 模拟人类思维处理空间知识, 提出一种基于灰朦胧集动态演化的线段特征提取方法. 该方法在具有几何约束的环境中, 通过灰朦胧集动态演化形成不同认知阶段表达, 逐步消除信息中的不确定性, ...
  • 线段动态开点

    2019-01-23 00:33:00
    在一些计数问题中,线段树用于维护值域(一段权值范围)...采用这种方法维护的线段树称为动态开点的线段树。动态开点的线段树抛弃了完全二叉树父节点的2倍编号规则,改为使用变量记录左右子节点的编号(相当于指针)。同...
  • 很好的算法ppt 线段动态规划 黑书
  • 采用这种方法维护的线段树称为动态开点线段树。动态开点线段树抛弃了完全二叉树父子结点二倍的编号原则,改为用变量记录左右子节点编号 建立线段树code struct Tree{ int l, r; int dat; }tree[MAXN
  • 线段动态开点

    2019-08-27 13:46:53
    动态开点的线段树不再使用完全二叉树父子节点的二倍编号规则, 而是用变量记录左右节点的编号。 例题: P1908 逆序对 (这题正常应该用离散化做) code: #include<cstdio> #include<cst...
  • 注意:动态建立线段树pushdown和pushup等操作,一定要先检查节点是否存在 WA了无数次,RE了无数次,之后无奈看了某牛题解#include #include #include #include #include <map>using namespace std; #define ...
  • 动态开点线段树学习笔记 前言 这篇博客只是为了后面主席树做铺垫的,而且动态开点线段树非常的简单,所以就讲的比较少。 正文 我们都知道,普通的线段树的空间是4倍,因为会有很多不需要的节点,那么动态开点线段树...
  • 动态开点线段树_TODO

    2021-05-04 16:55:42
    catalogbase base 动态开点线段树,与 “非单调 区间min/max” https://blog.csdn.net/weixin_42712593/article/details/116402036
  • 浅谈动态开点线段

    千次阅读 2018-11-15 15:49:27
    可惜突然发现动态开点线段树不会了。。。。 发挥大胆猜想,不用求证的精神:你们都会线段树 众所周知:线段树空间复杂度是O4*n,这就不用证,因为我菜 那当n很大,操作正常时,如果像正常的线段树一样(记左儿子...
  • 本文主要介绍在OSGEarth中绘制随模型位置变化而动态移动的线段,即两个三维模型通过线段进行连接,在模型移动的过程中,连接的线段跟着模型做相应的位移。 一、编写Callback #pragma once class UpdateLink :...
  • 题意:对于一个1-n的序列,有两种操作,第一种更改...题解:我们对每个位置的数建一颗区间01线段树,那么我们动态开点,注意这里有多个根,也就是说有很多颗线段树。那么我们可以维护五个值:val,len,sumL,sumR,sum...
  • 动态开点线段树+权值线段树概述

    千次阅读 2018-03-28 16:15:56
    一开始觉得什么动态开点啥的都特别叼。实际上并没有什么,就是在空间不够的情况下,把不需要的节点变成虚点就好了,具体什么意思,我们来看一道题:P1908 逆序对 题目描述 猫猫TOM和小老鼠JERRY最近又较量上了,...
  • 动态开点的线段树也是一个线段树,也可以完成普通线段树的区间查询,也可以采用懒标记的方法区间修改。但是需要注意的是,在查询或者修改的函数中,需要将根节点代表的区间写入形参。根据参数中的根区间确定子区间。...
  • Description quailty和tangjz正在玩一个关于线段的游戏。在平面上有n条线段,编号依次为1到n。其中第i条线段的两端点坐 标分别为(0,i)和(1,p_i),其中p_1,p_2...然后tangjz必须拿走所有剩下的线段,若有两条线段...
  • 前言线段树,是一个很好用...于是就出现了线段树的动态开点写法基本思想与普通的线段树相同,动态开点线段树只是一开始每一个节点都没有,insert的时候,如果遇到节点是空的,那么就声明这个点,询问的时候只访问询问的
  • 动态开点线段树  阅读本篇请先学习线段树。  动态开点线段树是一类特殊的线段树,与普通的线段树不同的是,每一个节点的左右儿子不是该点编号的两倍和两倍加一,而是现加出来的。  我们用lson[u]记录u的左儿子...
  • HDU - 6183 动态开点线段树 题目链接 考虑对每种颜色都沿y轴建立线段树,维护区间点的x坐标的最小值。 线段树需要动态开点不然会mle #include &amp;amp;amp;lt;algorithm&amp;amp;amp;gt; #include &amp...
  • 题目分析 【提示】您已获得新技能:动态开点线段树 这道题,如果没有只能留宿于信仰相同的城市...所谓动态开点线段树,就是你的编号不能和普通线段树一样,x的儿子是x∗2x∗2x*2和x∗2+1x∗2+1x*2+1,而应该新编号...
  • 那么反过来想,我们能否建立一个可以动态分配空间的线段树,把点分给我们实际上使用的位置,这样的话当点的个数不算太多时,我们就可以省下大量的空间,同时又满足我们解决问题 二、过程分析 以存入数列{5、4、2、6...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 29,280
精华内容 11,712
关键字:

动态线段