Hihocoder 1079 离散化

发布时间:2016-12-31 7:40:06编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Hihocoder 1079 离散化 ",主要涉及到Hihocoder 1079 离散化 方面的内容,对于Hihocoder 1079 离散化 感兴趣的同学可以参考一下。

离散化这里有很多种方式
利用结构体记录最初的索引在按位置排序再记录排名即为离散的位置再按索引排回来
或者用数组记录排序后直接对原位置二分直接去找离散应在的位置
或者对数组排序后直接map

3 201 101 46 10
3 202 31 23 4

两组答案应该都为3
但这里如果直接计算的话第一组会计算得2
1-4和6-10 这里用到了所有的离散后的数据1-2和3-4本来1-4和6-10中间还有4-6的部分是1-10这张的但1-2被改为2,3-4被改为3没有1了所以输出为2
要是1-4后还有节点5的话就不会了至少节点5是1
所以这里可以采用给每个位置后增加一个位置0.5用来连接原先的所有的两个位置,这样连续的位置被染色后这个0.5的位置也被染掉了,之后被其它的修改两边会仍然保留这个点的颜色
所以这里最终离散也只是离散到点本来的海报还是连续的,除非添加题目中不会有的小数数据作为中间点,不然就会漏掉原来连续染色(贴海报)的某段
当然也可以通过像小Hi大神这么想问题才是看出问题的本质以及对本质的运用

#include <cstdio>#include <memory>#include <cstdlib>#include <cstring>#include <cmath>#include <vector>#include <cassert>#include <string>#include <ctime>#include <map>#include <queue>#include <algorithm>#include <iostream>#include <cassert>using namespace std;#define REP(i,n) for(int i=0;i<n;i++)#define rep(i,a,b) for(int i=a;i<=b;i++)#define req(i,a,b) for(int i=a;i>=b;i--)#define rp(i,a) for(int i=head[a];i+1;i=edge[i].next)#define cl(a,b) memset(a,b,sizeof a);#define ll long long#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define mod 1000000007const int inf = ~0u >> 2;const ll INF = (1LL << 62) - 1;double eps = 1e-9;const int N = 1e6+5;const int M = 21;int ans=0, cnt;int n, m;int c[N<<2];int lan[N << 2];int color[N << 2];void down(int rt, int l, int r);void up(int rt) {    if (c[rt << 1] > 0 && c[rt << 1 | 1] > 0)    {        if (c[rt << 1] == c[rt << 1 | 1])            c[rt] = c[rt << 1];        else            c[rt] = -1;    }    else {        c[rt] = -1;    }}void down(int rt,int l,int r) {    int m = (l + r) >> 1;    if (lan[rt]!=0) {        c[rt << 1] = c[rt];        c[rt << 1 | 1] = c[rt];        lan[rt << 1] = lan[rt];        lan[rt << 1 | 1] = lan[rt];     }    lan[rt] = 0;}void build(int l, int r, int rt) {    if (l == r) {        c[rt] = 0;        return;                                             }    int m = (l + r) >> 1;       build(lson);    build(rson);    up(rt);}void update(int L,int R,int value,int l, int r, int rt) {    if (L<=l&&r<=R) {        c[rt] = value;        lan[rt] = 1;        return;    }    down(rt,l,r);    int m = (l + r) >> 1;    if (m >= L) {        update(L,R, value, lson);    }    if(m < R){        update(L,R, value, rson);    }    up(rt);}void query2(int L,int R,int l,int r,int  rt) {    if (L <= l&&R >= r) {        if (c[rt] > 0) {            color[c[rt]]++;            return;        }        if (l == r)return;    }    down(rt, l, r);    int m = (l + r) >> 1;    if (m >= L) {        query2(L, R, lson);    }    if(m<R){        query2(L, R, rson);    }    return;}struct node {    int index;    double pos;    int rank;}nd[N];int cmp(node a, node b) {    return a.pos < b.pos;}int cmp2(node a, node b) {    return a.index < b.index;}int main(){    memset(c, -1, sizeof c);    memset(lan, 0, sizeof lan);    int tlen;    scanf("%d%d", &m,&tlen);    cnt = 0;    for(int i=0;i<m;i++){        int op, l, r, value;        scanf("%d%d", &l, &r);        nd[cnt].index = i*2;        nd[cnt].pos = l;        cnt++;        nd[cnt].index = i*2+1;        nd[cnt].pos = r;        cnt++;    }    sort(nd, nd+cnt, cmp);    int tcnt = cnt;    for (int i = 0; i < tcnt; i++) {        nd[cnt].index = 999999;        nd[cnt++].pos = nd[i].pos + 0.5;    }    sort(nd, nd + cnt, cmp);    int rk = 1;    nd[0].rank = rk;    for (int i = 1; i < cnt; i++) {        if (nd[i].pos > nd[i - 1].pos)            nd[i].rank = ++rk;        else            nd[i].rank = rk;    }    sort(nd, nd + cnt, cmp2);    build(0, rk, 1);    for (int i = 0; i < m; i++) {        update(nd[i * 2].rank, nd[i * 2 + 1].rank, i+1, 1, rk, 1);    }    query2(1, rk, 1, rk, 1);    for (int i = 1; i <= m; i++)        if (color[i] != 0)            ans++;        printf("%d\n", ans);    return 0;}
在线段树的通常用法中,线段树的节点是有2种不同的意义的,一种是离散型的,比如在Hiho一下 第二十周中,一个节点虽然描述的是一个区间[3, 9],但是实际上这样一个区间是{3, 4, 5, 6, 7, 8, 9}这样的意义。而另一种就是连续型的,比如就在这一周的问题中,一个节点如果描述的是一个区间[3, 9],它就确确实实描述的是在数轴上从3这个标记到9这个标记的这一段。那么有的小朋友可能就要问了,这两种不同的意义有什么区别呢?在小Hi看来,其实只有这样的几个区别:1.叶子节点:在离散型中,叶子节点是[i, i],而连续性中是[i, i + 1];2.分解区间:在离散型中,一段区间是分解成为[l, m], [m + 1, r],而在连续型中,是分解成为[l, m], [m, r];3.其他所有类似的判定问题。那么亲爱的小朋友们,你们懂了么?

