欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

kuangbin线段树专题(已更一半

程序员文章站 2022-07-13 11:31:13
...

啊。。这个专题才开的时候,学校就恢复了vj挂题的制度,加上各种比赛,以及文化课之类的,导致这个专题写的好慢。。。写完后也一直没时间总结博客。。就是懒…
-------------------------------------------------------------------------
感觉…自己越来越没有斗志了…天天像个废物一样,就只会写几个傻瓜题,比赛也是签个到就开始罚坐。。学个新的图论算法几乎要自闭,,
图论也太难了吧!!!
图论也太难了吧!!!
图论也太难了吧!!!
二分图写着写着就遇到了HK算法,然后看不懂,,只会套板子,写着写着觉得放到暑假集训再处理这个二分图吧,不如先去把次小生成树完善一下,,然后写了四个题就遇到了最小树形图。。。再次自闭。。。。
还是先把这个线段树专题总结一下吧
-------------------------------------------------------------------------
就三个题没补
一个是多重lazy标记。。写吐了。真不想写这个(不会。。
还有一个是扫描线处理周长问题(只学了处理面积,周长一时半会没看会。
最后一个就是很玄学的看都看不懂的题目。。说是三维线段树????
我太菜了…
-------------------------------------------------------------
开始正文
专题链接
A - 敌兵布阵 HDU - 1166
kuangbin线段树专题(已更一半
单点修改 区间查询
最简单的线段树操作了,不如放个树状数组上来吧

int lowbit(int x){return x&(-x);}
int arr[maxn];
void updata(int pos,int val,int n){
    while(pos<=n){
        arr[pos]+=val;
        pos+=lowbit(pos);
    }
}
int query(int pos){
    int ans=0;
    while(pos>0){
        ans+=arr[pos];
        pos-=lowbit(pos);
    }
    return ans;
}
int cas=0;
void solve(){
    ms(arr,0);
    int n;cin>>n;
    rep(i,1,n){
        int tmp;cin>>tmp;
        updata(i,tmp,n);
    }
    string ope;
    int a,b;
    cout<<"Case "<<++cas<<":"<<endl;
    while(cin>>ope&&ope[0]!='E'){
        cin>>a>>b;
        if(ope[0]=='A'){
            updata(a,b,n);
        }else if(ope[0]=='S'){
            updata(a,-b,n);
        }else{
            cout<<query(b)-query(a-1)<<endl;
        }
    }
}

B - I Hate It HDU - 1754
kuangbin线段树专题(已更一半
区间查询,单点更新
还是基本操作。。上题放树状数组,那这个就放线段树把

struct node{
    int l,r;
    int val;
}tree[maxn<<2];
void build(int rt,int l,int r){
    tree[rt].l=l;
    tree[rt].r=r;
    if(l==r){
        scanf("%d",&tree[rt].val);
        return ;
    }
    build(lson);
    build(rson);
    tree[rt].val=max(tree[ls].val,tree[rs].val);
}
void updata(int rt,int a,int b){
    int l=tree[rt].l,r=tree[rt].r;
    if(l==r&&r==a){
        tree[rt].val=b;
    }else{
        if(a<=md){
            updata(ls,a,b);
        }else{
            updata(rs,a,b);
        }
        tree[rt].val=max(tree[ls].val,tree[rs].val);
    }
}
int query(int rt,int a,int b){
    int l=tree[rt].l,r=tree[rt].r;
    if(l==a&&r==b){
        return tree[rt].val;
    }else{
        if(b<=md){
            return query(ls,a,b);
        }else if(a>=md+1){
            return query(rs,a,b);
        }else{
            return max(query(ls,a,md),query(rs,md+1,b));
        }
    }
}
void solve(){
    int n,m;while(~scanf("%d %d",&n,&m)){
        build(1,1,n);
        while(m--){
            char str[30];int a,b;
            scanf("%s %d %d",str,&a,&b);
            if(str[0]=='Q'){
                cout<<query(1,a,b)<<endl;
            }else{
                updata(1,a,b);
            }
        }
    }
}

C - A Simple Problem with Integers POJ - 3468
kuangbin线段树专题(已更一半
嗯。。区间更新,区间查询
考察的是lazy标记的思想,单点修改必定会超时的
算是lazy标记入门题
我想不明白的是。。用scanf就一直wa…改成cin…就过了
迷惑。。。

struct node{
    ll l,r;
    ll val,tag;
}tree[maxn<<2];
void build(ll rt,ll l,ll r){
    tree[rt].l=l;
    tree[rt].r=r;
    tree[rt].tag=0;
    if(l==r){
        cin>>tree[rt].val;
    }else{
        build(lson);
        build(rson);
        tree[rt].val=tree[ls].val+tree[rs].val;
    }
}
inline void push_down(ll rt){
    if(!tree[rt].tag){
        return ;
    }
    ll l=tree[rt].l,r=tree[rt].r;
    tree[ls].tag+=tree[rt].tag;
    tree[rs].tag+=tree[rt].tag;
    tree[ls].val+=(md-l+1)*tree[rt].tag;
    tree[rs].val+=(r-md)*tree[rt].tag;
    tree[rt].tag=0;
}
void updata(ll rt,ll a,ll b,ll c){
    ll l=tree[rt].l,r=tree[rt].r;
    if(l==a&&r==b){
        tree[rt].tag+=c;
        tree[rt].val+=(r-l+1)*c;
        return ;
    }else{
        push_down(rt);
        if(b<=md){
            updata(ls,a,b,c);
        }else if(a>=md+1){
            updata(rs,a,b,c);
        }else{
            updata(ls,a,md,c);
            updata(rs,md+1,b,c);
        }
        tree[rt].val=tree[ls].val+tree[rs].val;
    }
}
ll query(ll rt,ll a,ll b){
    ll l=tree[rt].l,r=tree[rt].r;
    if(l==a&&r==b){
        return tree[rt].val;
    }else{
        push_down(rt);
        if(b<=md){
            return query(ls,a,b);
        }else if(a>=md+1){
            return query(rs,a,b);
        }else{
            return query(ls,a,md)+query(rs,md+1,b);
        }
    }
}
void solve(){
    ll n,q;
    cin>>n>>q;
    build(1,1,n);
    while(q--){
        char ope[10];
        ll a,b,c;
        cin>>ope>>a>>b;
        if(ope[0]=='Q'){
            cout<<query(1,a,b)<<endl;
        }else{
            cin>>c;
            updata(1,a,b,c);
        }
    }
    
}

D - Mayor’s posters POJ - 2528
kuangbin线段树专题(已更一半
kuangbin线段树专题(已更一半
呃。线段树染色+离散化处理
数据太大了,需要离散化一下,不然无法建树
注意这里每一个点代表的是片段的颜色,比如3,4,5,6,7
4,6之间,3,4之间,6,7之间依次染了色,然后你离散化就成了,3,4,6,7,对应1,2,3,4,然后你记录出来的就是1,2有颜色,3,4有颜色,这就忽略了一种颜色!!,原本的应该是,3,4 ,,,5,,6,7
所以离散化的时候,对于每一个长度大于1的区间,就需要额外添加一个数进去来确保正确度!即

for(ll i=1;i<=sz-1;i++){
        if(v[i]-v[i-1]>1){
            v.pb(v[i-1]+1);
        }
    }

注意这个题染的是点,和下面那个题不同,这点要区分开
然后就没啥好说的了,上代码吧,注意线段树离散化的操作

struct node{
    ll l,r;
    ll val;
}tree[maxn<<4];
struct IUPUT{
    ll l,r;
}input[maxn];
ll vis[maxn<<4];
vector<ll>v;
ll ans=0;
void build(ll rt,ll l,ll r){
    tree[rt].l=l;
    tree[rt].r=r;
    tree[rt].val=-1;
    if(l==r){
        return ;
    }
    build(lson);
    build(rson);
}
inline void push_down(ll rt){
    ll l=tree[rt].l,r=tree[rt].r;
    if(tree[rt].val!=-1&&l!=r){
        tree[ls].val=tree[rt].val;
        tree[rs].val=tree[rt].val;
        tree[rt].val=-1;
    }
}
void updata(ll rt,ll a,ll b,ll c){
    ll l=tree[rt].l,r=tree[rt].r;
    if(l==a&&r==b){
        tree[rt].val=c;
        return ;
    }
    push_down(rt);
    if(b<=md){
        updata(ls,a,b,c);
    }else if(a>=md+1){
        updata(rs,a,b,c);
    }else{
        updata(ls,a,md,c);
        updata(rs,md+1,b,c);
    }
}
void query(ll rt,ll a,ll b){
    ll l=tree[rt].l,r=tree[rt].r;
    //de(tree[rt].val),de(l),de(r),de(a),de(b);
    if(l==a&&r==b&&tree[rt].val!=-1){
        ll tmp=tree[rt].val;
        if(!vis[tmp]){
            vis[tmp]=1;
            ans++;
        }
        return ;
    }
    if(tree[rt].val==-1&&l==r){
        return ;
    }
    push_down(rt);
    if(b<=md){
        query(ls,a,b);
    }else if(a>=md+1){
        query(rs,a,b);
    }else{
        query(ls,a,md);
        query(rs,md+1,b);
    }
}
void solve(){
    v.clear();
    ans=0;
    ll n=read();
    rep(i,1,n){
        input[i].l=read();
        input[i].r=read();
        v.pb(input[i].l);
        v.pb(input[i].r);
    }
    ll sz=v.size();
    sort(v.begin(),v.end());
    for(ll i=1;i<=sz-1;i++){
        if(v[i]-v[i-1]>1){
            v.pb(v[i-1]+1);
        }
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    sz=v.size();
    build(1,1,sz);
    rep(i,1,n){
        ll a=lower_bound(v.begin(),v.end(),input[i].l)-v.begin()+1;
        ll b=lower_bound(v.begin(),v.end(),input[i].r)-v.begin()+1;
        updata(1,a,b,i);
    }
    ms(vis,0);
    query(1,1,sz);
    cout<<ans<<endl;
}

E - Just a Hook HDU - 1698
kuangbin线段树专题(已更一半
kuangbin线段树专题(已更一半
就是个区间更新,区间查询的题目
题意:一个拐杖原本单位长度价值为1,然后每次选定一个LL,RR区间,把这个区间单位价值修改为valval 最后求区间之和。。
就是lazy的应用吧

struct node{
    int l,r;
    int val,tag;
}tree[maxn<<2];
void build(int rt,int l,int r){
    tree[rt].l=l;
    tree[rt].r=r;
    tree[rt].tag=0;
    if(l==r){
        tree[rt].val=1;
        return ;
    }
    build(lson);
    build(rson);
    tree[rt].val=tree[ls].val+tree[rs].val;
}
inline void push_down(int rt){
    int l=tree[rt].l,r=tree[rt].r;
    if(l==r||tree[rt].tag==0){
        tree[rt].tag=0;
        return ;
    }
    tree[ls].tag=tree[rs].tag=tree[rt].tag;
    tree[ls].val=(md-l+1)*tree[ls].tag;
    tree[rs].val=(r-md)*tree[rs].tag;
    tree[rt].tag=0;
}
void updata(int rt,int a,int b,int c){
    int l=tree[rt].l,r=tree[rt].r;
    if(l==a&&r==b){
        tree[rt].tag=c;
        tree[rt].val=(r-l+1)*c;
        return ;
    }
    push_down(rt);
    if(b<=md){
        updata(ls,a,b,c);
    }else if(a>=md+1){
        updata(rs,a,b,c);
    }else{
        updata(ls,a,md,c);
        updata(rs,md+1,b,c);
    }
    tree[rt].val=tree[ls].val+tree[rs].val;
}
int query(int rt,int a,int b){
    int l=tree[rt].l,r=tree[rt].r;
    if(l==a&&r==b){
        return tree[rt].val;
    }
    push_down(rt);
    if(b<=md){
        return query(ls,a,b);
    }else if(a>=md+1){
        return query(rs,a,b);
    }else{
        return query(ls,a,md)+query(rs,md+1,b);
    }
}
int cas=0;
void solve(){
    int n=read();build(1,1,n);
    int q=read();while(q--){
        int a=read(),b=read(),c=read();
        updata(1,a,b,c);
    }
    printf("Case %d: The total value of the hook is %d.\n",++cas,query(1,1,n));
}

F - Count the Colors ZOJ - 1610
kuangbin线段树专题(已更一半
kuangbin线段树专题(已更一半
也是线段树染色问题,每次把一个区域染成颜色ii,最后求出每种颜色有多少段,输出段数,为0(或者被覆盖完)则不用输出
因为这个染色的是线段,不是点,也即是说【1,2】 和【3,4】是不相邻的
这时候我们可以用LL来代替LLL+1L+1这个区间,更新数值的时候更新
L+1,R的点就可以了,最后暴力找出每个颜色的段数

struct segtree{
    int l,r;
    int val;
}tree[maxn<<2];
int vis[maxn],ans,cup[maxn];
void build(int rt,int l,int r){
    tree[rt].l=l;
    tree[rt].r=r;
    tree[rt].val=-1;
    if(l==r){
        return ;
    }
    build(lson);
    build(rson);
}
inline void push_down(int rt){
    int l=tree[rt].l,r=tree[rt].r;
    if(l==r||tree[rt].val==-1){
        return ;
    }
    tree[ls].val=tree[rs].val=tree[rt].val;
    tree[rt].val=-1;
}
void updata(int rt,int a,int b,int c){
    //de(l),de(r);
    //de(rt);
    int l=tree[rt].l,r=tree[rt].r;
    //de(a),de(b),de(l),de(r);
    if(l==a&&r==b){
        tree[rt].val=c;
        return ;
    }
    push_down(rt);
    if(b<=md){
        updata(ls,a,b,c);
    }else if(a>=md+1){
        updata(rs,a,b,c);
    }else{
        updata(ls,a,md,c);
        updata(rs,md+1,b,c);
    }
    
}
void query(int rt,int a,int b){
    int l=tree[rt].l,r=tree[rt].r;
    if(l==a&&r==b&&tree[rt].val!=-1){
        for(int i=l;i<=r;i++){
            cup[i]=tree[rt].val;
        }
        return ;
    }
    if(l==r&&tree[rt].val!=-1){
        return ;
    }
    push_down(rt);
    if(b<=md){
        query(ls,a,b);
    }else if(a>=md+1){
        query(rs,a,b);
    }else{
        query(ls,a,md);
        query(rs,md+1,b);
    }
    
}
void solve(){
    int n;while(~scanf("%d",&n)){
        int N=8001;
        build(1,1,N-1);
        ms(vis,0),ms(cup,-1);
        rep(i,1,n){
            int x1,x2,c;
            scanf("%d %d %d",&x1,&x2,&c);
            x1++;
            updata(1,x1,x2,c);
        }
        query(1,1,N-1);
        for(int i=1;i<=N;i++){
            if(cup[i-1]!=-1&&(i==1||cup[i-1]!=cup[i-2])){
                vis[cup[i-1]]++;
            }
        }
        for(int i=0;i<=N;i++){
            if(vis[i]){
                printf("%d %d\n",i,vis[i]);
            }
        }
        printf("\n");
    }
}

G - Balanced Lineup POJ - 3264
kuangbin线段树专题(已更一半
呃,区间最值查询,每次输出一个区间最大值与最小值的差值
简单题》。

struct segtree{
    int l,r;
    int mx,mn;
}tree[maxn<<2];
int ans1,ans2;
void build(int rt,int l,int r){
    tree[rt].l=l;
    tree[rt].r=r;
    if(l==r){
        int tmp=read();
        tree[rt].mx=tree[rt].mn=tmp;
        return ;
    }
    build(lson);
    build(rson);
    tree[rt].mx=max(tree[ls].mx,tree[rs].mx);
    tree[rt].mn=min(tree[ls].mn,tree[rs].mn);
}
void query(int rt,int a,int b){
    int l=tree[rt].l,r=tree[rt].r;
    if(l==a&&r==b){
        ans1=max(ans1,tree[rt].mx);
        ans2=min(ans2,tree[rt].mn);
        return ;
    }
    if(b<=md){
        query(ls,a,b);
    }else if(a>=md+1){
        query(rs,a,b);
    }else{
        query(ls,a,md);
        query(rs,md+1,b);
    }
}
void solve(){
    int n=read(),q=read();
    build(1,1,n);
    while(q--){
        int a=read(),b=read();
        ans1=-1*INF;
        ans2=INF;
        query(1,a,b);
        printf("%d\n",ans1-ans2);
    }
}

H - Can you answer these queries? HDU - 4027
kuangbin线段树专题(已更一半
区间更新,区间求和
由于这个区间更新是开方操作。。。所以必然不能用lazy标记了。。
但是暴力会超时?那怎么办
仔细想想,开方操作对于一个整数来说,最多操作6,7次就变成1了,变成1之后的开方就不会再变化了,所以我们还是暴力更新。只不过需要维护一下每个区间是否全为1了,是的话就不需要更新了,区间求和就是常规套路了

struct segtree{
    ll l,r;
    ll val,be;
}tree[maxn<<2];
void build(int rt,int l,int r){
    tree[rt].l=l;
    tree[rt].r=r;
    tree[rt].be=0;
    if(l==r){
        scanf("%lld",&tree[rt].val);
        if(tree[rt].val==1){
            tree[rt].be=1;
        }
        return ;
    }
    build(lson);
    build(rson);
    tree[rt].val=tree[ls].val+tree[rs].val;
    tree[rt].be= tree[rt].val==(r-l+1);
}
void updata(ll rt,ll a,ll b){
    ll l=tree[rt].l,r=tree[rt].r;
    if(l==a&&r==b&&tree[rt].be==1){
        return ;
    }
    if(l==a&&l==r){
        tree[rt].val=sqrt(tree[rt].val);
    }else if(b<=md){
        updata(ls,a,b);
    }else if(a>=md+1){
        updata(rs,a,b);
    }else{
        updata(ls,a,md);
        updata(rs,md+1,b);
    }
    if(l != r){
        tree[rt].val=tree[ls].val+tree[rs].val;
    }
    tree[rt].be = tree[rt].val==(r-l+1);
}
ll query(ll rt,ll a,ll b){
    ll l=tree[rt].l,r=tree[rt].r;
    if(l==a&&r==b){
        return tree[rt].val;
    } else {
        if (b <= md) {
            return query(ls,a,b);
        } else if (a >= md+1){
            return query(rs,a,b);
        } else {
            return query(ls,a,md) + query(rs,md+1,b);
        }
    }
}
void solve(){
    ll cas=0;
    ll n;while(~scanf("%lld",&n)){
        build(1,1,n);
        ll m;scanf("%lld",&m);
        printf("Case #%lld:\n",++cas);
        while(m--){
            ll a,b,c;scanf("%lld %lld %lld",&a,&b,&c);
            if(b>c){
                swap(b,c);
            }
            if (a==0) {
                updata(1,b,c);
            } else {
                printf("%lld\n",query(1,b,c));
            }
        }
        puts("");
    }
}

先鸽了…明后天再继续补