34. else if(p>mid) return ask(k<<1|1,p,q);
35. else{
36. g=ask(k<<1,p,mid);
37. h=ask(k<<1|1,mid+1,q);
38. a.mx=max(max(g.mx,h.mx),g.rm+h.lm);
39. a.rm=max(h.sum+g.rm,h.rm);
40. a.lm=max(g.lm,g.sum+h.lm);
41. return a;
42. }
43. }
44. void change(int k,int x,int y)
45. {
46. int l=tree[k].l,r=tree[k].r;
47. if(l==r){tree[k].sum=tree[k].lm=tree[k].rm=tree[k].mx=y;return;}
48. int mid=(l+r)>>1;
49. if(x<=mid)change(k<<1,x,y);
50. else if(x>mid)change(k<<1|1,x,y);
51. update(k);
52. }
53. int main()
54. {
55. freopen("input.in","r",stdin);
56. freopen("output.txt","w",stdout);
57. while(scanf("%d%d",&n,&m)==2){
58. for(int i=1;i<=n;i++)
59. scanf("%d",&a[i]);
60. build(1,1,n);
61. for(int i=1;i<=m;i++)
62. {
63. int t,x,y;
64. scanf("%d%d%d",&t,&x,&y);
65. if(t==1)
66. {
67. if(x>y)swap(x,y);
68. printf("%d\n",ask(1,x,y).mx);
69. }
70. if(t==2) change(1,x,y);
71. }
72. }
73.
74. return 0;
75. }
评论0