线段树

HDU 3275 Light

Posted on

题意很简单 给你一串长度为n只有0,1的字符串,每次操作固定操作m长度的子串 问至少多少次才能使字符串全为 1

一开始没啥思路 后来发现每次找到第一个 0 的位置再以他为起点进行更新,重复操作要么全为 1 要么无法更新(别问我为什么,这是我队友跟我说的,我负责码线段树

这题我觉得有两个坑点

1.当m==0 的时候 这还能玩??一个字符都不让动 出题的人也是脑残,,,总是动一些小条件 总之这时候就输出他的其实状态 ,即如果全为 1 输出0 否则 输出-1

2.延迟更新的时候,这个就需要对线段树有一定的理解了 因为是延迟更新,在还未更新的时候可能存在对某一个区间多次标记 标记奇数次次就是0,1反转,偶数次就是不变咯 这里我对lazy标记进行异或,一切迎刃而解

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define root tree[id]
#define lson tree[id<<1]
#define rson tree[id<<1|1]

using namespace std;
const int maxn=100005;
int st,en;
struct segtree
{
    int le,ri;
    int sum,len,d;
} tree[maxn*4];
char ch[maxn];

void pushdown(int id)
{
    if(root.d&&root.le!=root.ri)
    {
        lson.sum=lson.len-lson.sum;
        rson.sum=rson.len-rson.sum;
        lson.d^=1;
        rson.d^=1;
        root.d=0;
    }
}

void build_tree(int id,int le,int ri)
{
    root.le=le,root.ri=ri,root.len=ri-le+1,root.d=0;
    if(le==ri)
    {
        root.sum=ch[le]-'0';
        return ;
    }
    int mid=(le+ri)>>1;
    build_tree(id<<1,le,mid);
    build_tree(id<<1|1,mid+1,ri);
    root.sum=lson.sum+rson.sum;
}

int query(int id,int le,int ri)
{
    int ans;
    if(root.len==root.sum) return 0;
    if(le==ri) return le;
    pushdown(id);
    int mid=(le+ri)>>1;
    if(ans=query(id<<1,le,mid)) return ans;
    if(ans=query(id<<1|1,mid+1,ri)) return ans;
    root.sum=lson.sum+rson.sum;
    return 0;
}

void update(int id,int le,int ri)
{
    if(st<=le&&ri<=en)
    {
        root.sum=root.len-root.sum;
        root.d^=1;
        return ;
    }
    pushdown(id);
    int mid=(le+ri)>>1;
    if(st<=mid) update(id<<1,le,mid);
    if(en>mid) update(id<<1|1,mid+1,ri);
    root.sum=lson.sum+rson.sum;
}

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(m==0&&n==0) break;
        getchar();
        scanf("%s",ch+1);
        build_tree(1,1,n);
        if(m==0)
        {
            if(tree[1].sum==tree[1].len) printf("0\n");
            else printf("-1\n");
            continue;
        }
        bool flag=true;
        int step=0;
        while(st=query(1,1,n))
        {
            en=st+m-1;
            if(en>n)
            {
                flag=false;
                break;
            }
            step++;
            update(1,1,n);
        }
        if(flag) printf("%d\n",step);
        else printf("-1\n");
    }
    return 0;
}
线段树

HDU 1828 Picture

Posted on

扫描线第二题

求周长

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=20010;
int sum[maxn<<2],segnum[maxn<<2],flag[maxn<<2];//sum与上面一样   segnum记录未被覆盖的竖边数量   flag 同上
bool lseg[maxn<<2],rseg[maxn<<2];////表示某个区间最左边和最右边是否有下底边多于上底边
struct node
{
    int lx,rx;
    int y,d;
    node(){}
    node(int _lx,int _rx,int _y,int _d)
    {
        lx=_lx,rx=_rx,y=_y,d=_d;
    }
    bool operator <(const node& a)const
    {
        if(y==a.y) return d>a.d;
        return y<a.y;
    }
}lines[maxn];

void pushup(int id,int le,int ri)
{
    if(flag[id])
    {
        sum[id]=ri-le+1;
        lseg[id]=rseg[id]=true;
        segnum[id]=2;
    }
    else if(le==ri) sum[id]=lseg[id]=rseg[id]=segnum[id]=0;
    else
    {
        sum[id]=sum[id<<1]+sum[id<<1|1];
        segnum[id]=segnum[id<<1]+segnum[id<<1|1];
        lseg[id]=lseg[id<<1];
        rseg[id]=rseg[id<<1|1];
        if(rseg[id<<1]&&lseg[id<<1|1]) segnum[id]-=2;//矩形相交
    }
}

