现在的位置: 首页 > 综合 > 正文

线段树小结

2019年08月21日 ⁄ 综合 ⁄ 共 18751字 ⁄ 字号 评论关闭

如果是1~n 个数 那么我们知道线段树 最后一层 一定是n个结点! 

那么 可得线段树 最多的结点数为 2^(log2(n)+1)-1 或者 2*n-1个  

单点更新

HDU1754

//9596209	2013-11-16 12:13:35	Accepted	1754	531MS	7184K	1579 B
#include <iostream>
#include<cstdio>
using namespace std;
#define MAX 200002
int val[MAX];
struct Node
{
    int left,right,max;
}tree[3*MAX];
int max(int a,int b)
{
    return a>b?a:b;
}
int creat(int root,int left,int right)
{
    tree[root].left=left;
    tree[root].right=right;
    if(left==right) return tree[root].max=val[left];
    int a,b,mid;
    mid=(right-left)/2+left;
    a=creat(2*root,left,mid);
    b=creat(2*root+1,mid+1,right);
    return tree[root].max=max(a,b);
}
int calculate(int root,int left,int right)
{
    if(tree[root].left>right || tree[root].right<left)/**两区间相离,就返回0**/
        return 0;
    if(tree[root].left>=left&&tree[root].right<=right)/**区间在所求区间内部,就返回这个区间的最大值**/
        return tree[root].max;
        int a,b;
    a=calculate(2*root,left,right);
    b=calculate(2*root+1,left,right);
    return max(a,b);
}
int updata(int root,int pos,int v)
{
    if(pos<tree[root].left||pos>tree[root].right)
        return tree[root].max;
    if(pos==tree[root].left&&pos==tree[root].right)
        return tree[root].max=v;
    int a,b;
    a=updata(root*2,pos,v);
    b=updata(root*2+1,pos,v);
    return tree[root].max=max(a,b);
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&val[i]);
        creat(1,1,n);
        for(int i=1;i<=m;i++)
        {
            char op;
            int x,y;
            scanf("\n%c%d%d",&op,&x,&y);
            if(op=='Q') printf("%d\n",calculate(1,x,y));
            else updata(1,x,y);
        }
    }
    return 0;
}

HDU1698

修改区间为定值

//9616564	2013-11-18 20:15:24	Accepted	1698	843MS/906MS	4764K	1995 B
#include <iostream>
#include<cstdio>
using namespace std;
#define MAX 100001
int val[MAX];
struct Node
{
    int left,right;
    int mark;
    int total;
}tree[3*MAX];
int creat(int root,int left,int right)
{
    tree[root].left=left;
    tree[root].right=right;
    tree[root].mark=0;
    if(left==right)
        return tree[root].total=val[left];
    int mid=(right+left)/2;
    return tree[root].total=creat(2*root,left,mid)+creat(2*root+1,mid+1,right);
}
void up_mark(int root)
{
    if(tree[root].mark)
    {
        tree[root].total=tree[root].mark*(tree[root].right-tree[root].left+1);
        if(tree[root].left!=tree[root].right)
            tree[2*root].mark=tree[2*root+1].mark=tree[root].mark;
        tree[root].mark=0;
    }
}
int up_data(int root,int left,int right,int vol)
{
    up_mark(root);
    if(tree[root].left>right || tree[root].right<left)
        return tree[root].total;
    if(tree[root].left>=left&&tree[root].right<=right)
    {
        tree[root].mark=vol;
        up_mark(root);
        return tree[root].total;
        //return tree[root].total=vol*(tree[root].right-tree[root].left+1); //843MS
    }
    return tree[root].total=up_data(2*root,left,right,vol)+up_data(2*root+1,left,right,vol);
}
int calculate(int root,int left,int right)
{
    up_mark(root);
    if(tree[root].left>right || tree[root].right<left)
        return 0;
    if(tree[root].left>=left&&tree[root].right<=right)
        return tree[root].total;
    return tree[root].total=calculate(2*root,left,right)+calculate(2*root+1,left,right);
}
int main()
{
    int t;
    int ces=1;
    scanf("%d",&t);
    while(t--)
    {
        int n,q,i;
        scanf("%d%d",&n,&q);
        for(i=1;i<=n;i++)
            val[i]=1;
        creat(1,1,n);
        int x,y,z;
        for(i=1;i<=q;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            up_data(1,x,y,z);
        }
        printf("Case %d: The total value of the hook is %d.\n",ces++,calculate(1,1,n));
    }
    return 0;
}

