精华内容
下载资源
问答
  • 题目给的区间最大是10000000,所以需要将区间离散化一下,然后线段树求解。 //35616K 94MS #include #include #include #define M 10007 using namespace std; int id[M*2],_hash[10000007]; int n,num; struct T...
    
    

    Mayor's posters
    Time Limit: 1000MS   Memory Limit: 65536K
    Total Submissions: 45894   Accepted: 13290

    Description

    The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim. The city council has finally decided to build an electoral wall for placing the posters and introduce the following rules: 
    • Every candidate can place exactly one poster on the wall. 
    • All posters are of the same height equal to the height of the wall; the width of a poster can be any integer number of bytes (byte is the unit of length in Bytetown). 
    • The wall is divided into segments and the width of each segment is one byte. 
    • Each poster must completely cover a contiguous number of wall segments.

    They have built a wall 10000000 bytes long (such that there is enough place for all candidates). When the electoral campaign was restarted, the candidates were placing their posters on the wall and their posters differed widely in width. Moreover, the candidates started placing their posters on wall segments already occupied by other posters. Everyone in Bytetown was curious whose posters will be visible (entirely or in part) on the last day before elections. 
    Your task is to find the number of visible posters when all the posters are placed given the information about posters' size, their place and order of placement on the electoral wall. 

    Input

    The first line of input contains a number c giving the number of cases that follow. The first line of data for a single case contains number 1 <= n <= 10000. The subsequent n lines describe the posters in the order in which they were placed. The i-th line among the n lines contains two integer numbers li and ri which are the number of the wall segment occupied by the left end and the right end of the i-th poster, respectively. We know that for each 1 <= i <= n, 1 <= li <= ri <= 10000000. After the i-th poster is placed, it entirely covers all wall segments numbered li, li+1 ,... , ri.

    Output

    For each input data set print the number of visible posters after all the posters are placed. 

    The picture below illustrates the case of the sample input. 

    Sample Input

    1
    5
    1 4
    2 6
    8 10
    3 4
    7 10
    

    Sample Output

    4
    

    Source


    给你n张画报要贴在墙上,后面贴上去的会覆盖前面贴上去的,求最后能够看见多少张画报。
    题目给的区间最大是10000000,所以需要将区间离散化一下,然后线段树求解。
    //35616K	94MS
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #define M 10007
    using namespace std;
    int id[M*2],_hash[10000007];
    int n,num;
    struct T
    {
        int left,right,mid,color;
        T(){color=0;}
    }tree[M<<4];
    struct P
    {
        int l,r;
    }p[M*8];
    void build(int l,int r,int i)
    {
        tree[i].left=l;tree[i].right=r;
        tree[i].mid=(l+r)>>1;tree[i].color=0;
        if(l==r)return;
        build(l,tree[i].mid,i<<1);
        build(tree[i].mid+1,r,i<<1|1);
    }
    bool query(int l,int r,int i)
    {
        bool flag;
        if(tree[i].color)return false;
        if(tree[i].left==l&&tree[i].right==r)
        {
            tree[i].color=true;
            return true;
        }
        if(r<=tree[i].mid)flag=query(l,r,i<<1);
        else if(l>tree[i].mid)flag=query(l,r,i<<1|1);
        else
        {
            bool flag1=query(l,tree[i].mid,i<<1);
            bool flag2=query(tree[i].mid+1,r,i<<1|1);
            flag=flag1||flag2;
        }
        if(tree[i<<1].color&&tree[i<<1|1].color)//反馈原节点
            tree[i].color=true;
        return flag;
    }
    void lisanhua()
    {
        sort(id,id+num);
        num=unique(id,id+num)-id;
        for(int i=0;i<num;i++)
            _hash[id[i]]=i;
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            num=0;
            scanf("%d",&n);
            for(int i=1;i<=n;i++)
            {
                scanf("%d%d",&p[i].l,&p[i].r);
                id[num++]=p[i].l;
                id[num++]=p[i].r;
            }
            lisanhua();
            build(0,num-1,1);
            int count=0;
            for(int i=n;i>=1;i--)//从最后贴的往前找
            {
                if(query(_hash[p[i].l],_hash[p[i].r],1))
                    count++;
            }
            printf("%d\n",count);
        }
        return 0;
    }
    


    展开全文
  • 我们在进行区间离散的过程中,虽然区间的大小会发生改变,但是他们的相对关系并没有变化.在离散过程中,我们将最小值标为1,次小值标为2,以此类推、 。比如说[1, 1000000]、[2, 1000001]、[2, 10]这3个区间的...
    时间限制: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

    最近刚好在补补以前的题,就借机学一下离散化吧

    我们先来说一下何为离散化: 对离散化简单的理解就是给定的数据量太大,而我们所求的问题与具体数值是多少并无太大关系,这时候我们就可以进行离散化.我们在进行区间离散的过程中,虽然区间的大小会发生改变,但是他们的相对关系并没有变化.在离散过程中,我们将最小值标为1,次小值标为2,以此类推、

    。比如说[1, 1000000]、[2, 1000001]、[2, 10]这3个区间的左右端点组成的集合为{1, 2, 10, 1000000, 1000001},那么我就将这个集合对应到{1, 2, 3, 4, 5},那么原来的三个区间就变成了[1, 4]、[2, 5]、[2, 3]这3个区间,但是他们的相互覆盖关系却是一点变化都没有。





    思路:将给定的区间用map进行离散化,然后每一张海报就相当于一次修改,然后用懒惰标记进行标记一下,对应的区间标记一下是否有海报,对应的是哪一张海报,然后查询一下即可;


    #include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<map>
    #include<algorithm> 
    const int N=2e6+5;
    using namespace std;
    int laz[2*N];
    int ans[2*N];
    map<int,int>mp;
    int n,m;
    int ss=0,num[2*N],a[2*N],b[2*N];
    void pushdown(int d)
    {
    if(laz[d])
    {
    laz[2*d]=laz[2*d+1]=laz[d];
    laz[d]=0;
    }
    return ;
    }
    void update(int L,int R,int l,int r,int val,int pos) {
        if(l>=L&&r<=R) {
            laz[pos]=val;
            return;
        }
        if(l+1==r)return;
        int mid=(l+r)>>1;
        pushdown(pos);
        if(L<=mid) update(L,R,l,mid,val,pos<<1);
        if(mid<R)update(L,R,mid,r,val,pos<<1|1);
    }
    void query(int L,int R,int l,int r,int pos) {
        if(laz[pos]&&!ans[laz[pos]]){
    //查询该区间是否有海报,是哪张海报,并标记,因为是线段树,海报的长度可能会分成几部分.
            ans[laz[pos]]=1;
            ss++;
            return;
        }
        if(l+1==r)return;
        int mid=(l+r)>>1;
        pushdown(pos);
        int ans=0;
        if(L<=mid) query(L,R,l,mid,pos<<1);
        if(R>mid) query(L,R,mid,r,pos<<1|1);
        return;
    }
    int main()
    {
    int i,j,k=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
    scanf("%d%d",&a[i],&b[i]);
    num[k++]=a[i];
    num[k++]=b[i];
    }
    sort(num,num+k);
    int s=0;
    for(i=0;i<k;i++)
    if(!mp[num[i]])//用map进行区间的离散化;
    mp[num[i]]=++s;
    for(i=1;i<=n;i++)
    update(mp[a[i]],mp[b[i]],1,s,i,1);
    query(1,s,1,s,1);
    printf("%d\n",ss);
    return 0;
     
    }

    展开全文
  • 区间离散化+线段树区间求最值poj 3368 Frequent values

    Frequent values
    Time Limit: 2000MS Memory Limit: 65536K
    Total Submissions: 15238 Accepted: 5553
    Description
    You are given a sequence of n integers a1 , a2 , … , an in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers ai , … , aj.
    Input
    The input consists of several test cases. Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a1 , … , an (-100000 ≤ ai ≤ 100000, for each i ∈ {1, …, n}) separated by spaces. You can assume that for each i ∈ {1, …, n-1}: ai ≤ ai+1. The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the
    query.
    The last test case is followed by a line containing a single 0.
    Output
    For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.
    Sample Input
    10 3
    -1 -1 1 1 1 1 3 10 10 10
    2 3
    1 10
    5 10
    0
    Sample Output
    1
    4
    3
    Source
    Ulm Local 2007
    本题关键点是区间离散化。所谓离散就是把连续相等的点缩成一个点,同时用结构体记录该点所代表的的区间的端点和元素个数。

    #include <stdio.h>
    #include <string.h>
    #include <algorithm>
    using namespace std;
    const int maxn = 100005;
    int a[maxn];
    int hash[maxn];
    int p;
    struct node
    {
        int start;
        int end;
    }seg[maxn];//seg记录每个离散得到的点对应区间的端点。
    struct line
    {
        int l;
        int r;
        int maxnum;
    }tree[maxn<<2];
    void build(int Node, int l, int r)
    {
        tree[Node].l = l; tree[Node].r = r;
        if(l == r)//是叶子点
        {
            tree[Node].maxnum = seg[l].end - seg[l].start + 1;//这个节点里面重复的数有几个
            return;
        }
        int mid = (tree[Node].l+tree[Node].r)>>1;
        build(Node*2,l,mid);
        build(Node*2+1,mid+1,r);
        tree[Node].maxnum = max(tree[Node*2].maxnum, tree[Node*2+1].maxnum);
    }
    int query(int Node, int l, int r)
    {
        if(tree[Node].l == l && tree[Node].r == r) return tree[Node].maxnum;
        int mid = (tree[Node].l+tree[Node].r)>>1;
        if(r <= mid) return query(Node*2,l,r);
        else if(l > mid) return query(Node*2+1,l,r);
        else return max(query(Node*2,l,mid),query(Node*2+1,mid+1,r));
    }
    int main()
    {
        freopen("output.txt","w",stdout);
        freopen("input.txt","r",stdin);
        int n,m,pre;
        while(EOF!=scanf("%d",&n)&&n)
        {
            scanf("%d",&m);
            for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
            pre = 100001;
            p = 0;      //p为离散成的点。
            for(int i = 1; i <= n; i++)
            {
                if(a[i] != pre)//新的节点
                {
                    pre = a[i];
                    p++;
                    seg[p].start = i;
                    seg[p].end = i;
                }
                else seg[p].end = i;
                hash[i] = p;    //标记原序列中每个下标对应离散后的点。
            }
            build(1,1,p);   //对离散后的点建树
            while(m--)
            {
                int x,y,xx,yy;
                scanf("%d %d",&x,&y);
    
                xx = hash[x];//下标为x的点离散后对应的点
                yy = hash[y];//下标为y的点离散后对应的点
    
                if(xx == yy)//离散后的点是用一个点,说明[x,y]为同一个点集
                {
                    printf("%d\n",y-x+1);
                    continue;
                }
                else        //[x,y]不是同一个点集,就分为三部分,第二部分的点集最大值用线段树来求。
                {
                    int ans1 = seg[xx].end-x+1;
                    int ans2 = 0;
                    int ans3 = y-seg[yy].start+1;
                    if(yy-xx > 1)
                        ans2 = query(1,xx+1,yy-1);
                    printf("%d\n",max( max(ans1,ans2),ans3 ) );
                    continue;
                }
            }
        }
        return 0;
    }
    展开全文
  • POJ2528解题报告,区间离散化线段树

    POJ2528解题报告,区间离散化,线段树
    Mayor’s posters
    Time Limit: 1000MS Memory Limit: 65536K
    Total Submissions: 51104 Accepted: 14790
    Description
    The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim. The city council has finally decided to build an electoral wall for placing the posters and introduce the following rules:
    • Every candidate can place exactly one poster on the wall.
    • All posters are of the same height equal to the height of the wall; the width of a poster can be any integer number of bytes (byte is the unit of length in Bytetown).
    • The wall is divided into segments and the width of each segment is one byte.
    • Each poster must completely cover a contiguous number of wall segments.

    They have built a wall 10000000 bytes long (such that there is enough place for all candidates). When the electoral campaign was restarted, the candidates were placing their posters on the wall and their posters differed widely in width. Moreover, the candidates started placing their posters on wall segments already occupied by other posters. Everyone in Bytetown was curious whose posters will be visible (entirely or in part) on the last day before elections.
    Your task is to find the number of visible posters when all the posters are placed given the information about posters’ size, their place and order of placement on the electoral wall.
    Input
    The first line of input contains a number c giving the number of cases that follow. The first line of data for a single case contains number 1 <= n <= 10000. The subsequent n lines describe the posters in the order in which they were placed. The i-th line among the n lines contains two integer numbers li and ri which are the number of the wall segment occupied by the left end and the right end of the i-th poster, respectively. We know that for each 1 <= i <= n, 1 <= li <= ri <= 10000000. After the i-th poster is placed, it entirely covers all wall segments numbered li, li+1 ,… , ri.
    Output
    For each input data set print the number of visible posters after all the posters are placed.

    The picture below illustrates the case of the sample input.

    Sample Input
    1
    5
    1 4
    2 6
    8 10
    3 4
    7 10
    Sample Output
    4
    Source
    Alberta Collegiate Programming Contest 2003.10.18
    这次主要学习了离散化:在不改变端点的相对顺序的情况下,将区间压缩到最小。例如,两个区间[1,10]、[5,11],对端点进行排序,然后重新赋值,令5=2,10=3,11=14,然后区间变成[1,3]、[2,4]。对输入的数排序去重后,把区间缩减。这样,总共就输入10000个线段,最多20000个端点,这样的线段树规模比原先的一千万就小了很多。

    #include <cstring>
    #include <cstdlib>
    #include <cstdio>
    #include <algorithm>
    #define MAX 20010
    #define Lson(x) ((x) << 1)  //计算左孩子位置
    #define Rson(x) (((x) << 1) + 1)    //计算右孩子位置
    using namespace std;
    struct Node
    {
        int l;  //线段左端点值
        int r;  //线段右端点
        int c;  //线段的颜色
    }nodes[MAX * 5];
    int map[MAX][2];    //记录输入线段的左右两个端点
    int record[MAX];    //记录颜色是否已经出现
    int total;
    //用于离散化
    struct Line
    {
        int point;  //记录端点的坐标
        int num;    //记录原来的编号
    }line[MAX * 2];
    int mycmp(const Line &a, const Line &b)
    {
        return a.point < b.point;
    }
    void buildTree(int l, int r, int Node)//口诀:赋值,判断,递归,(更新)
    {
        nodes[Node].l = l,nodes[Node].r = r,nodes[Node].c = 0;  //初始化颜色都为0
        if(l == r) return ;
        int mid = (l + r) >> 1;
        buildTree(l, mid, Lson(Node));  //构造左子树
        buildTree(mid + 1, r, Rson(Node));  //构造右子树
    }
    void insert(int l, int r, int Node, int color)//口诀:先判断完全覆盖,再判断更新左右儿子,后递归染色,(回溯更新)
    {
        if(nodes[Node].l == l && nodes[Node].r == r)    //刚好完全覆盖,修改颜色,直接返回
        {
            nodes[Node].c = color;
            return ;
        }
        if(nodes[Node].c > 0)   //如果当前线段已经有颜色,先将颜色复制给左右两个子树,非常重要
        {
            nodes[Lson(Node)].c = nodes[Node].c;
            nodes[Rson(Node)].c = nodes[Node].c;
            nodes[Node].c = 0;  //将颜色传到左右子树后,标记线段没有颜色,等待再次染色
        }
        if(l >= nodes[Rson(Node)].l)    //完全在右子树
            insert(l, r, Rson(Node), color);
        else if(r <= nodes[Lson(Node)].r)   //完全在左子树
            insert(l, r, Lson(Node), color);
        else        //两个子树都有
        {
            insert(l, nodes[Lson(Node)].r, Lson(Node), color);
            insert(nodes[Rson(Node)].l, r, Rson(Node), color);
        }
    }
    void update(int Node)
    {
        if(nodes[Node].c != 0)  //如果当前线段有颜色,记录,不再搜索左右子树,直接返回,相当于上面的广告覆盖下面的广告。
        {
            if(!record[nodes[Node].c])//该颜色还没有计数
            {
                total++;
                record[nodes[Node].c] = 1;//该下次就不会再计数
            }
            return ;
        }
        //如果当前线段没有颜色,递归调用左右子树,查询颜色
        update(Lson(Node));
        update(Rson(Node));
        return ;
    }
    int main()
    {
        freopen("output.txt","w",stdout);
         freopen("input.txt","r",stdin);
        int number,n,i;
        scanf("%d", &number);
        while(number--)
        {
            scanf("%d", &n);
            for(i = 0; i < n; i++)
            {
                scanf("%d%d", &map[i][0], &map[i][1]);
                line[2*i].point = map[i][0];    //记录数据,用于离散化
                line[2*i + 1].point = map[i][1];
                line[2*i].num = -(i + 1);   //线段第一个端点用负数记录
                line[2*i + 1].num = i + 1;  //线段第二个端点用正数记录
            }
            //首先将所有端点排序
            sort(line, line + 2*n, mycmp);
            int temp = line[0].point;
            int count = 1;  //重新开始编号,从1开始
            for(i = 0; i < 2*n; i++)
            {
                if(temp != line[i].point)   //如果当前端点和前面的端点不一样,编号值+1
                {
                    count++;
                    temp = line[i].point;
                }
                if(line[i].num < 0) map[-line[i].num - 1][0] = count;//反解求得相对顺序
                else map[line[i].num - 1][1] = count;//反解求得相对顺序
            }
            buildTree(1, count, 1);
            for(i = 0; i < n; i++) insert(map[i][0], map[i][1], 1, i + 1);
            memset(record, 0, sizeof(record));
            total = 0;
            update(1);
            printf("%d\n", total);
        }
        return 0;
    }
    展开全文
  • 这题的离散化有点不一样。...然后就是线段树区间更新加查询 #include #include #include using namespace std; const int maxn = 10005; int n,num; int li[maxn]; int ri[maxn]; int ne[maxn]; int clo[m
  • 这个题非常有意思的地方是,我们发现区间[1,4]和[5,8]是紧挨着的,因为这个的数代表的是一段区间,原本我们对于普通的离散, a[1]=1,a[2]=5,a[3]=6,a[4]=8;数组下标就是重新离散的位置,但是a[2]和a[3]明显不重叠,...
  • 离散化:维护区间端点的相对大小关系,将其map到[1, 2n]的区间上。 注意:map之后得到的是端点,而线段树上的节点是单位长度的区间,所以在update的时候应该 update(l, r-1)。。。 #include #include #include ...
  • hiho1079 : 离散化(线段树+区间离散化)

    千次阅读 2016-08-16 21:33:02
    #1079 : 离散化 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 小Hi和小Ho在回国之后,重新过起了朝7晚5的学生生活,当然了,他们还是在一直学习着各种算法~ 这天小Hi和小Ho所在的学校举办社团...
  • 主要想练下线段树区间离散化,这是一门学问。 我一般喜欢线段树每个结点维护左开右闭区间,设计到区间计数的话。 这题明显是个区间覆盖和,区间数种类统计。 这一题我是每个结点维护[i-1,i]这个长度为1的区间...
  • 分析: 区间离散化之后 就是一个裸的区间染色啦 套用线段树区间更新就可以搞啦 代码: // // Created by TaoSama on 2015-09-16 // Copyright (c) 2015 TaoSama. All rights reserved. // //#pragma comment(link
  • 线段树+区间离散化

    2016-11-25 17:27:00
    校赛1007 题意 给你一个n(n<1e5),表示n个比赛直播,然后n个区间,l,r(0<=l,r<=1e9),表示比赛开始的时间和结束的...以区间的端点作为标记离散化离散化后映射到线段树,将重复的端点去掉,然后重新排...
  • 一直在用树状数组解题,线段树都有点忘了。。。。 参考了别人的代码后终于明白了离散化的道理和步骤,一下为参考网址:点击打开链接 #include #include #include using namespace std; int casenum,postnum,ans,...
  • 题目大意: 一段长度未知的线段,一种操作:a b c ,表示区间[a,b]要涂的颜色,c=w涂白色,c=b涂黑色,问你最长的白色... 就快去南京邀请赛了,最近做题超没状态,CF rating一直掉,这么简单的线段树离散化居...
  • 很明显的线段树题目,不过主要是想学习以下动态开点,不过数组范围自己一时间也还不懂怎么处理。看cf上很多大佬STL做的,很是骚,%%% #include&lt;bits/stdc++.h&gt; using namespace st...
  • 给定一个区间0~L,以及N条线段(li, ri),这N条线段按照输入顺序覆盖到...算是线段树的另一种使用,虽然标题是离散化,但其实是连续区间下使用线段树。中间还有一些小问题要处理,就是线段树的边界问题。离散情况下,线
  • 一眼过去很像是:排序,然后从前向后扫,有这个区间时插到里,过去以后再删除。然后事实也是这样做的…… 具体起来: 1.如果考虑暴力的话,一种想法是枚举左端和右端要选取的区间(如果我们按长度排序的话),...
  • 线段树线段树基本概念 离散化:把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。通俗的说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小。 例如: 原数据:1,999,...
  • 其实最重要的是离散化的过程,由于展板分成整数单元,普通离散化不能表示,间隔超过一的中间加一点即可。 最最最最傻×的是没写scanf("%d",&n);!!! /******************* poj2528 2016.3.7 1088K 79MS C++ ...
  • title BZOJ 4653 LUOGU 1712 ...现在要从中选出 \(M\) 个区间,使得这 \(M\) 个区间共同包含至少一个位置。换句话说,就是使得存在一个 \(x\),使得对于每一个被选中的区间 \([l_i,r_i]\),都有 \(l_i\l...
  • 离散化——目的是压缩区间范围——优化线段树区间覆盖问题——传统的cover数组再加上——这个题目的特殊性——计算的是最终能看到海报的数量——所以节点的值在这里我的含义是第几张海报覆盖了这个节点好,看...
  • POJ 3277 离散化线段树

    2012-10-26 11:35:22
    坑爹啊 不断徘徊与TL与WA之间 ...注意区间问题 #include #include using namespace std; typedef long long ll; const int n_max=40005; ll h[n_max]; ll hmax[n_max]; ll add[n_max]; ll x[n_max]; struct bu
  •  操作\(1\)是把给定区间\([l,r]\)设为\(1\);  操作\(2\)是把给定区间\([l,r]\)设为\(0\);  操作\(3\)把给定区间\([l,r]0,1\)反转;  一共\(n\)个操作,每次操作后要输出最小位置的\(0\)。  \(n\leq 100000,1\...
  • 第一次写离散化,第一次写线段树,写的时候挺迷茫,AC之后很兴奋...说一下这道题的小trick,大家如果仔细看一下这道题的discuss后会发现,我们在离散化的时候不能只考虑顺序相邻,还要考虑位置相邻,也就是说在顺序...
  • 所以考虑离散化,但是这不同于单点离散化,这是区间离散化,意思就是说离散化原来数据的同时还要保留他们的区间的性质。(大神的栗子:原数据“1-10, 1-4,6-10”,常规单点离散化之后“1-4,1-2,3-4”,原本不...
  • 题意: 给出T组测试数据,N对数字,左和右。代表这海报粘贴的区间。可以有覆盖。询问最后有多少种海报露...第一次sort将点人为的离散,第二次sort把点还原,线段树就很好写了,此题关键是离散化 #include #inclu
  • 这个区间离散化把我调死了。。 总之用vector来离散化,然后叶子节点维护的是一段区间,记录下每个叶子结点的起点+长度 千万要注意下标不能弄错! #include<bits/stdc++.h> #define MAXN 400005 #define...
  • 题意:每个样例给出n块砖的高度和m次询问,每次询问给出三个数l,r,h,问区间l-r内<=h的砖有多少块。...=它的砖块插入线段树(插入的是砖块的下标),之后进行普通的区间查询(因为这时可以保证线段树...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,856
精华内容 742
关键字:

区间离散化线段树