|
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114 |
#include<iostream>#include<stdio.h>using
namespace
std;int
sum;int
ans;struct
Tree{ int
a,b; int
sum; int
ans; Tree *lchile,*rchile;};int
swap(int
x,int
y){ if(x>y) return
x; else return
y;} Tree *build(int
l,int
r){ Tree *root=new
Tree; root->a=l; root->b=r; root->sum=0; root->ans=-1; root->lchile=NULL; root->rchile=NULL; if(l<r) { int
mid=(l+r)>>1; root->lchile=build(l,mid); root->rchile=build(mid+1,r); } return
root;}void
insert(Tree *root,int
l,int
k){ if((root->a==l)&&(root->b==l)) { root->ans=k; root->sum=k; return
; } int
mid=(root->a+root->b)>>1; if(mid>=l) { insert(root->lchile,l,k); } else { insert(root->rchile,l,k); } root->sum=root->lchile->sum+root->rchile->sum; root->ans=swap(root->lchile->ans,root->rchile->ans);}void
search(Tree *root,int
l,int
r){ if(root->a>=l&&root->b<=r) { if(root->ans>ans) ans=root->ans; sum+=root->sum; return
; } int
mid=(root->a+root->b)>>1; if(mid>=r) { search(root->lchile,l,r); } else
if(mid<l) { search(root->rchile,l,r); } else { search(root->lchile,l,mid); search(root->rchile,mid+1,r); }}int
main(){ Tree *root=new
Tree; int
n,m,i,s,c,b,t; cin>>n>>m; root=build(1,n); for(i=1;i<=n;i++) { cin>>t; insert(root,i,t); } for(i=1;i<=m;i++) { int
ch; cin>>ch; if(ch==1) { cin>>s>>b; insert(root,s,b); } else { sum=0; ans=-1; cin>>s>>b; search(root,s,b); if(ch==2) cout<<sum<<endl; if(ch==3) cout<<ans<<endl; } } return
0;} |
原文：http://www.cnblogs.com/MonkeyAC/p/3534934.html