Chef and Churu codechef solution for interlinked Segment tree

Chef and Churu

1. #include<stdio.h>
2. #include<algorithm>
3. #include<vector>
4. using namespace std;
5. typedef long long int lli;
6. typedef long int li;
7. li to=0;
8. #define F first
9. #define S second
10. lli arr[100005];
11. lli sum[100005],ran[100005];
13. vector <pair<pair<int,int> ,int> > pa(100005),tre(300005);
14. vector <pair<pair<int,int> ,int> > :: iterator it,it2;
15. //build(1,t,0,t-1);
16. int build(int index, int n, int s,int e )
17. {
18. if(s==e)
19. {
20. tre[index]=pa[s];
21. return 0;
22. }
23. int m=(s+e)/2;
24. build(index*2,n,s,m);
25. build(index*2+1,n,m+1,e);
26. int le=index*2,ri=index*2+1;
27. if(tre[le].first.first<tre[ri].first.first)
28. tre[index].F.F=tre[le].F.F;
29. else tre[index].F.F=tre[ri].F.F;
31. if(tre[le].F.S>tre[ri].F.S)
32. tre[index].F.S=tre[le].F.S;
33. else
34. tre[index].F.S=tre[ri].F.S;
35. }
37. int query(int index,int l,int r,int p,int dif)
38. {
39. if(l==r && tre[index].F.F<=p && tre[index].F.S>=p)
40. {
41. // do the needful
42. ran[tre[index].S]+=dif;
43. return 0;
44. }
45. if(tre[index].F.F<=p && tre[index].F.S>=p)
46. {
47. query(index*2,l,(l+r)/2,p,dif);
48. query(index*2+1,(l+r)/2+1,r,p,dif);
50. }
52. }
54. int main()
55. { // freopen("kr.in", "r", stdin);
56. long long int t;
57. lli a,b,c;
59. scanf("%lld",&t);
60. for(long long int i=0;i<t;i++)
61. {
62. scanf("%lld",&arr[i]);
63. if(i==0)
64. sum[i]=arr[i];
65. else
66. sum[i]=arr[i]+sum[i-1];
67. }
68. for(long long int i=0;i<t;i++)
69. {
70. scanf("%lld %lld",&a,&b);
71. a--,b--;
72. if(a==0)
73. ran[i]=sum[b];
74. else
75. ran[i]=sum[b]-sum[a-1];
76. pa[i]=make_pair(make_pair(a,b),i);
79. }
80. long long int mm;
81. sort(pa.begin(),pa.begin()+t);
82. // build a new seg tree for
83. build(1,t,0,t-1);
84. /* for(int i=1;i<=t*2;i++)
85. {
86. printf("%d %d %d %d \n",i,tre[i].F.F+1,tre[i].F.S+1,tre[i].S);
87. }*/
88. scanf("%lld",&mm);
89. for(long long int i=0;i<mm;i++)
90. {
91. scanf("%lld %lld %lld",&a,&b,&c);
92. if(a==1)//update
93. {b--;
94. to=0;
95. lli dif=c-arr[b];
96. arr[b]=c;
97. //int query(int index,int l,int r,int p,int dif)
98. query(1,0,t-1,b,dif);
101. }
102. else if(a==2)
103. {
104. b--;c--;
105. lli tt=0;
106. for(int i=b;i<=c;i++)
107. {
108. tt+=ran[i];
109. }
110. printf("%lld\n",tt);
111. }
112. }
114. }

The important point is the sort the range segment tree so that we are able to minimize the range will of the parent and we are able to choose the path , so just a overhead of sorting the ranges using pair sort and the creating the range tree we have great optimization for the range segment tree..... Enjoy the new concept.