UVALive 3938 一道被我WA了的线段树

Posted by Cww97 on 2016-03-06

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/50816151
题目点着
题意是一段区间,q次询问一段区间最大连续字段和
看了眼白书,每段最大连续子段和为
左子树的最大子段,右子树的最大子段,或横跨左右的最大子段
这三个里面最大的
每个节点维护3个值,最大前缀子段(L开头),最大后缀子段(R结尾),最大子段

WAWAWAWAWAWAWA。。。。。。
代码能力捉急,先存着,等到海枯石烂那天在回头看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<cstdio>//cww=2016.3.6
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<int,int> pa;
const int N=1000100;
int QL,QR;
LL s[N];
LL sum(int L,int R){return s[R]-s[L-1];}
LL sum(pa x){return sum(x.first,x.second);}
pa better(pa a,pa b){
if (sum(a)!=sum(b))return sum(a)>sum(b)?a:b;
return a<b?a:b;
}

struct tree{
int pre[N],suf[N];pa sub[N];

void build(int t,int L,int R){
if (L==R){
pre[t]=suf[t]=L;
sub[t]=make_pair(L,L);
return ;
}
int lc=t<<1,rc=lc+1,mid=L+(R-L)/2;
build(lc,L,mid); //子树
build(rc,mid+1,R);
LL x=sum(L,pre[lc]);//pre
LLy=sum(L,pre[rc]);
if (x==y)pre[t]=min(pre[lc],pre[rc]);
else pre[t]=x>y?pre[lc]:pre[rc];
x=sum(suf[lc],R);//suf
y=sum(suf[rc],R);
if (x==y)suf[t]=min(suf[lc],suf[rc]);
else suf[t]=x>y?suf[lc]:suf[rc];
sub[t]=better(sub[lc],sub[rc]); //sub
sub[t]=better(sub[t],make_pair(suf[lc],pre[rc]));
}

pa querypre(int t,int L,int R){
if (pre[t]<=QR)return make_pair(L,pre[t]);
int mid=L+(R-L)/2,lc=t<<1,rc=lc+1;
if (QR<=mid)return querypre(lc,L,mid);
pa x=querypre(rc,mid+1,R);
x.first=L;
return better(x,make_pair(L,pre[lc]));
}

pa querysuf(int t,int L,int R){
if (QL<=suf[t])return make_pair(suf[t],R);
int mid=L+(R-L)/2,lc=t<<1,rc=lc+1;
if (mid<QL)return querysuf(rc,mid+1,R);
pa x=querysuf(lc,L,mid);
x.second=R;
return better(x,make_pair(suf[rc],R));
}

pa query(int t,int L,int R){
if (QL<=L&&R<=QR)return sub[t];
int mid=L+(R-L)/2,lc=t<<1,rc=lc+1;
if (QL<=mid)return query(lc,L,mid);
if (mid<QR)return query(rc,mid+1,R);
pa x=querypre(rc,mid+1,R);
pa y=querysuf(lc,L,mid);
pa z=better(query(lc,L,mid),query(rc,mid+1,R));
return better(z,make_pair(y.first,x.second));
}
}T;
int main(){
//freopen("fuck.in","r",stdin);
int cas=0,n,x,q;
while (scanf("%d%d",&n,&q)==2){
s[0]=0;
for (int i=1;i<=n;i++){
scanf("%d",&x);
s[i]=s[i-1]+x;
}
T.build(1,1,n);
printf("Case %d:\n", ++cas);
while (q--){
int L,R;scanf("%d%d",&L,&R);
QL=L;QR=R;
pa ans=T.query(1,1,n);
printf("%d %d\n",ans.first,ans.second);
}
}
return 0;
}