POJ3468

将区间的数加上某数

#include <iostream>
#include<cstdio>
using namespace std;
#define MAX 100005
int val[MAX];
struct Node
{
    int left,right;
    __int64 mark,total;
}tree[MAX*3];
__int64 creat(int root,int left,int right)
{
    tree[root].left=left;
    tree[root].right=right;
    tree[root].mark=0;
    if(left==right)
        return tree[root].total=val[left];
    int mid=(right+left)/2;
    return tree[root].total=creat(2*root,left,mid)+creat(root*2+1,mid+1,right);
}
void up_mark(int root)
{
    if(tree[root].mark)
    {
        tree[root].total+=tree[root].mark*(tree[root].right-tree[root].left+1);
        if(tree[root].left!=tree[root].right)
        {
            tree[2*root].mark+=tree[root].mark;
            tree[2*root+1].mark+=tree[root].mark;
        }
        tree[root].mark=0;

    }
}
__int64 up_data(int root,int left,int right,int vol)
{
    up_mark(root);
    if(tree[root].left>right || tree[root].right<left)
        return tree[root].total;
    if(tree[root].left>=left&&tree[root].right<=right)
    {
        tree[root].mark=vol;
        up_mark(root);
        return tree[root].total;
        //return tree[root].total+=vol*(tree[root].right-tree[root].left+1);
    }
    return tree[root].total=up_data(2*root,left,right,vol)+up_data(2*root+1,left,right,vol);
}
__int64 calculate(int root,int left,int right)
{
    up_mark(root);
    if(tree[root].left>right || tree[root].right<left)
        return 0;
    if(tree[root].left>=left&&tree[root].right<=right)
        return tree[root].total;
    return calculate(2*root,left,right)+calculate(2*root+1,left,right);
}
int main()
{
    int n,q;
    while(~scanf("%d%d",&n,&q))
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&val[i]);
        creat(1,1,n);
        while(q--)
        {
            char op;
            scanf("\n%c",&op);
            if(op=='C')
            {
                int x,y,z;
                scanf("%d%d%d",&x,&y,&z);
                up_data(1,x,y,z);
            }
            else
            {
                int x,y;
                scanf("%d%d",&x,&y);
                printf("%I64d\n",calculate(1,x,y));
            }
        }

    }
    return 0;
}

区间染色问题

推荐 浙大ACM培训资料关于线段树的PPT

http://wenku.baidu.com/link?url=FWwB9gUJZZxWJuRNDCMcfBW8ebrEx6nRUJJkmqFcSRA_w1XOfv76lgrO-dLvzxvkh_LbXj05Ck1i5S9OBd0RbJBhLSj6lelePYmzSEi0r9W

POJ2528

题意:

有一些海报要贴墙上,按照先后顺序贴墙上,可以覆盖。问最后能看见几张海报(看见一部分也算)?、

分析:

这题就是:离散化+线段树 的水题。

染色一个区间就把这个区间 刷成一个值就好,最后遍历一遍整个区间看有几个不同的数,就有几张不同的海报。

//Accepted	1584K	125MS	C++	2835B
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXN 40000

int sub[MAXN];
struct node
{
    int ll,rr,l,r;
}qu[MAXN];

/**线段树部分**/