void update(int id,int le,int ri,int st,int en,int add)
{
    if(st<=le&&ri<=en)
    {
        flag[id]+=add;
        pushup(id,le,ri);
        return ;
    }
    int mid=(le+ri)>>1;
    if(st<=mid) update(id<<1,le,mid,st,en,add);
    if(en>mid) update(id<<1|1,mid+1,ri,st,en,add);
    pushup(id,le,ri);
}

int main()
{
    int n,x1,y1,x2,y2;
    while(scanf("%d",&n)!=EOF)
    {
        int ss=inf,ee=-inf;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            lines[2*i+1]=node(x1,x2,y1,1);
            lines[2*i+2]=node(x1,x2,y2,-1);
            ss=min(x1,ss),ee=max(x2,ee);
        }
        n*=2;
        sort(lines+1,lines+1+n);
        int ans=0,last=0;
        for(int i=1;i<=n;i++)
        {
            update(1,ss,ee,lines[i].lx,lines[i].rx-1,lines[i].d);
            ans+=segnum[1]*(lines[i+1].y-lines[i].y);
            ans+=abs(sum[1]-last);//底边增加的长度
            last=sum[1];
        }
        printf("%d\n",ans);
    }
    return 0;
}
线段树

HDU 1542 Atlantis

Posted on

线段树扫描线入门题

扫描线扫描线 一开始看的时候真的是看的我整个人都不好了 全程懵逼状态 自信心严重受损 最后休整了一天再来看它 用纸和笔动手比划了一点时间才终于算是稍微明白了一点 所以我的建议还是大家自己动手比划一下 毕竟实践出真知 网上的那些题解虽然有图 但他们的语言也只有他们自己读得懂 自己动过手之后才知道他整个过程都是这么精妙

据我所知 线段树的扫描线一般只有两个用处 一个是求覆盖的矩形面积 和覆盖的矩形周长

(毕竟我是鶸 还没碰到过其他用法的扫描线

这题 求面积 数据大 需要离散化

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int maxn=4100;
const double eps=1e-6;
int n,len,flag[maxn];
double ans,xx[maxn],sum[maxn];//xx用于离散化     sum记录扫描线边长   并聚合在sum[1]上
struct line
{
    double lx,rx;
    double y;
    int d;
    line(){}
    line(double _lx,double _rx,double _y,int _d)
    {
        lx=_lx,rx=_rx,y=_y,d=_d;
    }
    bool operator <(const line& a) const
    {
        return y<a.y;
    }
}lines[maxn];

int fin(double a)
{
    int l=1,r=len,mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(xx[mid]==a) return mid;
        else if(xx[mid]>a) r=mid-1;
        else l=mid+1;
    }
    return l;
}

void pushup(int id,int le,int ri)//这是最难理解的一步    我就是卡在了这里   之后比划过才知道玄妙
{
    if(flag[id]) sum[id]=xx[ri+1]-xx[le];
    else if(le==ri) sum[id]=0;
    else sum[id]=sum[id<<1]+sum[id<<1|1];
}

void update(int id,int le,int ri,int st,int en,int add)
{
    if(st<=le&&ri<=en)
    {
        flag[id]+=add;
        pushup(id,le,ri);
        return ;
    }
    int mid=(le+ri)>>1;
    if(st<=mid) update(id<<1,le,mid,st,en,add);
    if(en>mid) update(id<<1|1,mid+1,ri,st,en,add);
    pushup(id,le,ri);
}

int main()
{
    double x1,y1,x2,y2;
    int time=0;
    while(scanf("%d",&n),n)
    {
        memset(flag,0,sizeof flag);
        memset(sum,0,sizeof sum);
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            xx[2*i+1]=x1,xx[2*i+2]=x2;
            lines[2*i+1]=line(x1,x2,y1,1);
            lines[2*i+2]=line(x1,x2,y2,-1);
        }
        n*=2,len=1,ans=0;
        sort(xx+1,xx+1+n);
        sort(lines+1,lines+1+n);
        for(int i=2;i<=n;i++) if(xx[i]!=xx[i+1]) xx[++len]=xx[i];//去重
        for(int i=1;i<n;i++)
        {
            int l=fin(lines[i].lx);
            int r=fin(lines[i].rx)-1;
            update(1,1,len,l,r,lines[i].d);
            ans+=sum[1]*(lines[i+1].y-lines[i].y);
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n",++time,ans);
    }
    return 0;
}
线段树

POJ 2777 Count Color 附带线段树小结

Posted on

POJ 2777 题解

