Advertisement
Guest User

Untitled

a guest
Dec 31st, 2013
1,017
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.43 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <math.h>
  4. #include <vector>
  5. using namespace std;
  6. int a,b,c,d,e,f,g;
  7. vector<int> tree[250000];
  8. void query(int cvor,int from,int to,int a,int b)
  9. {
  10. if(from>=a && to<=b)
  11. {
  12. //napravi nesto sa varijablom G
  13. int low=0;
  14. int midd=0;
  15. int high=tree[cvor].size()-1;
  16. while(low<=high)
  17. {
  18. midd=(low+high)/2;
  19. //printf("%d %d\n",midd,tree[cvor][midd]);
  20. if(tree[cvor][midd]<=f)low=midd+1;
  21. else high=midd-1;
  22. }
  23. g+=(tree[cvor].size()-low);
  24. //printf("Cvor %d %d\n",cvor,tree[cvor].size()-low);
  25. return;
  26. }
  27. if((from+to)/2>=a)query(cvor*2,from,(from+to)/2,a,b);
  28. if((from+to)/2+1<=b)query(cvor*2+1,(from+to)/2+1,to,a,b);
  29. }
  30. int main()
  31. {
  32. scanf("%d",&a);
  33. for(b=1;b<a;b*=2){}
  34. for(int i=0;i<a;++i)
  35. {
  36. scanf("%d",&c);
  37. tree[i+b].push_back(c);
  38. }
  39. //konstrukcija binarnog stabla
  40. for(int i=a+b-1;i>1;--i)
  41. {
  42. //tree[i/2]+=tree[i];
  43. for(int j=0;j<tree[i].size();++j)tree[i/2].push_back(tree[i][j]);
  44. if(i%2==0)sort(tree[i/2].begin(),tree[i/2].end());
  45. }
  46. scanf("%d",&c);
  47. for(int i=0;i<c;++i)
  48. {
  49. scanf("%d%d%d",&d,&e,&f);
  50. g=0;
  51. //prodi kroz segment tree
  52. query(1,0,b-1,d-1,e-1);
  53. printf("%d\n",g);
  54. }
  55. return 0;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement