spoj 1557 线段树区间最大连续和（不重复数）

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<string.h>
 5 #define LL long long
 6 using std::sort;
 7 const int N = 100005;
 8 struct Order
 9 {
10     int l,r,id;
11     bool operator <(const Order & tmp)const
12     {
13         return r<tmp.r;
14     }
15 }order[N];
16 LL pmax[N<<2],padd[N<<2],add[N<<2],sum[N<<2],ans[N];
17 int pos[N<<1],num[N];
18 LL Max(LL a,LL b)
19 {
20    return a>b?a:b;
21 }
22 void PushUp(int t)
23 {
24      int t1=t<<1,t2=t1|1;
25      sum[t]=Max(sum[t1],sum[t2]);
26      pmax[t]=Max(pmax[t1],pmax[t2]);
27 }
28 void PushDown(int t)
29 {
30      if(add[t]||padd[t])
31      {
32        int t1=t<<1,t2=t1|1;
33        padd[t1]=Max(padd[t1],add[t1]+padd[t]);
34        pmax[t1]=Max(pmax[t1],sum[t1]+padd[t]);
35        add[t1]+=add[t],sum[t1]+=add[t];
36        padd[t2]=Max(padd[t2],add[t2]+padd[t]);
37        pmax[t2]=Max(pmax[t2],sum[t2]+padd[t]);
38        add[t2]+=add[t],sum[t2]+=add[t];
39        add[t]=padd[t]=0;
40      }
41 }
42 void update(int t,int l,int r,int L,int R,int val)
43 {
44      if(L<=l&&r<=R)
45      {
46          padd[t]=Max(padd[t],add[t]+=(LL)val);
47          pmax[t]=Max(pmax[t],sum[t]+=(LL)val);
48          return ;
49      }
50      PushDown(t);
51      int m=(l+r)>>1;
52      if(L<=m)update(t<<1,l,m,L,R,val);
53      if(R>m)update(t<<1|1,m+1,r,L,R,val);
54      PushUp(t);
55 }
56 LL query(int t,int l,int r,int L,int R)
57 {
58      if(L<=l&&r<=R)return pmax[t];
59      PushDown(t);
60      int m=(l+r)>>1;
61      LL aa=0;
62      if(L<=m)aa=Max(aa,query(t<<1,l,m,L,R));
63      if(R>m)aa=Max(aa,query(t<<1|1,m+1,r,L,R));
64      return aa;
65 }
66 void build(int t,int l,int r)
67 {
68      pos[t]=sum[t]=pmax[t]=padd[t]=0;
69      if(l==r)return ;
70      int m=(r+l)>>1;
71      build(t<<1,l,m);
72      build(t<<1|1,m+1,r);
73 }
74 int main()
75 {
76     int n,m;
77     while(~scanf("%d",&n))
78     {
79           for(int i=1;i<=n;i++){scanf("%d",&num[i]);pos[num[i]+N]=0;}
80           scanf("%d",&m);
81           for(int i=1;i<=m;i++){scanf("%d%d",&order[i].l,&order[i].r),order[i].id=i;}
82           sort(order+1,order+m+1);
83           build(1,1,n);
84           for(int i=1,j=1;i<=n;i++)
85           {
86               update(1,1,n,pos[num[i]+N]+1,i,num[i]);
87               pos[num[i]+N]=i;
88               while(i>=order[j].r)
89               {
90                   ans[order[j].id]=query(1,1,n,order[j].l,order[j].r);
91                   j++;
92                   if(j>m)break;
93               }
94               if(j>m)break;
95           }
96           for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
97     }
98     return 0;
99 }

看到这道题目的时候，被之前turing tree完全误导了。。看来以后做题目还是要仔细的分析题目啊。。。

这道题目的更新有点特殊，每个点记录的是从这个位置起到某个点所产生的最大连续和。

好比如：x1,x2,x3,x4

那么最大连续和就只可能是x1 x1+x2 x1+x2+x3 x1+x2+x3+x4

x2 x2+x3 x2+x3+x4

x3 x3+x4

那么我们怎么去维护这样子一个值呢，需要四个标记pmax(区间最大连续和) sum(区间总和) padd(历史最大累加和) add(累加总和)。

spoj 1557 线段树 区间最大连续和 （不重复数）

spoj 1557 线段树区间最大连续和（不重复数）