struct Node
{
    int left,right;
    int mark;
    int total;
}tree[3*MAXN];
int creat(int root,int left,int right)
{
    tree[root].left=left;
    tree[root].right=right;
    tree[root].mark=0;
    if(left==right)
        return tree[root].total=-1;
    int mid=(right+left)/2;
    return tree[root].total=creat(2*root,left,mid)+creat(2*root+1,mid+1,right);
}
void up_mark(int root)
{
    if(tree[root].mark)
    {
        tree[root].total=tree[root].mark*(tree[root].right-tree[root].left+1);
        if(tree[root].left!=tree[root].right)
            tree[2*root].mark=tree[2*root+1].mark=tree[root].mark;
        tree[root].mark=0;
    }
}
int up_data(int root,int left,int right,int vol)
{
    up_mark(root);
    if(tree[root].left>right || tree[root].right<left)
        return tree[root].total;
    if(tree[root].left>=left&&tree[root].right<=right)
    {
        tree[root].mark=vol;
        up_mark(root);
        return tree[root].total;
        //return tree[root].total=vol*(tree[root].right-tree[root].left+1); //843MS
    }
    return tree[root].total=up_data(2*root,left,right,vol)+up_data(2*root+1,left,right,vol);
}
int calculate(int root,int left,int right)
{
    up_mark(root);
    if(tree[root].left>right || tree[root].right<left)
        return 0;
    if(tree[root].left>=left&&tree[root].right<=right)
        return tree[root].total;
    return tree[root].total=calculate(2*root,left,right)+calculate(2*root+1,left,right);
}