这里注意到l=r-1之后就可以不处理了,不然不加条件或不另外加条件会无线循环的另外之前的m+1<=R也就是m<R这里因为连续了可以改为m<=R了

#include <cstdio>#include <memory>#include <cstdlib>#include <cstring>#include <cmath>#include <vector>#include <cassert>#include <string>#include <ctime>#include <map>#include <queue>#include <algorithm>#include <iostream>#include <cassert>using namespace std;#define REP(i,n) for(int i=0;i<n;i++)#define rep(i,a,b) for(int i=a;i<=b;i++)#define req(i,a,b) for(int i=a;i>=b;i--)#define rp(i,a) for(int i=head[a];i+1;i=edge[i].next)#define cl(a,b) memset(a,b,sizeof a);#define ll long long#define lson l,m,rt<<1#define rson m,r,rt<<1|1#define mod 1000000007const int inf = ~0u >> 2;const ll INF = (1LL << 62) - 1;double eps = 1e-9;const int N = 1e6+5;const int M = 21;int ans=0, cnt;int n, m;int c[N<<2];int lan[N << 2];int color[N << 2];void down(int rt, int l, int r);void up(int rt) {    if (c[rt << 1] > 0 && c[rt << 1 | 1] > 0)    {        if (c[rt << 1] == c[rt << 1 | 1])            c[rt] = c[rt << 1];        else            c[rt] = -1;    }    else {        c[rt] = -1;    }}void down(int rt,int l,int r) {    int m = (l + r) >> 1;    if (lan[rt]!=0) {        c[rt << 1] = c[rt];        c[rt << 1 | 1] = c[rt];        lan[rt << 1] = lan[rt];        lan[rt << 1 | 1] = lan[rt];     }    lan[rt] = 0;}void build(int l, int r, int rt) {    if (l == r-1) {        c[rt] = 0;        return;                                             }    int m = (l + r) >> 1;       build(lson);    build(rson);    up(rt);}void update(int L,int R,int value,int l, int r, int rt) {    //if (r <= L||l>=R)return;    if (L<=l&&r<=R) {        c[rt] = value;        lan[rt] = 1;        return;    }    if (l == r - 1)return;    down(rt,l,r);    int m = (l + r) >> 1;    if (m >= L) {        update(L,R, value, lson);    }    if(m <= R){        update(L,R, value, rson);    }    up(rt);}void query2(int L,int R,int l,int r,int  rt) {    //if (r <= L || l>=R)return;    if (L <= l&&R >= r) {        if (c[rt] > 0) {            color[c[rt]]++;            return;        }    }    if (l == r - 1)return;    down(rt, l, r);    int m = (l + r) >> 1;    if (m >= L) {        query2(L, R, lson);    }    if(m<=R){        query2(L, R, rson);    }    return;}struct node {    int index;    double pos;    int rank;}nd[N];int cmp(node a, node b) {    return a.pos < b.pos;}int cmp2(node a, node b) {    return a.index < b.index;}int a[N];int b[N];map<int, int> f;int main(){    memset(c, -1, sizeof c);    memset(lan, 0, sizeof lan);    int tlen;    scanf("%d%d", &m,&tlen);    cnt = 0;    for(int i=0;i<m;i++){        int op, l, r, value;        scanf("%d%d", &l, &r);        nd[cnt].index = i*2;        nd[cnt].pos = l;        cnt++;        nd[cnt].index = i*2+1;        nd[cnt].pos = r;        cnt++;    }    sort(nd, nd+cnt, cmp);    int rk = 1;    nd[0].rank = rk;    for (int i = 1; i < cnt; i++) {        if (nd[i].pos > nd[i - 1].pos)            nd[i].rank = ++rk;        else            nd[i].rank = rk;    }    sort(nd, nd + cnt, cmp2);    build(0, rk, 1);    for (int i = 0; i < m; i++) {        update(nd[i * 2].rank, nd[i * 2 + 1].rank, i+1, 1, rk, 1);    }    query2(1, rk, 1, rk, 1);    for (int i = 1; i <= m; i++)        if (color[i] != 0)            ans++;        printf("%d\n", ans);    return 0;


上一篇:系统无法开始服务器进程。请检查用户名和密码。 (Exception from HRESULT: 0x8000401A)
下一篇:Android 开源框架Universal-Image-Loader学习

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款