【hdu1754】I Hate It

2015.02.20 12:32 Fri | 9次阅读 | 旧日oi | 固定链接 | 源码

题目不好贴
就是单点修改区间查询最大值的线段树
写了个按区间修改的zkw线段树……
那个标记永久化还是没太搞懂,模拟一下的确是对的,好神啊……

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long 
using namespace std;
int n,m,l,r;ll w;
char s[2];
ll v[1<<19];
struct ZKW{
    ll tree[1<<19];
    int m;
    void build(int len)
    {
        m=1;
        while(m-1<=len) m<<=1;
        for(int i=1;i<=len;i++) tree[i+m]=v[i];
        for(int i=m-1;i;i--) tree[i]=max(tree[i<<1],tree[i<<1|1]);
        for(int i=m+len+1;i;i--) tree[i]=tree[i]-tree[i>>1];
    }
    void update(int l,int r,int val)
    {
        ll tmp;
        for(l+=m-1,r+=m+1;l^r^1;l>>=1,r>>=1)
        {
            if(~l&1) tree[l^1]+=val;
            if(r&1) tree[r^1]+=val;
            tmp=max(tree[l],tree[l^1]),tree[l]-=tmp,tree[l^1]-=tmp,tree[l>>1]+=tmp;
            tmp=max(tree[r],tree[r^1]),tree[r]-=tmp,tree[r^1]-=tmp,tree[r>>1]+=tmp;
        }
        for(;l>1;l>>=1)
        tmp=max(tree[l],tree[l^1]),tree[l]-=tmp,tree[l^1]-=tmp,tree[l>>1]+=tmp;
    }
    ll query(int l,int r)
    {
        ll lAns=0,rAns=0;
        if(l!=r) 
        {
            for(l+=m,r+=m;l^r^1;l>>=1,r>>=1) {
                lAns+=tree[l],rAns+=tree[r];
                if(~l&1) lAns=max(lAns,tree[l^1]);
                if(r&1) rAns=max(rAns,tree[r^1]);
            }
        }
        ll ans=max(lAns+tree[l], rAns+tree[r]);
        while(l>1) ans+=tree[l>>=1];
        return ans;
    }
    void del()
    {
        for(int i=1;i<=m+n;i++)
        tree[i]=0;
    }
}a; 
int main() 
{
    while(cin>>n>>m)
    {
        for(int i=1;i<=n;i++) scanf("%d",&v[i]);
        a.build(n);
        while(m--) {
            scanf("%s%d%d",s,&l,&r);
            if(s[0]=='U') a.update(l,l,r-v[l]),v[l]=r;
            else printf("%d\n",a.query(l,r));
        }
        a.del();
    }
    return 0;
}```