好久没这么兴奋过了
poj2777 这绝对是 是道线段树的好题 至少对我来说
一开始看这题的时候 看了一下数据范围就知道了 可以用位运算 进行状态压缩
我想要自己做 对 完全不看题解 结果问题就慢慢显现出来了
尤其是我对pushdown操作的理解完全不够 最后还是自己动笔好好画了一下模拟几遍才恍然大悟 我真是太辣鸡了

先附上 代码和注释 最后写上我对线段树基础操作的理解(包括以前写的一些 觉得太基础了就没卸载博客上 今天就在这里汇总一下

AC Code(G++好像就超了 C++能过

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#define root tree[id]
#define lson tree[id<<1]
#define rson tree[id<<1|1]

using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=100005;
int st,en,n,m,qnum;
long long change,col;//col是最后query的最终颜色汇总   最后对其位操作计算颜色数量即可
struct segtree
{
    int le,ri;
    long long color,change_color;//这段区间上的颜色总和   延迟更新标记
} tree[maxn<<2];

inline void pushup(int id)
{
    root.color=lson.color|rson.color;//颜色汇总
}

inline void pushdown(int id)
{
    if(root.change_color!=0&&root.le!=root.ri)
    {
        long long cc=root.change_color;
        lson.change_color=rson.change_color=lson.color=rson.color=cc;
        root.change_color=0;
    }
}

void build_tree(int id,int le,int ri)
{
    root.le=le,root.ri=ri,root.change_color=0;
    root.colo=1;
    if(le==ri) return;
    int mid=(le+ri)/2;
    build_tree(id<<1,le,mid);
    build_tree(id<<1|1,mid+1,ri);
}

void update(int id)
{
    int le=root.le,ri=root.ri;
    if(st<=le&&ri<=en)
    {
        root.color=root.change_color=change;
        return ;
    }
    pushdown(id);
    int mid=(le+ri)/2;
    if(st<=mid) update(id<<1);
    if(en>mid) update(id<<1|1);
    pushup(id);
}

void query(int id)
{
    int le=root.le,ri=root.ri;
    if(st<=le&&ri<=en)
    {
        col=col|root.color;
        return ;
    }
    pushdown(id);//牛逼啊!!!!真的牛逼!!!!pushdown这个位置  沃夫
    int mid=(le+ri)/2;
    if(st<=mid) query(id<<1);
    if(en>mid) query(id<<1|1);
}

int main()
{
    while(scanf("%d%d%d",&n,&m,&qnum)!=EOF)
    {
        char op[2];
        build_tree(1,1,n);
        while(qnum--)
        {
            scanf("%s",op);
            if(op[0]=='C')
            {
                scanf("%d%d%I64d",&st,&en,&change);
                if(st>en) swap(st,en);
                change=1<<(change-1);
                update(1);
            }
            else
            {
                scanf("%d%d",&st,&en);
                if(st>en) swap(st,en);
                int ans=0;
                col=0;//col初始化
                query(1);
                for(int i=0; i<m; i++)
                    if((col>>i)&1) ans++;
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}

线段树小结

下面是对线段树的理解(从小白开始的历程 不喜勿喷…………

线段树的精髓 就在于 它永远都是从根节点出发

1.关于query以及update时判断的标志 st<=le&&ri<=en 的理解
假如区间为 1-7 要求求出 2-6的值
并不是说 什么2-3 2-4 3-5 3-6 什么乱七八糟的都可以满足条件
首先由于线段树的性质 如果该节点 在区间内部 那么只要我一个return 该节点的所有叶子节点就不会再出现,更不用说是该节点内的数字
也就是说 假如我 1-4 满足条件 那么1-2 3-4都不会再出现 1,2,3,4也不会再次被访问到
所以 如此继续向下查询 线段式地返回 最后就是所要求的区间值

2.关于pushdown与pushup的理解
就如字面意思 假如 一个节点更新 那么它的叶子节点和父亲节点都需要更新
如果每次都这么向下向上更新 百分之8000要超时 效率低下
所以我们先暂时向下更新 一直向下更新 到最后再一起向上更新 如此就能实现所有更新

3.关于pushdown和lazy标记的详解

现在才知道为什么总是说线段树对递归的要求稍微高了一些

以此题为例 在update时 在此区间更新后 直接return 这个区间和他的子区间都不会被再次访问

并不是说不会更新 而是他觉得暂时没必要

当query操作时 如果你不会访问他的子区间 他就不会更新

eg 总区间是 1-12 你更新 4-5区间 查询 5-6区间

当你访问到4-5区间时 发现没有符合条件 他才会向下更新 4和5节点

这样说来可能还有优化的余地 就是当切仅当你要查询的区间与 你当前访问的区间有交集的时候 才向下更新 也不失为一个方法 有兴趣的可以尝试一下

啊! 果然 算法的优化是无止尽的!!