题解

45 条题解

  • 2
    @ 2020-10-20 20:40:51
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    namespace dts
    {
        struct st_node
        {
            int l,r,mid,sum,lazy;
            //sum:maxsum,lazy:maxsumlazy
        };
        
        int n,m,a[100000];
        st_node st[(1<<19)+2];
        #define lc(now) ((now)<<1)
        #define rc(now) ((now)<<1|1)
        
        void st_push_down(int now)
        {
            st[lc(now)].sum+=st[now].lazy;
            st[rc(now)].sum+=st[now].lazy;
            st[lc(now)].lazy+=st[now].lazy;
            st[rc(now)].lazy+=st[now].lazy;
            st[now].lazy=0;
        }
        
        void st_build(int now,int l,int r)
        {
            st[now].l=l,st[now].r=r;
            st[now].lazy=0;
            if (l<r)
            {
                st[now].mid=(l+r)>>1;
                st_build(lc(now),l,st[now].mid);
                st_build(rc(now),st[now].mid+1,r);
                st[now].sum=max(st[lc(now)].sum,st[rc(now)].sum);
            }
            else
                st[now].sum=a[st[now].l-1];
        }
        
        void st_update(int now,int l,int r,int val)
        {
            if (st[now].l==l&&r==st[now].r)
                st[now].sum+=val,st[now].lazy+=val;
            else
            {
                st_push_down(now);
                if (r<=st[now].mid)
                    st_update(lc(now),l,r,val);
                else if (st[now].mid+1<=l)
                    st_update(rc(now),l,r,val);
                else
                    st_update(lc(now),l,st[now].mid,val),st_update(rc(now),st[now].mid+1,r,val);
                st[now].sum=max(st[lc(now)].sum,st[rc(now)].sum);
            }
        }
        
        int st_ask(int now,int l,int r)
        {
            if (st[now].l==l&&r==st[now].r)
                return st[now].sum;
            else
            {
                st_push_down(now);
                if (r<=st[now].mid)
                    return st_ask(lc(now),l,r);
                else if (st[now].mid+1<=l)
                    return st_ask(rc(now),l,r);
                else
                    return max(st_ask(lc(now),l,st[now].mid),st_ask(rc(now),st[now].mid+1,r));
            }
        }
        
        void main()
        {
            scanf("%d",&n);
            for (int i=0;i<n;i++)
                scanf("%d",&a[i]);
            st_build(1,1,n);
            scanf("%d",&m);
            for (int i=1;i<=m;i++)
            {
                int K,l,r;
                scanf("%d%d%d",&K,&l,&r);
                if (K==1)
                {
                    int val;
                    scanf("%d",&val);
                    st_update(1,l,r,val);
                }
                else if (K==2)
                    printf("%d\n",st_ask(1,l,r));
            }
        }
    }
    
    int main()
    {
        dts::main();
    }
    
  • 2
    @ 2017-10-17 15:52:47

    线段树区间修改+区间查询
    ```cpp
    #include<cstdio>
    using namespace std;

    int n,m,x,y,z;
    struct data
    {
    int l,r,x,tag;
    } tr[300005];

    int readln()
    {
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while ('0'<=ch&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*f;
    }

    int max(int x,int y){return x>y?x:y;}

    void build(int l,int r,int rt)
    {
    tr[rt].l=l;tr[rt].r=r;
    if (l==r) {tr[rt].x=readln();return;}
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);
    tr[rt].x=max(tr[rt<<1].x,tr[rt<<1|1].x);
    }

    void pushdown(int rt)
    {
    tr[rt<<1].tag+=tr[rt].tag;
    tr[rt<<1|1].tag+=tr[rt].tag;
    tr[rt<<1].x+=tr[rt].tag;
    tr[rt<<1|1].x+=tr[rt].tag;
    tr[rt].tag=0;
    }

    void updata(int l,int r,int add,int rt)
    {
    int ll=tr[rt].l,rr=tr[rt].r;
    if (ll==l&&rr==r) {tr[rt].tag+=add;tr[rt].x+=add;return;}
    if (tr[rt].tag) pushdown(rt);
    int mid=(ll+rr)>>1;
    if (r<=mid) updata(l,r,add,rt<<1);
    else if (mid<l) updata(l,r,add,rt<<1|1);
    else {updata(l,mid,add,rt<<1);updata(mid+1,r,add,rt<<1|1);}
    tr[rt].x=max(tr[rt<<1].x,tr[rt<<1|1].x);
    }

    int query(int l,int r,int rt)
    {
    int ll=tr[rt].l,rr=tr[rt].r;
    if (ll==l&&rr==r) return tr[rt].x;
    if (tr[rt].tag) pushdown(rt);
    int mid=(ll+rr)>>1;
    if (r<=mid) return query(l,r,rt<<1);
    else if (mid<l) return query(l,r,rt<<1|1);
    else return max(query(l,mid,rt<<1),query(mid+1,r,rt<<1|1));
    }

    int main()
    {
    n=readln();
    build(1,n,1);
    m=readln();
    for (int i=1;i<=m;i++)
    {
    x=readln();
    if (x==1){
    x=readln();y=readln();z=readln();
    updata(x,y,z,1);
    }
    else {
    x=readln();y=readln();
    printf("%d\n",query(x,y,1));
    }
    }
    }
    ```

  • 1
    @ 2009-10-11 20:03:29

    Accepted 有效得分:100 有效耗时:373ms

    我只能说,我极度鄙视这道题,可恶的输出.......

    话说这个c居然真的有负数,害我wa得更惨......

  • 0
    @ 2022-04-14 11:37:53

    好基础的一道线段树啊……

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    struct tree
    {
        int l,r;
        long long maxn,lb;
    }a[10000005];
    int n,m;
    int s[1000005];
    void build(int d,int l,int r)
    {
        a[d].l=l;
        a[d].r=r;
        a[d].lb=0;
        if(l==r)
        {
            a[d].maxn=s[l];
            return;
        }
        int mid=(l+r)/2; 
        build(2*d,l,mid);
        build(2*d+1,mid+1,r);
        a[d].maxn=max(a[2*d].maxn,a[2*d+1].maxn);
        return;
    }
    inline void xf(int d)
    {
        if(a[d].lb!=0)
        {
            a[2*d].maxn+=a[d].lb;
            a[2*d+1].maxn+=a[d].lb;
            a[2*d].lb+=a[d].lb;
            a[2*d+1].lb+=a[d].lb;
            a[d].lb=0;
        }
    }
    void gai(int d,int x,int y,long long s)
    {
        if(a[d].l>=x&&a[d].r<=y)
        {
            a[d].maxn+=s;
            a[d].lb+=s;
            return;
        }
        xf(d);
        int mid=(a[d].l+a[d].r)/2;
        if(x<=mid)
        {
            gai(2*d,x,y,s);
        }
        if(y>mid)
        {
            gai(2*d+1,x,y,s);
        }   
        a[d].maxn=max(a[2*d].maxn,a[2*d+1].maxn);
        return;
    }
    long long ask(int d,int x,int y)
    {
        if(a[d].l>=x&&a[d].r<=y)
        {
            return a[d].maxn;
        }
        xf(d);
        int mid=(a[d].l+a[d].r)/2;
        long long ans=-1e18;
        if(x<=mid)
        {
            ans=max(ans,ask(2*d,x,y));
        }
        if(y>mid)
        {
            ans=max(ans,ask(2*d+1,x,y));
        }
        return ans;
    }
    int main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&s[i]);
        }
        build(1,1,n);
        scanf("%d",&m);
        int x,y,op;
        long long s;
        for(int i=1;i<=m;++i)
        {
            scanf("%d",&op);
            if(op==1)
            {
                scanf("%d%d%lld",&x,&y,&s);
                gai(1,x,y,s);
            }
            else
            {
                scanf("%d%d",&x,&y);
                printf("%lld\n",ask(1,x,y));
            }
        }
        return 0;
    }
    /*
    5 1 2 3 4 5 3
    2 1 4
    1 1 3 3
    2 3 5
    */
    
  • 0
    @ 2017-01-28 00:00:24

    #include <bits/stdc++.h>
    #include <ext/pb_ds/tree_policy.hpp>
    #include <ext/pb_ds/assoc_container.hpp>
    using namespace std;

    const int N = 100000 + 5;

    int n, m, a[N], addv[N << 2], maxv[N << 2];

    inline void maintain(int rt) { maxv[rt] = max(maxv[rt << 1], maxv[rt << 1 | 1]); }

    inline void pushdown(int rt) {
    addv[rt << 1] += addv[rt];
    addv[rt << 1 | 1] += addv[rt];
    maxv[rt << 1] += addv[rt];
    maxv[rt << 1 | 1] += addv[rt];
    addv[rt] = 0;
    }

    void build(int L, int R, int rt) {
    if (L == R) {
    maxv[rt] = a[L];
    return;
    }
    int mid = (L + R) >> 1;
    build(L, mid, rt << 1);
    build(mid + 1, R, rt << 1 | 1);
    maintain(rt);
    }

    void update(int l, int r, int v, int L, int R, int rt) {
    if (l <= L && r >= R) {
    addv[rt] += v;
    maxv[rt] += v;
    return;
    }
    pushdown(rt);
    int mid = (L + R) >> 1;
    if (l <= mid) update(l, r, v, L, mid, rt << 1);
    if (r > mid) update(l, r, v, mid + 1, R, rt << 1 | 1);
    maintain(rt);
    }

    int query(int l, int r, int L, int R, int rt) {
    if (l <= L && r >= R) return maxv[rt];
    pushdown(rt);
    int mid = (L + R) >> 1;
    if (r <= mid) return query(l, r, L, mid, rt << 1);
    else if (l > mid) return query(l, r, mid + 1, R, rt << 1 | 1);
    else return max(query(l, r, L, mid, rt << 1), query(l, r, mid + 1, R, rt << 1 | 1));
    maintain(rt);
    }

    int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    build(1, n, 1);
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
    int k, l, r, c; scanf("%d", &k);
    if (k == 1) {
    scanf("%d%d%d", &l, &r, &c);
    update(l, r, c, 1, n, 1);
    } else {
    scanf("%d%d", &l, &r);
    printf("%d\n", query(l, r, 1, n, 1));
    }
    }
    return 0;
    }

  • 0
    @ 2016-11-17 20:44:52

    在更新的时候一边pushup 一边pushdown

    #include<cstdio>
    #include<iostream>
    #define L(u) (u<<1)
    #define R(u) (u<<1|1)
    using namespace std;
    const int N=100005;
    struct xx{
    int l,r,val,Max;
    }T[N<<2];
    int n,t,a[N];
    int op,L,R,C;
    void Pushup(int u){T[u].Max=max(T[L(u)].Max,T[R(u)].Max);}
    inline void Pushdown(int u)
    {
    if(!T[u].val)return;
    T[L(u)].val+=T[u].val;
    T[R(u)].val+=T[u].val;
    T[L(u)].Max+=T[u].val;
    T[R(u)].Max+=T[u].val;
    T[u].val=0;
    }
    void Build(int u,int l,int r)
    {
    T[u].l=l,T[u].r=r;
    if(l==r)
    {
    T[u].Max=a[l];
    return ;
    }
    int mid=(l+r)>>1;
    Build(L(u),l,mid),Build(R(u),mid+1,r);
    Pushup(u);
    }
    inline void Update(int u,int l,int r,int c)
    {
    if(T[u].l==l&&T[u].r==r)
    {
    T[u].val+=c;
    T[u].Max+=c;
    return;
    }
    Pushdown(u);
    int mid=(T[u].l+T[u].r)>>1;
    if(l>mid)

    Update(R(u),l,r,c);
    else if(r<=mid)
    Update(L(u),l,r,c);
    else
    Update(L(u),l,mid,c),Update(R(u),mid+1,r,c);
    Pushup(u);
    }
    inline int Query(int u,int l,int r)
    {
    if(T[u].l==l&&T[u].r==r)
    return T[u].Max;
    Pushdown(u);
    int mid=(T[u].l+T[u].r)>>1;
    if(l>mid)
    return Query(R(u),l,r);
    else if(r<=mid)
    return Query(L(u),l,r);
    else
    return max(Query(L(u),l,mid),Query(R(u),mid+1,r));
    Pushup(u);
    }
    int main()
    {
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    Build(1,1,n);
    cin>>t;
    while(t--)
    {
    scanf("%d",&op);
    if(op==1)
    {
    scanf("%d%d%d",&L,&R,&C);
    Update(1,L,R,C);
    }
    else{
    scanf("%d%d",&L,&R);
    printf("%d\n",Query(1,L,R));
    }
    }
    return 0;
    }

  • 0
    @ 2016-11-17 20:44:01

    #include<cstdio>
    #include<iostream>
    #define L(u) (u<<1)
    #define R(u) (u<<1|1)
    using namespace std;
    const int N=100005;int n,t,a[N],op,L,R,C;struct xx{int l,r,val,Max;}T[N<<2];
    inline void Pushdown(int u){if(!T[u].val)return;T[L(u)].val+=T[u].val,T[R(u)].val+=T[u].val,T[L(u)].Max+=T[u].val,T[R(u)].Max+=T[u].val;T[u].val=0;}
    void Build(int u,int l,int r){T[u].l=l,T[u].r=r;if(l==r){T[u].Max=a[l];return;}int mid=(l+r)>>1;Build(L(u),l,mid),Build(R(u),mid+1,r);T[u].Max=max(T[L(u)].Max,T[R(u)].Max);}
    inline void Update(int u,int l,int r,int c){if(T[u].l==l&&T[u].r==r){T[u].val+=c,T[u].Max+=c;return;}Pushdown(u); int mid=(T[u].l+T[u].r)>>1;if(l>mid)Update(R(u),l,r,c);else if(r<=mid)Update(L(u),l,r,c);else Update(L(u),l,mid,c),Update(R(u),mid+1,r,c);T[u].Max=max(T[L(u)].Max,T[R(u)].Max);}
    inline int Query(int u,int l,int r){if(T[u].l==l&&T[u].r==r)return T[u].Max;Pushdown(u);int mid=(T[u].l+T[u].r)>>1;if(l>mid)return Query(R(u),l,r);else if(r<=mid)return Query(L(u),l,r);else return max(Query(L(u),l,mid),Query(R(u),mid+1,r));T[u].Max=max(T[L(u)].Max,T[R(u)].Max);}
    int main(){cin>>n;for(int i=1;i<=n;i++)scanf("%d",a+i);Build(1,1,n);cin>>t;while(t--){scanf("%d",&op);if(op==1)scanf("%d%d%d",&L,&R,&C),Update(1,L,R,C);else scanf("%d%d",&L,&R),printf("%d\n",Query(1,L,R));}return 0;}

  • 0
    @ 2016-10-17 12:50:36

    线段树区间更新+区间最大值。。线段树很不熟。。最坑的是写读入优化的时候偷懒直接没有负数的判断,我以为所有的数都是正的5555555555555555(~~o(>_<)o ~~) 然后就A了。。

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #define L(u) (u<<1)
    #define R(u) (u<<1|1)
    #define ll long long
    using namespace std;
    const int M=1000005;
    struct Node{
    int maxn,val,add;
    int l,r;
    }node[M<<2];
    int A[M],m,n,k,p,l,flag,a,b,c;
    inline ll read()
    {
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
    if(ch=='-')f=-1;
    ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
    x=x*10+ch-'0';
    ch=getchar();
    }
    return x*f;
    }
    void Pushup(int u){
    node[u].maxn=max(node[L(u)].maxn,node[R(u)].maxn);
    }
    void Pushdown(int u){
    node[L(u)].add+=node[u].add;
    node[R(u)].add+=node[u].add;
    node[L(u)].maxn+=node[u].add;
    node[R(u)].maxn+=node[u].add;
    node[u].add=0;
    }
    void Build(int u,int left,int right){
    node[u].l=left;node[u].r=right;
    if(node[u].l==node[u].r){
    node[u].maxn=A[left];
    return;
    }
    int mid=(left+right)>>1;
    Build(L(u),left,mid);Build(R(u),mid+1,right);
    Pushup(u);
    }
    void Update(int u,int left,int right,int v){
    if(node[u].l==left&&node[u].r==right){
    node[u].add+=v;
    node[u].maxn+=v;
    return;
    }
    if(node[u].add) Pushdown(u);
    int mid=(node[u].l+node[u].r)>>1;
    if(right<=mid) Update(L(u),left,right,v);
    else if(left>=mid+1) Update(R(u),left,right,v);
    else {Update(L(u),left,mid,v);Update(R(u),mid+1,right,v);}
    Pushup(u);
    }
    int Query(int u,int left,int right){
    if(node[u].l==left&&node[u].r==right){
    return node[u].maxn;
    }
    if(node[u].add) Pushdown(u);
    int mid=(node[u].l+node[u].r)>>1;
    if(right<=mid) return Query(L(u),left,right);
    else if(left>=mid+1) return Query(R(u),left,right);
    else return max(Query(L(u),left,mid),Query(R(u),mid+1,right));
    Pushup(u);
    }
    int main()
    {
    n=read();
    for (int i=1;i<=n;i++)
    A[i]=read();
    Build(1,1,n);
    m=read();
    for (int i=1;i<=m;i++){
    k=read();
    if(k==2){a=read(),b=read();printf("%d\n",Query(1,a,b));}
    if(k==1) {a=read(),b=read();c=read();Update(1,a,b,c);}
    }
    return 0;
    }

  • 0
    @ 2015-07-31 12:38:33

    P1659河蟹王国
    Accepted记录信息
    评测状态 Accepted
    题目 P1659 河蟹王国
    递交时间 2015-07-31 12:32:48
    代码语言 C++
    评测机 VijosEx
    消耗时间 2790 ms
    消耗内存 10128 KiB
    评测时间 2015-07-31 12:32:53

    评测结果
    编译成功

    测试数据 #0: Accepted, time = 187 ms, mem = 3124 KiB, score = 10

    测试数据 #1: Accepted, time = 328 ms, mem = 7088 KiB, score = 10

    测试数据 #2: Accepted, time = 312 ms, mem = 10128 KiB, score = 10

    测试数据 #3: Accepted, time = 165 ms, mem = 5688 KiB, score = 10

    测试数据 #4: Accepted, time = 375 ms, mem = 8756 KiB, score = 10

    测试数据 #5: Accepted, time = 250 ms, mem = 4544 KiB, score = 10

    测试数据 #6: Accepted, time = 306 ms, mem = 6064 KiB, score = 10

    测试数据 #7: Accepted, time = 281 ms, mem = 5832 KiB, score = 10

    测试数据 #8: Accepted, time = 211 ms, mem = 2396 KiB, score = 10

    测试数据 #9: Accepted, time = 375 ms, mem = 6280 KiB, score = 10

    Accepted, time = 2790 ms, mem = 10128 KiB, score = 100

    代码
    #include <iostream>
    #include <stdio.h>

    using namespace std;

    struct Node
    {
    int l , r;
    Node * left , * right;
    int value;
    int tag;
    bool have;
    };

    int max( int a , int b )
    {
    if( a > b )
    return a;
    return b;
    }

    int merge( int a , int b )
    {
    return max( a , b );
    }

    inline void pushdown( Node * cur )
    {
    if( cur -> l == cur -> r )
    if( cur -> have )
    {
    cur -> have = 0;
    cur -> value += cur -> tag;
    cur -> tag = 0;
    return;
    }
    if( cur -> have )
    {
    cur -> have = 0;
    cur -> left -> tag += cur -> tag;
    cur -> right -> tag += cur -> tag;
    cur -> left -> have = 1;
    cur -> right -> have = 1;
    cur -> tag = 0;
    cur -> value = merge( cur -> left -> value + cur -> left -> tag , cur -> right -> value + cur -> right -> tag );
    }
    return;
    }

    inline void update( Node * cur )
    {
    cur -> value = merge( cur -> left -> value + cur -> left -> tag , cur -> right -> value + cur -> right -> tag );
    return;
    }

    int find( int l , int r , Node * cur )
    {
    //cout << l << " " << r << " " << cur -> l << " " << cur -> r << endl;
    pushdown( cur );
    if( cur -> l == l && cur -> r == r )
    return cur -> value;
    int mid = ( cur -> l + cur -> r ) / 2;
    if( l > mid )
    return find( l , r , cur -> right );
    else if( mid >= r )
    return find( l , r , cur -> left );
    return merge( find( l , mid , cur -> left ) , find( mid + 1 , r , cur -> right ) );
    }

    void modify( int l , int r , int v , Node * cur )
    {
    if( cur -> l == l && cur -> r == r )
    {
    cur -> have = 1;
    cur -> tag += v;
    return;
    }
    int mid = ( cur -> l + cur -> r ) / 2;
    if( l > mid )
    modify( l , r , v , cur -> right );
    else if( mid >= r )
    modify( l , r , v , cur -> left );
    else
    {
    modify( l , mid , v , cur -> left );
    modify( mid + 1 , r , v , cur -> right );
    }
    update( cur );
    }

    int a[100000 + 2];

    Node * build( int l , int r )
    {
    Node * cur = new Node();
    cur -> l = l;
    cur -> r = r;
    cur -> tag = 0;
    cur -> have = 0;
    if( l == r )
    {
    cur -> value = a[l];
    return cur;
    }
    int mid = ( l + r ) / 2;
    cur -> left = build( l , mid );
    cur -> right = build( mid + 1 , r );
    cur -> value = merge( cur -> left -> value , cur -> right -> value );
    return cur;
    }

    Node * root;
    int n , m;
    int s;
    int l , r , v;
    int i;

    int main()
    {
    scanf( "%d" , &n );
    for( i = 1 ; i <= n ; i++ )
    scanf( "%d", &a[i] );
    root = build( 1 , n );
    scanf( "%d" , &m );
    for( i = 0 ; i < m ; i++ )
    {
    scanf( "%d" , &s );
    if( s == 2 )
    {
    scanf( "%d %d" , &l , &r );
    printf( "%d\n" , find( l , r , root ) );
    }
    else
    {
    scanf( "%d %d %d" , &l , &r , &v );
    modify( l , r , v , root );
    }
    }
    return 0;
    }

  • 0
    @ 2013-11-26 14:28:32

    虽然我还有负的这句话看了很多遍,但我自己写的时候初始化还是初始了0- -

  • 0
    @ 2013-08-02 11:40:29

    交了10遍终于明白了
    update前要pushdown

  • 0
    @ 2013-05-11 21:12:07

    貌似说,输出完全没问题啊!!!!WA了N次后,改成正常输出格式就对了!????

    编译成功

    测试数据 #0: Accepted, time = 125 ms, mem = 6856 KiB, score = 10
    测试数据 #1: Accepted, time = 125 ms, mem = 6856 KiB, score = 10
    测试数据 #2: Accepted, time = 78 ms, mem = 6856 KiB, score = 10
    测试数据 #3: Accepted, time = 31 ms, mem = 6856 KiB, score = 10
    测试数据 #4: Accepted, time = 171 ms, mem = 6856 KiB, score = 10
    测试数据 #5: Accepted, time = 140 ms, mem = 6856 KiB, score = 10
    测试数据 #6: Accepted, time = 171 ms, mem = 6856 KiB, score = 10
    测试数据 #7: Accepted, time = 140 ms, mem = 6856 KiB, score = 10
    测试数据 #8: Accepted, time = 140 ms, mem = 6856 KiB, score = 10
    测试数据 #9: Accepted, time = 187 ms, mem = 6856 KiB, score = 10
    Accepted, time = 1308 ms, mem = 6856 KiB, score = 100

    #include <cstdio>
    #include <algorithm>

    using namespace std;

    #define MAXN 100001

    int a[MAXN];
    int n;

    struct saver{
    int l,r;
    int maxn;
    int c;
    } tree[MAXN*4];

    void make_tree(int l,int r,int k){
    tree[k].l=l;
    tree[k].r=r;
    tree[k].c=0;
    if (l==r){
    tree[k].maxn=a[l];
    return ;
    }
    int mid=(l+r)>>1;
    make_tree(l,mid,k<<1);
    make_tree(mid+1,r,k<<1^1);
    tree[k].maxn=max(tree[k<<1].maxn,tree[k<<1^1].maxn);
    }

    void Increase(int l,int r,int c,int k){
    if (tree[k].l==l&&tree[k].r==r){
    tree[k].c+=c;
    return ;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    if (r<=mid){ Increase(l,r,c,k<<1);} else
    if (l>mid){ Increase(l,r,c,k<<1^1);} else
    {
    Increase(l,mid,c,k<<1);
    Increase(mid+1,r,c,k<<1^1);
    }
    tree[k].maxn=max(tree[k<<1].maxn+tree[k<<1].c,tree[k<<1^1].maxn+tree[k<<1^1].c);
    }

    int Search(int l,int r,int k){
    if (l==tree[k].l&&r==tree[k].r){
    return tree[k].c+tree[k].maxn;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    if (r<=mid) return Search(l,r,k<<1)+tree[k].c;
    if (l>mid) return Search(l,r,k<<1^1)+tree[k].c;
    return max(Search(l,mid,k<<1),Search(mid+1,r,k<<1^1))+tree[k].c;
    }

    int main(){
    scanf("%d",&n);
    for (int i=0;i++<n;) scanf("%d",&a[i]);
    make_tree(1,n,1);
    int m;
    scanf("%d",&m);
    while (m--){
    int k;
    scanf("%d",&k);
    if (k==1){
    int l,r,c;
    scanf("%d%d%d",&l,&r,&c);
    Increase(l,r,c,1);
    }
    else {
    int l,r;
    scanf("%d%d",&l,&r);
    printf("%d\n",Search(l,r,1));
    }
    }
    return 0;
    }

  • 0
    @ 2009-10-22 21:12:28

    话说 一开始是当做直白的线段树

    后来同学说直接做等于浪费AC率

    然后我就想到再定义一个add数组来记录和谐值的增加量c

    没想到思路是对的

    可是!!!!

    因为好久没做题

    中间过程中的i没有var定义

    导致跟主程序里面的i冲突

    结果我这个“倔强”的人愣是交了10+便都没有通过

    我滴神啊

    原来真正难倒我的不是线段树 是寂寞!!!!

  • 0
    @ 2009-10-18 20:45:55

    我错了,忘记写write~

    用writeln卡了一次Conan~

  • 0
    @ 2009-10-14 19:30:14

    程序写得比较麻烦,

    一开始总超时,

    但用cena都在半秒内over了,

    后来才知道是输出的问题。

  • 0
    @ 2009-10-12 19:06:49

    泪目……

    自己的题,竟然没有一次AC……

    主要原因voyagec2神牛也说了,Vijos不适合加交互式的题目……

    BS我自己!

  • 0
    @ 2009-10-14 16:06:29

    好河蟹的提交次数和通过人数-_-|||

    Flag Accepted

    题号 P1659

    类型(?) 高级数据结构

    通过 44人

    提交 444次

    通过率 10%

    难度 2

    终于在下课铃响的时候过了……

    编译通过...

    ├ 测试数据 01:答案正确... 9ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 25ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 25ms

    ├ 测试数据 08:答案正确... 25ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:84ms

    关于输入问题

    都用read就ok了。

    关于输出问题

    我是每次write(find(l,r),' ');

    在程序最后writeln;

    ps:c是不是负数有关系吗?

  • 0
    @ 2009-10-08 12:44:50

    第39个AC!!!!!!!!!

    线段树的烦题

    终于入门了!

    ps:输出不能换行啊!

  • 0
    @ 2009-10-07 08:15:51

    只能用wirte才能AC啊,真是晕死啊~

信息

ID
1659
难度
7
分类
数据结构 | 线段树 点击显示
标签
(无)
递交数
2094
已通过
323
通过率
15%
被复制
10
上传者