【题解】HDOJ P1698【Just a Hook】

背景

居然在这题上得到了人生中第一个PE(Persentation Error),少了换行233。

分析

区间修改,整段查询,套线段树就好了

代码

#include<cstdio>

typedef long long int64;
const int MAXN = 100000 + 6;
int A[MAXN];

class SegmentTree{
    public:int l,r;
    public:int sum,add;
};SegmentTree t[MAXN * 4];
inline int L(int x){return x << 1;}
inline int R(int x){return x << 1 | 1;}
inline void maintain(int p){t[p].sum = t[L(p)].sum + t[R(p)].sum;}

void build(int p,int l,int r){
    t[p].l = l;t[p].r = r;t[p].add = 0;
    if(l == r){t[p].sum = A[l];return;}
    int mid = (l + r) >> 1;
    build(L(p),l,mid);
    build(R(p),mid + 1,r);
    maintain(p);
}
void spread(int p){
    if(t[p].add){
        t[L(p)].sum = (t[p].add * (t[L(p)].r - t[L(p)].l + 1));
        t[R(p)].sum = (t[p].add * (t[R(p)].r - t[R(p)].l + 1));
        t[L(p)].add = t[R(p)].add = t[p].add;
        t[p].add = 0;
    }
}
void change(int p,int l,int r,int d){
    if(l <= t[p].l && r >= t[p].r){
        t[p].sum = ((int64)d * (t[p].r - t[p].l + 1));
        t[p].add = d;
        return;
    }
    spread(p);int mid = (t[p].l + t[p].r) >> 1;
    if(l <= mid) change(L(p),l,r,d);
    if(r > mid) change(R(p),l,r,d);
    maintain(p);
}
int ask(int p,int l,int r){
    if(l <= t[p].l && r >= t[p].r) return t[p].sum;
    spread(p);int ans = 0,mid = (t[p].l + t[p].r) >> 1;
    if(l <= mid) ans += ask(L(p),l,r);
    if(r > mid) ans += ask(R(p),l,r);
    return ans;
}

int main(){
    int T;scanf("%d",&T);
    for(int GG = 1;GG <= T;GG++){
        int n;scanf("%d",&n);
        for(int i = 1;i <= n;i++) A[i] = 1;
        build(1,1,n);
        int m,x,y,z;scanf("%d",&m);
        while(m--)scanf("%d %d %d",&x,&y,&z),change(1,x,y,z);
        printf("Case %d: The total value of the hook is %d.\n",GG,ask(1,1,n));
    }

    return 0;
}

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注