首页 > 代码库 > 线段树

线段树

2024-07-05 16:04:22   233人阅读

感觉线段树一直学的不好，从开始学到现在换了很多风格，模板其实不是问题，关键是还是思路吧。

从水题，开始再来一遍。

HDU 1166 敌兵步阵

#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define MOD 1000000009
#define N 50000
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int p[4*N];
void pushup(int rt)
{
    p[rt] = p[rt<<1] + p[rt<<1|1];
}
void build(int l,int r,int rt)
{
    int m;
    if(l == r)
    {
        scanf("%d",&p[rt]);
        return ;
    }
    m = (l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt);
}
void update(int x,int sc,int l,int r,int rt)
{
    int m;
    if(l == r)
    {
        p[rt] += sc;
        return ;
    }
    m = (l+r)>>1;
    if(x <= m)
    update(x,sc,lson);
    else
    update(x,sc,rson);
    pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
    int m,sum = 0;
    if(l >= L&&r <= R)
    {
        return p[rt];
    }
    m = (l+r)>>1;
    if(L <= m)
    sum += query(L,R,lson);
    if(R > m)
    sum += query(L,R,rson);
    return sum;
}
int main()
{
    int t,cas = 1,a,b,n;
    char str[101];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        build(1,n,1);
        printf("Case %d:\n",cas++);
        for(;;)
        {
            scanf("%s",str);
            if(str[0] == ‘E‘) break;
            if(str[0] == ‘Q‘)
            {
                scanf("%d%d",&a,&b);
                printf("%d\n",query(a,b,1,n,1));
            }
            else if(str[0] == ‘A‘)
            {
                scanf("%d%d",&a,&b);
                update(a,b,1,n,1);
            }
            else
            {
                scanf("%d%d",&a,&b);
                update(a,-b,1,n,1);
            }
        }
    }
    return 0;
}
View Code

HDU 1698 Just a Hook

#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define N 100001
int p[4*N];
int lz[4*N];
void pushup(int rt)
{
    p[rt] = p[rt<<1] + p[rt<<1|1];
}
void pushdown(int rt,int m)
{
    if(lz[rt])
    {
        lz[rt<<1] = lz[rt];
        lz[rt<<1|1] = lz[rt];
        p[rt<<1] = lz[rt]*(m-(m>>1));
        p[rt<<1|1] = lz[rt]*(m>>1);
        lz[rt] = 0;
    }
}
void build(int l,int r,int rt)
{
    int m;
    lz[rt] = 0;
    if(l == r)
    {
        p[rt] = 1;
        return ;
    }
    m = (l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt);
}
void update(int L,int R,int sc,int l,int r,int rt)
{
    if(L <= l&&R >= r)
    {
        lz[rt] = sc;
        p[rt] = (r-l+1)*sc;
        return ;
    }
    int m = (l+r)>>1;
    pushdown(rt,r-l+1);
    if(L <= m)
    update(L,R,sc,lson);
    if(R > m)
    update(L,R,sc,rson);
    pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
    int m,sum = 0;
    if(L <= l&&R >= r)
    {
        return p[rt];
    }
    m = (l+r)>>1;
    pushdown(rt,r-l+1);
    if(L <= m)
    sum += query(L,R,lson);
    if(R > m)
    sum += query(L,R,rson);
    return sum;
}
int main()
{
    int t,cas = 1,i,n,m,x,y,z;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        build(1,n,1);
        scanf("%d",&m);
        for(i = 1;i <= m;i ++)
        {
            scanf("%d%d%d",&x,&y,&z);
            update(x,y,z,1,n,1);
        }
        printf("Case %d: The total value of the hook is %d.\n",cas++,query(1,n,1,n,1));
    }
    return 0;
}
View Code

 

 


联系
我们