【线段树】bzoj3747 [POI2015]Kinoman

题解：http://www.cnblogs.com/zyfzyf/p/4105184.html

一、下传标记写法

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 #define lson rt<<1,l,m

 #define rson rt<<1|1,m+1,r

 int Num,CH[],f,c;

 inline void R(int &x){

     c=;f=;

     for(;c<''||c>'';c=getchar())if(c=='-')f=-;

     for(x=;c>=''&&c<='';c=getchar())(x*=)+=(c-'');

     x*=f;

 }

 typedef long long ll;

 int n,m,w[],now[],b[],fa[];

 ll ans,maxv[],delta[];

 void pushdown(int rt)

 {

     if(delta[rt])

       {

         delta[rt<<]+=delta[rt]; delta[rt<<|]+=delta[rt];

         maxv[rt<<]+=delta[rt]; maxv[rt<<|]+=delta[rt];

         delta[rt]=;

       }

 }

 void update(int ql,int qr,int v,int rt,int l,int r)

 {

     if(ql<=l&&r<=qr)

       {

         delta[rt]+=(ll)v;

         maxv[rt]+=(ll)v;

         return;

       }

     pushdown(rt); int m=l+r>>;

     if(ql<=m) update(ql,qr,v,lson);

     if(m<qr) update(ql,qr,v,rson);

     maxv[rt]=max(maxv[rt<<],maxv[rt<<|]);

 }

 ll query(int qr,int rt,int l,int r)

 {

     if(<=l&&r<=qr) return maxv[rt];

     pushdown(rt);

     int m=l+r>>; ll res=;

     if(<=m) res=max(res,query(qr,lson));

     if(m<qr) res=max(res,query(qr,rson));

     return res;

 }

 int main()

 {

     R(n); R(m);

     for(int i=;i<=n;++i) R(b[i]);

     for(int i=;i<=m;++i) R(w[i]);

     for(int i=;i<=n;++i)

       {

         fa[i]=now[b[i]];

         now[b[i]]=i;

       }

     for(int i=;i<=n;++i)

       {

         update(fa[i]+,i,(ll)w[b[i]],,,n);

         if(fa[i]) update(fa[fa[i]]+,fa[i],(ll)(-w[b[i]]),,,n);

         ans=max(ans,query(i,,,n));

       } printf("%lld\n",ans);

     return ;

 }

二、不下传标记写法

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 #define lson rt<<1,l,m

 #define rson rt<<1|1,m+1,r

 int Num,CH[],f,c;

 inline void R(int &x){

     c=;f=;

     for(;c<''||c>'';c=getchar())if(c=='-')f=-;

     for(x=;c>=''&&c<='';c=getchar())(x*=)+=(c-'');

     x*=f;

 }

 typedef long long ll;

 int n,m,w[],now[],b[],fa[];

 ll ans,maxv[],delta[];

 void update(int ql,int qr,int v,int rt,int l,int r)

 {

     if(ql<=l&&r<=qr)

       {

         delta[rt]+=(ll)v;

         return;

       }

     int m=l+r>>;

     if(ql<=m) update(ql,qr,v,lson);

     if(m<qr) update(ql,qr,v,rson);

     maxv[rt]=max(maxv[rt<<]+delta[rt<<],maxv[rt<<|]+delta[rt<<|]);

 }

 ll query(int qr,int rt,int l,int r)

 {

     if(<=l&&r<=qr) return maxv[rt]+delta[rt];

     int m=l+r>>; ll res=;

     if(<=m) res=max(res,query(qr,lson));

     if(m<qr) res=max(res,query(qr,rson));

     return res;

 }

 int main()

 {

     R(n); R(m);

     for(int i=;i<=n;++i) R(b[i]);

     for(int i=;i<=m;++i) R(w[i]);

     for(int i=;i<=n;++i)

       {

           fa[i]=now[b[i]];

           now[b[i]]=i;

       }

     for(int i=;i<=n;++i)

       {

           update(fa[i]+,i,(ll)w[b[i]],,,n);

           if(fa[i]) update(fa[fa[i]]+,fa[i],(ll)(-w[b[i]]),,,n);

           ans=max(ans,query(i,,,n));

       } printf("%lld\n",ans);

     return ;

 }