Saturday, 13 December 2014

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];
  12. vector <pair<pair<int,int> ,int> > pa(100005),tre(300005);
  13. vector <pair<pair<int,int> ,int> > :: iterator it,it2;
  14. //build(1,t,0,t-1);
  15. int build(int index, int n, int s,int e )
  16. {
  17. if(s==e)
  18. {
  19. tre[index]=pa[s];
  20. return 0;
  21. }
  22. int m=(s+e)/2;
  23. build(index*2,n,s,m);
  24. build(index*2+1,n,m+1,e);
  25. int le=index*2,ri=index*2+1;
  26. if(tre[le].first.first<tre[ri].first.first)
  27. tre[index].F.F=tre[le].F.F;
  28. else tre[index].F.F=tre[ri].F.F;
  29. if(tre[le].F.S>tre[ri].F.S)
  30. tre[index].F.S=tre[le].F.S;
  31. else
  32. tre[index].F.S=tre[ri].F.S;
  33. }
  34. int query(int index,int l,int r,int p,int dif)
  35. {
  36. if(l==r && tre[index].F.F<=p && tre[index].F.S>=p)
  37. {
  38. // do the needful
  39. ran[tre[index].S]+=dif;
  40. return 0;
  41. }
  42. if(tre[index].F.F<=p && tre[index].F.S>=p)
  43. {
  44. query(index*2,l,(l+r)/2,p,dif);
  45. query(index*2+1,(l+r)/2+1,r,p,dif);
  46. }
  47. }
  48. int main()
  49. { // freopen("kr.in", "r", stdin);
  50. long long int t;
  51. lli a,b,c;
  52. scanf("%lld",&t);
  53. for(long long int i=0;i<t;i++)
  54. {
  55. scanf("%lld",&arr[i]);
  56. if(i==0)
  57. sum[i]=arr[i];
  58. else
  59. sum[i]=arr[i]+sum[i-1];
  60. }
  61. for(long long int i=0;i<t;i++)
  62. {
  63. scanf("%lld %lld",&a,&b);
  64. a--,b--;
  65. if(a==0)
  66. ran[i]=sum[b];
  67. else
  68. ran[i]=sum[b]-sum[a-1];
  69. pa[i]=make_pair(make_pair(a,b),i);
  70. }
  71. long long int mm;
  72. sort(pa.begin(),pa.begin()+t);
  73. // build a new seg tree for
  74. build(1,t,0,t-1);
  75. /* for(int i=1;i<=t*2;i++)
  76. {
  77. printf("%d %d %d %d \n",i,tre[i].F.F+1,tre[i].F.S+1,tre[i].S);
  78. }*/
  79. scanf("%lld",&mm);
  80. for(long long int i=0;i<mm;i++)
  81. {
  82. scanf("%lld %lld %lld",&a,&b,&c);
  83. if(a==1)//update
  84. {b--;
  85. to=0;
  86. lli dif=c-arr[b];
  87. arr[b]=c;
  88. //int query(int index,int l,int r,int p,int dif)
  89. query(1,0,t-1,b,dif);
  90. }
  91. else if(a==2)
  92. {
  93. b--;c--;
  94. lli tt=0;
  95. for(int i=b;i<=c;i++)
  96. {
  97. tt+=ran[i];
  98. }
  99. printf("%lld\n",tt);
  100. }
  101. }
  102. }
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.