/**线段树部分**/
int vis[MAXN];
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n,num=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&qu[i].ll,&qu[i].rr);
            sub[num++] = qu[i].ll;
            sub[num++] = qu[i].rr;
        }
        sort(sub,sub+n*2);
        int X = unique(sub,sub+n*2)-sub;
        creat(1,1,X); /**建树**/
       int color=0;
        for(int i=1;i<=n;i++)
        {
            qu[i].l = lower_bound(sub,sub+X,qu[i].ll)-sub+1;
            qu[i].r = lower_bound(sub,sub+X,qu[i].rr)-sub+1;
            color++; /**每个区间的颜色都不同!**/
            up_data(1,qu[i].l,qu[i].r,color);/**覆盖区间**/
        }
        int  ans=0;
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=X;i++)/**遍历染色**/
        {
            int t=calculate(1,i,i);
            //cout<<"----"<<t<<endl;
            if(t!=-1&& !vis[t])
            {
                ans++;
                vis[t] = 1;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
/**
10
5
30 1000
2 30
2 12
12 12000
1 2
**/

POJ2777

题意:一个长区间,初始全部染成颜色1,然后有两种操作:

1. 把区间 A 到 B 刷成 C 颜色。

2. 询问区间 A 到 B 有多少种不同的颜色。 (A 可能大于 B)

这题是赤裸裸的染色题,学会几点:

1. 用位运算来处理颜色。

2.延迟下放更新操作。(被延迟标记 坑了N 次WA。。。)

//Accepted	4796K	438MS	G++	2197B	2014-08-18 20:18:59
//Accepted	4272K	344MS	C++	2298B	2014-08-18 20:22:40
#include <iostream>
#include <cstdio>
using namespace std;
/**线段树部分**/

#define MAX 200001 /**先前开了100万**/
struct Node
{
    int left,right;
    int mark;
    int statu;
}tree[3*MAX];
int creat(int root,int left,int right)
{
    tree[root].left=left;
    tree[root].right=right;
    tree[root].mark=-1; /**延迟标记应该标记为 -1,WA了N次!就是写成0了!0代表1这种颜色,不能不下放!**/
    if(left==right)
        return tree[root].statu=1;
    int mid=(right+left)>>1;
    return tree[root].statu=creat(2*root,left,mid)|creat(2*root+1,mid+1,right);
}
void up_mark(int root)
{
    if(tree[root].mark>=0)
    {
        tree[root].statu=(1<<tree[root].mark);
        if(tree[root].left!=tree[root].right)
            tree[2*root].mark=tree[2*root+1].mark=tree[root].mark;
        tree[root].mark=-1;
    }
}
int up_data(int root,int left,int right,int vol)
{
    up_mark(root);
    if(tree[root].left>right || tree[root].right<left)
        return tree[root].statu;
    if(tree[root].left>=left&&tree[root].right<=right)
    {
        tree[root].mark=vol;
        up_mark(root);
        return tree[root].statu;
    }
    return tree[root].statu=up_data(2*root,left,right,vol)|up_data(2*root+1,left,right,vol);
}
int calculate(int root,int left,int right)
{
    up_mark(root);
    if(tree[root].left>right || tree[root].right<left)
        return 0;
    if(tree[root].left>=left&&tree[root].right<=right)
        return tree[root].statu;
    return calculate(2*root,left,right)|calculate(2*root+1,left,right);
}

/**线段树部分**/
int main()
{
    int L,O,T;
    while(~scanf("%d%d%d",&L,&T,&O))
    {
        creat(1,1,L);
        for(int i=1;i<=O;i++)
        {
            getchar();
            char ch;
            int l,r,color;
            scanf("%c%d%d",&ch,&l,&r);
            if(l>r) swap(l,r);
            if(ch=='C')
            {
              scanf("%d",&color);
              up_data(1,l,r,color-1);
            }
            else
            {
                int st=calculate(1,l,r),ans=0;
                while(st)
                {
                    if(st&1) ans++;
                    st>>=1;
                }
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}

poj3277 

这题需要用到这样的技巧:

二分建树时,这样二分  左子树(left,middle) 右子树(middle,right)

把线段树的叶子节点 设置为 ( l , l+1);

这样可以避免  左子树(left,middle) 右子树(middle+1,right)

导致的中间段没加上面积的情况!

//Accepted	7516K	485MS	C++	1752B	2014-09-26 21:51:23
#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 41000
#define LL __int64 // 注意 楼真实下标,楼面积,楼高,都要用LL。线段树的下标可以用int
struct node1
{
    LL a,b,h;
    bool operator<(const node1 &a )const
    {
        return h<a.h;
    }
}built[MAXN];
LL s[MAXN*2];
int num;
struct node
{
     LL area,mark;
     int l,r;
}tree[MAXN*6]; //因为一个楼,两个坐标,所以线段树范围是 MAXN*2*3
void built_tree(int rt,int l,int r)
{
    tree[rt].l=l;
    tree[rt].r=r;
    tree[rt].area=0;
    tree[rt].mark=0;
    if(l==r-1) return;
    int m=(l+r)>>1;
    built_tree(rt<<1,l,m);
    built_tree(rt<<1|1,m,r);
}
void upmark(int rt)
{
    if(tree[rt].mark)
    {
        int a=tree[rt].l;
        int b=tree[rt].r;
        tree[rt].area=tree[rt].mark*(s[b]-s[a]);
        if(tree[rt].l!=tree[rt].r-1)
        tree[rt<<1].mark=tree[rt<<1|1].mark=tree[rt].mark;
        tree[rt].mark=0;
    }
}
LL updata(int rt,int l,int r,int h) // 这里返回没用LL WA几发。。
{
    upmark(rt);
    if(tree[rt].l>=r || tree[rt].r<=l)
    return tree[rt].area;
    if(tree[rt].l>=l&&tree[rt].r<=r)
    {
        tree[rt].mark=h;
        upmark(rt);
        return tree[rt].area;
    }
    return tree[rt].area=updata(rt<<1,l,r,h)+updata(rt<<1|1,l,r,h);;
}
int main()
{
    int N;
    scanf("%d",&N);
    num=0;
    for(int i=1;i<=N;i++)
    {
        scanf("%I64d%I64d%I64d",&built[i].a,&built[i].b,&built[i].h);
        s[num++]=built[i].a;
        s[num++]=built[i].b;
    }
    sort(s,s+num);
    int X=unique(s,s+num)-s;
    sort(built+1,built+1+N);
    built_tree(1,0,X);
    for(int i=1;i<=N;i++)
    {
        int a=lower_bound(s,s+X,built[i].a)-s;
        int b=lower_bound(s,s+X,built[i].b)-s;
        updata(1,a,b,built[i].h);
    }
    printf("%I64d\n",tree[1].area);

    return 0;
}

POJ2828

题意:N 个人插队买票,给出两个值 id 和 val

表示 这个人插在第 id 个人的后面,他的价值为 val

问最后的输出顺序。。

分析:

这我真的一开始没想到是线段树,真的是题做少了。

如果正向的考虑,那么每插入一个进来,就会改变相对顺序,用链表肯定是超时的。

学会逆向思考,

从最后一个人开始,那么他的位置是肯定确定的,就是他前面必须有 id个人。

那么同理放好其它的人。

可以看下:

http://www.cnblogs.com/CheeseZH/archive/2012/04/29/2476134.html

的图示;

//Accepted	10736K	1594MS	C++	1543B
#include <iostream>
#include<cstdio>
using namespace std;
#define MAXN 300000
struct node
{
    int id,val;
}p[MAXN];
/**线段树部分**/
struct Node
{
    int left,right,blank,val;
}tree[3*MAXN];
int creat(int root,int left,int right)
{
    tree[root].left=left;
    tree[root].right=right;
    if(left==right) return tree[root].blank=1;
    int a,b,mid;
    mid=(right-left)/2+left;
    a=creat(2*root,left,mid);
    b=creat(2*root+1,mid+1,right);
    return tree[root].blank=a+b;
}
int find(int root,int key,int v)
{
    int l = 2*root;
    int r=  2*root+1;
    if(tree[root].left==tree[root].right)
    {
        tree[root].val = v;
        return tree[root].blank=0;
    }
    if(tree[l].blank < key) find(r,key-tree[l].blank,v);
    else find(l,key,v);
    return tree[root].blank=tree[l].blank+tree[r].blank;
}
int ans[MAXN],num;
void show(int root)
{
    if(tree[root].left==tree[root].right)
    {
        ans[num++] = tree[root].val;
        return ;
    }
    show(2*root);
    show(2*root+1);
}
/**线段树部分**/
int main()
{
    int N;
    while(~scanf("%d",&N))
    {
        for(int i=1;i<=N;i++)
        {
            scanf("%d%d",&p[i].id,&p[i].val);
        }
        creat(1,1,N);
        num=0;
        for(int i=N;i>=1;i--)
        {
            find(1,p[i].id+1,p[i].val);
        }
        show(1);
        printf("%d",ans[0]);
        for(int i=1;i<num;i++)
        {
            printf(" %d",ans[i]);
        }
        printf("\n");

    }
    return 0;
}

POJ2886

题意:

N个人顺时针站成一个圈,每个人手中有一张牌,牌上一个整数(不为0,可能为负数),从第k个开始出去,

他手中的整数,若是正整数就是顺时针的第几个继续出去,负数就是逆时针的第几个继续出去。

出去的第 i 个人 , p( i  )指示 i 的约数个数。

问:约数个数最大的 那个人。

分析:

类似约瑟夫环,但是约瑟夫环,报第几个数出去是固定的。

首先,学到了个新知识--反素数:如果N 是N以内约数个数最多的数,则N就是一个反素数。

题目给出一个 N 即人的个数,那么只需要打出给出范围内的 所有反素数就可以找出 N以内约数个数最多的是 第几个。

现在第几个人是答案已经出来了,只需要知道这个人的名字就行,就是要知道他是谁。

如果用队列模拟这个过程,肯定超时,因为光是一次出队,都有可能执行 10^8。

上面已经做了个这样的题,就是线段树上找位置的。。

那么同理只需要每次找到位置就行了。。

注意一点:如果牌上是正整数 k ,那么顺时针找到的就是 p+k ,因为 p 这个人出队了, 所以p+k的相对顺序改变了,所有应该是编号 p+k-1 的人出去。

如果是负数,那么相对顺序不会改变。就是p+k。。 画个图就可以明白!

lower_bound(数组头,数组尾,k) 找出的是第一个小于 k 的数的上一个数下标,或者是等于k的数的下标。

没注意 RE了好多次。。 

a存的是反素数,b存的是对应a中反素数 的约数个数。

//Accepted	24244K	1344MS	C++	1960B	2014-08-19 16:50:13
#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 600000
const int a[37]={1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,
25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,500001};
const int b[37]={1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,80,84,90,96,100,108,120,128,144,
160,168,180,192,200,1314521};
int N,k;
struct node
{
    char name[20];
    int id;
}stu[MAXN];
/**线段树部分**/
struct Node
{
    int left,right,blank;
}tree[3*MAXN];
int creat(int root,int left,int right)
{
    tree[root].left=left;
    tree[root].right=right;
    if(left==right)
    {
         return tree[root].blank=1;
    }
    int a,b,mid;
    mid=(right-left)/2+left;
    a=creat(2*root,left,mid);
    b=creat(2*root+1,mid+1,right);
    return tree[root].blank=a+b;
}
int find(int root,int key,int &ans)
{
    int l = 2*root;
    int r=  2*root+1;
    if(tree[root].left==tree[root].right)
    {
        ans=tree[root].left;
        return tree[root].blank=0;
    }
    if(tree[l].blank < key) find(r,key-tree[l].blank,ans);
    else find(l,key,ans);
    return tree[root].blank=tree[l].blank+tree[r].blank;
}
/**线段树部分**/
int search(int n)
{
    int tag=lower_bound(a,a+37,n)-a;
    if(n<a[tag]) tag--; /**如果不是等于的情况,这里就是第一个大于n的数,所以要--**/
    return tag;
}
void solve()
{
    creat(1,1,N);
    int goal=search(N);
    int ID=0; //从标号为ID 的人开始
    stu[0].id=0;
    for(int i=0;i<a[goal];i++)/**模拟队**/
    {
        int mod=tree[1].blank;
        if(stu[ID].id>0) k= ((k + stu[ID].id- 2)%mod+mod)%mod + 1;//因为从1开始所以就多减1 改变了相对顺序 总共就-2
        else k= ((k + stu[ID].id-1)%mod+mod)%mod + 1;
        find(1,k,ID);
    }
    printf("%s %d\n",stu[ID].name,b[goal]);
}
int main()
{
    while(~scanf("%d%d",&N,&k))
    {
        for(int i=1;i<=N;i++)
        {
            scanf("%s%d",stu[i].name,&stu[i].id);
        }
        solve();
    }
    return 0;
}

省赛题---高桥低桥

首先建树肯定拿10^5 的下标建树!

只需  每次  在桥数组中找洪水的值 的上下界。相当于去淹下标!

最后就遍历一次各个节点,求出ans。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 110000
int val[MAX];
int n,m,k;
struct Node
{
    int left,right;
    int mark,total;
}tree[MAX*3];
int creat(int root,int left,int right)
{
    tree[root].left=left;
    tree[root].right=right;
    tree[root].mark=0;
    if(left==right)
        return tree[root].total=0;
    int mid=(right+left)/2;
    return tree[root].total=creat(2*root,left,mid)+creat(root*2+1,mid+1,right);
}
void up_mark(int root)
{
    if(tree[root].mark)
    {
        tree[root].total+=tree[root].mark*(tree[root].right-tree[root].left+1);
        if(tree[root].left!=tree[root].right)
        {
            tree[2*root].mark+=tree[root].mark;
            tree[2*root+1].mark+=tree[root].mark;
        }
        tree[root].mark=0;

    }
}
int up_data(int root,int left,int right,int vol)
{
    up_mark(root);
    if(tree[root].left>right || tree[root].right<left)
        return tree[root].total;
    if(tree[root].left>=left&&tree[root].right<=right)
    {
        tree[root].mark=vol;
        up_mark(root);
        return tree[root].total;
    }
    return tree[root].total=up_data(2*root,left,right,vol)+up_data(2*root+1,left,right,vol);
}
int calculate(int root,int left,int right)
{
    up_mark(root);
    if(tree[root].left>right || tree[root].right<left)
        return 0;
    if(tree[root].left>=left&&tree[root].right<=right)
        return tree[root].total;
    return calculate(2*root,left,right)+calculate(2*root+1,left,right);
}

int main()
{
    int cas=1;
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        for(int i=1;i<=n;i++) scanf("%d",&val[i]);
        sort(val+1,val+1+n);
        creat(1,1,n);
        int cur=1;
        for(int i=1;i<=m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            int l=upper_bound(val+1,val+n+1,cur)-val;
            int r=upper_bound(val+1,val+n+1,a)-val;   r--;
            cur=b;
            if(l<=r) up_data(1,l,r,1);
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            if(calculate(1,i,i)>=k) ans++;;
        }
        printf("Case %d: %d\n",cas++,ans);
    }
    return 0;
}

区间合并

HDU1540 

题意:D代表破坏村庄,R代表修复最后被破坏的那个村庄,Q代表询问包括x在内的最大连续区间是多少

分析:线段树节点 添加 三个域:当前区间最大连续长度 MAX ,左端点最大连续长度 , 右端点最大连续长度。

R 修复时,用栈来保存就行。

参考代码:

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
using namespace std;

const int maxn = 50000+10;

int n,m;
int s[maxn],top;//s为模拟栈

struct node
{
    int l,r;
    int ls,rs,ms;//ls,左端最大连续区间,rs右端最大连续区间,ms区间内最大连续区间
} a[maxn<<2];

void init(int l,int r,int i)
{
    a[i].l = l;
    a[i].r = r;
    a[i].ls = a[i].rs = a[i].ms = r-l+1;
    if(l!=r)
    {
        int mid = (l+r)>>1;
        init(l,mid,i*2);
        init(mid+1,r,2*i+1);
    }
}

void insert(int i,int t,int x)
{
    if(a[i].l == a[i].r)
    {
        if(x==1)
            a[i].ls = a[i].rs = a[i].ms = 1;//修复
        else
            a[i].ls = a[i].rs = a[i].ms = 0;//破坏
        return ;
    }
    int mid = (a[i].l+a[i].r)>>1;
    if(t<=mid)
        insert(2*i,t,x);
    else
        insert(2*i+1,t,x);
    a[i].ls = a[2*i].ls;//左区间
    a[i].rs = a[2*i+1].rs;//右区间
    a[i].ms = max(max(a[2*i].ms,a[2*i+1].ms),a[2*i].rs+a[2*i+1].ls);//父亲区间内的最大区间必定是,左子树最大区间,右子树最大区间,左右子树合并的中间区间,三者中最大的区间值
    if(a[2*i].ls == a[2*i].r-a[2*i].l+1)//左子树区间满了的话,父亲左区间要加上右孩子的左区间
        a[i].ls += a[2*i+1].ls;
    if(a[2*i+1].rs == a[2*i+1].r-a[2*i+1].l+1)//同理
        a[i].rs += a[2*i].rs;
}

int query(int i,int t)
{
    if(a[i].l == a[i].r || a[i].ms == 0 || a[i].ms == a[i].r-a[i].l+1)//到了叶子节点或者该访问区间为空或者已满都不必要往下走了
        return a[i].ms;
    int mid = (a[i].l+a[i].r)>>1;
    if(t<=mid)
    {
        if(t>=a[2*i].r-a[2*i].rs+1)//因为t<=mid,看左子树,a[2*i].r-a[2*i].rs+1代表左子树右边连续区间的左边界值,如果t在左子树的右区间内,则要看右子树的左区间有多长并返回
            return query(2*i,t)+query(2*i+1,mid+1);
        else
            return query(2*i,t);//如果不在左子树的右边界区间内,则只需要看左子树
    }
    else
    {
        if(t<=a[2*i+1].l+a[2*i+1].ls-1)//同理
            return query(2*i+1,t)+query(2*i,mid);
        else
            return query(2*i+1,t);
    }
}

int main()
{
    int i,j,x;
    char ch[2];
    while(~scanf("%d%d",&n,&m))
    {
        top = 0;
        init(1,n,1);
        while(m--)
        {
            scanf("%s",ch);
            if(ch[0] == 'D')
            {
                scanf("%d",&x);
                s[top++] = x;
                insert(1,x,0);
            }
            else if(ch[0] == 'Q')
            {
                scanf("%d",&x);
                printf("%d\n",query(1,x));
            }
            else
            {
                if(x>0)
                {
                    x = s[--top];
                    insert(1,x,1);
                }
            }
        }
    }

    return 0;
}

可持久化线段树

求第k小(第k大)。现在已经做的分为2类:(给定1~n的序列)

第一类:不断询问 1~m 中的第k小(第k大)。《优先队列,堆,线段树,Treap》

第二类:不断询问 某一区间 (m1,m2) 的第k小(第k大)。----比前一种更一般的情况。《主席树,Treap》

第三类:在第二类上还可以不断修改。----比前一种更一般的情况。

第一类不再赘述啦!

这里是第二类.

poj2104,poj2761,hdu2665.

#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 100010
int n,m;
int ans[maxn];
struct Node
{
    int a,b,id;
}num[maxn];
bool cmp1(Node A,Node B)
{
    return A.a<B.a;
}
bool cmp2(Node A,Node B)
{
    return A.id<B.id;
}
struct T_node
{
    T_node *left;
    T_node *right;
    int sum;
}*root[maxn],nod[maxn*20];
int tot;
void built(T_node*&p,int l,int r)
{
    p=&nod[tot++];
    p->sum=0;
    if(l==r) return ;
    int m=(l+r)>>1;
    built(p->left,l,m);
    built(p->right,m+1,r);
}
void updata(T_node*p,T_node*&q,int t,int l,int r)
{
    q=&nod[tot++];
    q->left=p->left;
    q->right=p->right;
    q->sum=p->sum+1;
    if(l==r)return ;
    int m=(l+r)>>1;
    if(t<=m) updata(p->left,q->left,t,l,m);
    else       updata(p->right,q->right,t,m+1,r);
}
int query(T_node*p,T_node*q,int k,int l,int r)
{
    if(l==r) return l;
    int m=(l+r)>>1;
    int cnt=q->left->sum - p->left->sum;
    if(k<=cnt)
        return query(p->left,q->left,k,l,m);
    else
        return query(p->right,q->right,k-cnt,m+1,r);
}
void gogogo()
{
    int i;
    tot=0;
    int l,r,k;
    for( i=1;i<=n;i++)
    {
        scanf("%d",&num[i].a);
        num[i].id=i;
    }

    sort(num+1,num+1+n,cmp1);
	/**求出每个的相对大小,并去重另保存ans**/
    int p;
    int sb=1;
    num[1].b=sb;
    ans[sb]=num[1].a;
    p=num[1].a;
    for( i=2;i<=n;i++)
    {
        if(p!=num[i].a)
        {
            p=num[i].a;
            sb++;
        }
        num[i].b=sb;
        ans[sb]=num[i].a;
    }
	/**按id排回来,建线段树! **/
    sort(num+1,num+1+n,cmp2);
	/**先建一个root[0]树--相当于模板**/
    built(root[0],1,sb);
	/**序列每个数都建一棵前缀线段树!**/
	/**( 保存了前一棵的历史!)**/
    for( i=1;i<=n;i++) updata(root[i-1],root[i],num[i].b,1,sb);/**这里果然傻逼了!把sb搞成p啦**/
	/**两个前缀树相减==所求区间**/
	/**(返回的是相对大小,就到ans里找序列原来的值)**/
    while(m--)
    {
        scanf("%d%d%d",&l,&r,&k);
        int id=query(root[l-1],root[r],k,1,sb);
        printf("%d\n",ans[id]);
    }
}
int main()
{
   // int T;
    //scanf("%d",&T);
    while(~scanf("%d%d",&n,&m))
    {
       //;
        gogogo();
    }
    return 0;
}

抱歉!评论已关闭.