精华内容
下载资源
问答
  • 区间离散化

    千次阅读 2014-06-07 20:16:02
    很多题要求对段改变,由于段端点范围比较大所以没办法开数组,但输入却很小,这个时候就要考虑用输入代替区间,因为区间很多部分完全不起作用,所以直接压缩区间,把端点记入排序后用1....n重新标记。 推荐:poj ...

    很多题要求对段改变,由于段端点范围比较大所以没办法开数组,但输入却很小,这个时候就要考虑用输入代替区间,因为区间很多部分完全不起作用,所以直接压缩区间,把端点记入排序后用1....n重新标记。

    推荐:poj Intervals(好题)

    hdu  2795

    展开全文
  • 离散化:把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。通俗的说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小。 例如: 原数据:1,999,100000,15;处理后:1,3,4,2; ...

    一、基本概念

    线段树:线段树基本概念

    离散化:把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。通俗的说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小。

    例如:

    原数据:1,999,100000,15;处理后:1,3,4,2;

    原数据:{100,200},{20,50000},{1,400};

    处理后:{3,4},{2,6},{1,5};

     

    二、算法

    思想:

    • 记录每个点的左端和右端,全部保存到一个数组a中并排序
    • 节点去重
    • 如果两个节点间距离大于1,添加一个中间节点
    • 再次对a排序
    • 在a中二分搜索原来每个点的左右端,将索引值保存在线段树中

    C++版本一

            scanf("%d",&n);
            int cnt = 0,len = 1;
            for(i=1;i<=n;i++)//记录头尾
            {
                sf("%d %d",&s1[i],&s2[i]);
                a[++cnt] = s1[i];
                a[++cnt] = s2[i];
            }
            sort(a+1,a+1+cnt);
    
            for(i=2;i<=cnt;i++)//去重
            {
                if(a[i]!=a[i-1]) a[++len] = a[i];
            }
    
            for(i=len;i>1;i--)//添加中间值
            {
                if(a[i]-a[i-1]>1) a[++len] = a[i]-1;
            }
            sort(a+1,a+1+len);
    
            for(i=1;i<=n;i++)
            {
                int l = BSearch(1,len,s1[i]);
                int r = BSearch(1,len,s2[i]);
                update(i,l,r,1,len,1);
            }

    三、例题

    http://poj.org/problem?id=2528(题解:https://blog.csdn.net/weixin_43272781/article/details/83420707

    http://acm.hdu.edu.cn/showproblem.php?pid=1199(题解:https://blog.csdn.net/weixin_43272781/article/details/83653497

    四、参考文章

    https://www.cnblogs.com/qlky/articles/5716796.html

    展开全文
  • hiho1079 : 离散化(线段树+区间离散化)

    千次阅读 2016-08-16 21:33:02
    #1079 : 离散化 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 小Hi和小Ho在回国之后,重新过起了朝7晚5的学生生活,当然了,他们还是在一直学习着各种算法~ 这天小Hi和小Ho所在的学校举办社团...

    #1079 : 离散化

    时间限制: 10000ms
    单点时限: 1000ms
    内存限制: 256MB

    描述

    小Hi和小Ho在回国之后,重新过起了朝7晚5的学生生活,当然了,他们还是在一直学习着各种算法~

    这天小Hi和小Ho所在的学校举办社团文化节,各大社团都在宣传栏上贴起了海报,但是贴来贴去,有些海报就会被其他社团的海报所遮挡住。看到这个场景,小Hi便产生了这样的一个疑问——最后到底能有几张海报还能被看见呢?

    于是小Ho肩负起了解决这个问题的责任:因为宣传栏和海报的高度都是一样的,所以宣传栏可以被视作长度为L的一段区间,且有N张海报按照顺序依次贴在了宣传栏上,其中第i张海报贴住的范围可以用一段区间[a_i, b_i]表示,其中a_i, b_i均为属于[0, L]的整数,而一张海报能被看到当且仅当存在长度大于0的一部分没有被后来贴的海报所遮挡住。那么问题就来了:究竟有几张海报能被看到呢?

    提示一:正确的认识信息量

    提示二:小Hi大讲堂之线段树的节点意义

    输入

    每个测试点(输入文件)有且仅有一组测试数据。

    每组测试数据的第1行为两个整数N和L,分别表示总共贴上的海报数量和宣传栏的宽度。

    每组测试数据的第2-N+1行,按照贴上去的先后顺序,每行描述一张海报,其中第i+1行为两个整数a_i, b_i,表示第i张海报所贴的区间为[a_i, b_i]。

    对于100%的数据,满足N<=10^5,L<=10^9,0<=a_i<b_i<=L。

    输出

    对于每组测试数据,输出一个整数Ans,表示总共有多少张海报能被看到。

    样例输入
    5 10
    4 10
    0 2
    1 6
    5 9
    3 4
    样例输出
    5
    这道题我们首先想到的就是用线段树做  可是发现数据特别大

    这时候就用到离散化了。

    离散化  简而言之 就是把区间缩小  但是相对大小不变  这样就能用线段树维护了

    当然 还有一个注意点就是 离散的区间是[l,mid],[mid,r]  而不是[l,mid],[mid+1,r].


    至于为什么这样  可以用反证法~~如果[mid,mid+1]之间有一个海报怎么存贮?

    奉上代码:

    #include <stdio.h>
    #include <vector>
    #include <string.h>
    #include <algorithm>
    using namespace std;
    struct node
    {
    	int flag;
    	int l,r;
    };
    vector<int>v;
    int res;
    int N; 
    bool use[100005*2+10];
    node tree[40*100000];
    int point_x[100005];
    int point_y[100005];
    int getid(int x)
    {
    	return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
    }
    void build(int root,int l,int r)
    {
    	tree[root].flag=0;
    	tree[root].l=l;
    	tree[root].r=r;
    	if(l+1==r) return ;
    	int mid=(l+r)/2;
    	build(root*2,l,mid);
    	build(root*2+1,mid,r);
    }
    void update(int l,int r,int root,int x)
    {
    	
    	if(tree[root].l==l&&tree[root].r==r)
    	{
    		tree[root].flag=x;
    		return ;
    	}
    	if(tree[root].l+1>=tree[root].r) return;
    	if(tree[root].flag)
    	{
    		tree[root*2+1].flag=tree[root*2].flag=tree[root].flag;
    		tree[root].flag=0;
    	}
    	int mid=(tree[root].l+tree[root].r)/2;
    	if(l>mid)
    	update(l,r,root*2+1,x);
    	else if(r<=mid)
    	update(l,r,root*2,x);
    	else
    	{
    		update(l,mid,root*2,x);
    		update(mid,r,root*2+1,x);
    	}
    }
    void query(int root)
    {
    	
    	if(tree[root].flag&&!use[tree[root].flag])
    	{
    		res++;
    		use[tree[root].flag]=true;
    		return ;
    	}
    	if(tree[root].l+1>=tree[root].r) return ;
    	if(!use[tree[root].flag]) 
    	{
    		query(root*2);
    		query(root*2+1);
    	}
    
    }
    int main()
    {
    	int n,l;
    	memset(tree,0,sizeof(tree));
    	v.clear(); 
    	scanf("%d %d",&n,&l);
    	for(int i=0;i<n;i++)
    	{
    		scanf("%d %d",&point_x[i],&point_y[i]);
    		v.push_back(point_x[i]);
    		v.push_back(point_y[i]);
    	}
    	sort(v.begin(),v.end());
    	v.erase(unique(v.begin(),v.end()),v.end());
    	N=v.size();
    	build(1,1,N);
    	for(int i=0;i<n;i++)
    	{
    		update(getid(point_x[i]),getid(point_y[i]),1,i+1);
    	}
    	res=0;
    	memset(use,false,sizeof(use));
    	query(1);
    	printf("%d\n",res);
    	return 0;
    }


    展开全文
  • 主要想练下线段树区间离散化,这是一门学问。 我一般喜欢线段树每个结点维护左开右闭区间,设计到区间计数的话。 这题明显是个区间覆盖和,区间数种类统计。 这一题我是每个结点维护[i-1,i]这个长度为1的区间...

    题目水题

     

    主要想练下线段树区间离散化,这是一门学问。

     

    我一般喜欢线段树每个结点维护左开右闭区间,设计到区间计数的话。

    这题明显是个区间覆盖和,区间数种类统计。

    这一题我是每个结点维护[i-1,i]这个长度为1的区间染色情况。

    先把区间左端点减一。(因为我们离散化只能离散化端点,离散化区间会出错。比如如果你要对区间离散化[1,4],[6,7]离散化后[1,2],[3,4],就会把所有区间覆盖)

    ,离散化后  更新(l+1,r)这段区间。//(这是为了把端点再转化成区间)。

     

    在纸上画下  很容易想明白。

    #include<cstdio>
    #include<algorithm>
    #include<vector>
    using namespace std;
    typedef long long ll;
    typedef double db;
    const int M= 2e4+7;
    #define ls o*2
    #define rs o*2+1
    int li[M*2],l[M],r[M];
    ll st[M<<2],tag[M<<2];
    int vis[M<<2];
    int mp[M];
    vector<int>G;
    void pu(int o,int l,int r)
    {
    	if(tag[o]==0)
    	return ;
    	int m=(l+r)/2;
    	tag[ls]=tag[o]; 
    	tag[rs]=tag[o];
    	st[ls]=tag[o]*(m-l+1);
    	st[rs]=tag[o]*(r-m);
    	vis[ls]=1;vis[rs]=1;
    	tag[o]=0;
    }
    void bd(int o,int l,int r)
    {
    	if(vis[o]==0)return;
    	tag[o]=0,st[o]=0;
    	if(l==r) return ;
    	int m=(l+r)/2;
    	bd(ls,l,m);
    	bd(rs,m+1,r);
    }
    void up(int o,int l,int r,int x,int y,int d)
    {
    	vis[o]=1;
    	if(x<=l&&r<=y)
    	{
    		st[o]=(r-l+1)*d;
    		tag[o]=d;
    		return ;
    	}
    	pu(o,l,r);
    	int m=(l+r)/2;
    	if(x<=m)up(ls,l,m,x,y,d);
    	if(y>m)up(rs,m+1,r,x,y,d);
    	st[o]=st[ls]+st[rs];
    }
    ll qu(int o,int l,int r,int x,int y)
    {
    	vis[o]=1;
    	if(x<=l&&r<=y)
    	{
    		return st[o];
    	}
    	pu(o,l,r);
    	ll ans=0;
    	int m=(l+r)/2;
    	if(x<=m)ans+=qu(ls,l,m,x,y);
    	if(y>m)ans+=qu(rs,m+1,r,x,y);
    	return ans;
    }
    int main()
    {
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{
    		int n;
    		bd(1,1,M);
    		//线段树维护左开右闭区间 
    		scanf("%d",&n);
    		int ma=0,sz=0;
    		for(int i=1;i<=n;i++)
    		{
    			scanf("%d%d",&l[i],&r[i]);
    			l[i]--;
    			li[++sz]=l[i],li[++sz]=r[i]; 
    		}
    		sort(li+1,li+1+sz);
    		sz=unique(li+1,li+1+sz)-(li+1);
    		for(int i=1;i<=n;i++)
    		{
    			l[i]=lower_bound(li+1,li+1+sz,l[i])-li;
    			r[i]=lower_bound(li+1,li+1+sz,r[i])-li;
    		//	printf("%d  %d  %d\n",i,l[i],r[i]);
    			up(1,1,sz,l[i]+1,r[i],i);//这样避免区间讨论 
    		}
    		
    		int ans=0;
    		for(int i=1;i<=sz;i++)
    		{
    			int now=qu(1,1,sz,i,i);
    		//	printf("%d   %d\n",i,now);
    			if(!mp[now]&&now)ans++;
    			mp[now]++;
    			G.push_back(now);
    		}
    		int len=G.size();
    		for(int i=0;i<len;i++)
    		{
    			int x=G[i];
    			mp[x]=0;
    		}
    		G.clear();
    		printf("%d\n",ans);
    	}
    	return 0;
    }

     

    展开全文
  • 看到这道题,知道要离散化,也知道怎么将时间区间离散化,但不知道怎么处理建边。o(╯□╰)o 不得不ORZ神牛了 题意:有 N 个人来吃烤肉,每个人到达时间为 si,离开时间为 ei,点的烤肉数量为 ni,烤好一份...
  • 我们在进行区间离散的过程中,虽然区间的大小会发生改变,但是他们的相对关系并没有变化.在离散过程中,我们将最小值标为1,次小值标为2,以此类推、 。比如说[1, 1000000]、[2, 1000001]、[2, 10]这3个区间的...
  • 通常对于我们不想要连续的数值,我们可将其离散化离散化也可称为分组、区间化。 Pandas为我们提供了方便的函数cut(): pd.cut(x, bins, right=True, labels=None, retbins=False, precision=3, include_lowest=...
  • bins: 离散化的数目,或者切分的区间 labels: 离散化后各个类别的标签 right: 是否包含区间右边的值 import pandas as pd import numpy as np import os os.getcwd() 'D:\\Jupyter\\notebook\\Python数据清洗实战\...
  • 区间离散化+线段树区间求最值poj 3368 Frequent values
  • 通常对于我们不想要连续的数值,我们可将其离散化离散化也可称为分组、区间化。 Pandas为我们提供了方便的函数cut(): pd.cut(x, bins, right=True, labels=None, retbins=False, precision=3, include_lowest=...
  • POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
  • 分析: 区间离散化之后 就是一个裸的区间染色啦 套用线段树区间更新就可以搞啦 代码: // // Created by TaoSama on 2015-09-16 // Copyright (c) 2015 TaoSama. All rights reserved. // //#pragma comment(link
  • 上面的例子并不很生动,于是我们开始以线段树的区间离散化为例: 首先,就这题而言,我们 只需要区间的相对属性,而不需要区间的具体长度 (这是显然的) 所谓区间的相对属性,主要就是各个区间之间的关系了,...
  • 题目大意:  有一面墙,墙上铺着瓷砖,有n张海报,每张海报是从第a块瓷砖到第b块瓷砖,从第一张海报开始贴,贴到第n张海报的时候,问有... 由于瓷砖有10000000块,直接使用线段树,空间耗费过大,所以使用离散化分解
  • 离散化:维护区间端点的相对大小关系,将其map到[1, 2n]的区间上。 注意:map之后得到的是端点,而线段树上的节点是单位长度的区间,所以在update的时候应该 update(l, r-1)。。。 #include #include #include ...
  • 连续属性离散化方法

    千次阅读 2019-07-18 21:52:59
    离散化方法 由于一些数据挖掘的算法,主要是一些分类算法,要求数据是分类的形式即是离散的。所以就需要将连续的属性变换为分类的属性,即连续的变为离散的。 常用的离散化方法有以下三种:等宽法、等频法、基于聚类...
  • 我做这道题遇到的坑点,第一点离散化,第二点线段树用的不熟练,在update和pushdown出错了,区间覆盖和区间更新有一点点不一样就是,你要把根节点变回-1,还有就是用的太少了,理解不够update左右儿子更新出错了。...
  • 离散化模板题(区间和)题解

    多人点赞 2020-02-27 23:52:57
    本题是一个非常好的模板题,结合了前缀和、离散化的知识点。 题目 题目链接 AcWing的OJ,https://www.acwing.com/problem/content/804/。 题目描述 假定有一个无限长的数轴,数轴上每个坐标上的数都是 0。 现在...
  • 论文研究-基于粗糙集的区间型数据离散化算法.pdf, 针对条件属性取值为区间型数据的离散化问题,提出了一种新的基于粗糙集理论的离散化算法.首先将粗糙集理论中上、下近似...
  • 802. 区间和(离散化

    千次阅读 2019-05-26 11:19:23
    近下来,进行 m 次询问,每个询问包含两个整数l和r,你需要求出在区间[l, r]之间的所有数的和。 输入格式 第一行包含两个整数n和m。 接下来 n 行,每行包含两个整数x和c。 再接下里 m 行,每行包含两个整数l和r。 ...
  • 随着数据挖掘和知识发现等技术的迅速发展,出现了很多数据离散的算法,但是,已有的离散化方法大多是针对固定点上的连续属性值的情况,实际应用中大量存在着连续区间属性值的情况。针对这一问题,提出了一种连续区间...
  • 连续特征离散化的方法

    万次阅读 2017-04-23 11:37:36
    首先在网上搜了一下,连续特征离散化处理起到的效果是什么,这里引用一下知乎的回答 作者:严林 链接:https://www.zhihu.com/question/31989952/answer/54184582 来源:知乎 著作权归作者所有。
  • 数据标准(normalization)是将数据按比例缩放, 使之落入一个小的特定区间. 在某些比较和评价的指标处理中经常会用到, 去除数据的单位限制, 将其转化为无量纲的纯数据, 便于在不同单位或量级的指标能够进行比较和...
  • 离散化-区间

    2019-09-23 00:03:30
    近下来,进行 m 次询问,每个询问包含两个整数l和r,你需要求出在区间[l, r]之间的所有数的和。 输入格式 第一行包含两个整数n和m。 接下来 n 行,每行包含两个整数x和c。 再接下里 m 行,每行包含两个整数l和r...
  • 1.策略概述 光滑:去掉数据中的噪声,包括分箱、回归和...离散化:数值属性(例如:年龄)的原始值用区间标签或者概念标签替换。这些标签可以递归的组织成更高层概念,导致数值属性的概念分层。 由标称数据产生...
  • 提出一种基于分类目标的启发式离散化算法, 通过该算法能够解决粗糙集理论中的连续属性离散化问题. 该算法充分考虑目标分类和属性的重要性, 在减少决策规则的同时完成了属性约简. 通过茶味觉信号的验证及与传统算法...
  • 1知识点:线段树区间覆盖+离散化 2题意分析:竞选人需要在墙上贴宣传海报,海报高度相同宽度不一定相同,按照时间轴会出现覆盖,给定按照时间轴海报的起始位置和终止位置,询问在最终状态会展现多少海报,n([1, ...
  • 离散化技术方法可以通过将属性(连续取值)域值范围分为若干区间,来帮助消减一个连续(取值)属性的取值个数。可以用一个标签来表示一个区间内的实际数据值。在基于决策树的分类挖掘中,消减属性取值个数的离散化...
  • 使用决策树往往倾向于少量的离散化区间,过多的离散化将使得规则过多受到碎片区间的影响。 关联规则需要对所有特征一起离散化,关联规则关注的是所有特征的关联关系,如果对每个列单独离散化将失去整体规则性...
  • 在机器学习中,很多人在处理连续数据的时候,很多情况下要将连续数据离散化,那么什么时候离散化离散化的好处是什么? 目录 连续数据概念 离散化概念 离散化原因 离散化的优势 连续数据概念 连续数据,统计学概念...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 39,804
精华内容 15,921
关键字:

区间离散化