fork download
copy 
  1. #include <iostream>
  2. #include <math.h>
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <algorithm>
  6. #include <vector>
  7. #include <queue>
  8. #include <stack>
  9. #include <set>
  10. #include <iterator>
  11. #include <map>
  12. #include <cstring>
  13. #include <climits>
  14. #include <time.h>
  15.  
  16. using namespace std;
  17.  
  18. #define READ() 	freopen("in.txt","r",stdin)
  19. #define WRITE() freopen("out.txt","w",stdout)
  20. #define sf(n) 	scanf("%d",&n)
  21. #define lsf(n) 	scanf("%lld", &n)
  22. #define pb(n) 	push_back(n)
  23. #define EPS 	1e-10
  24. #define NL 		printf("\n")
  25. #define INF     INT_MAX
  26. #define MAX     500010
  27. #define MOD     1000000007
  28. #define LL      long long
  29.  
  30. #define callLeft()
  31. #define callRight() (right,mid+1,j)
  32. #define cnd tree[idx]
  33. #define lnd tree[left]
  34. #define rnd tree[left+1]
  35.  
  36. using namespace std;
  37.  
  38. /**
  39. problem: how many numbers in a segment that appears exactly 2 times!
  40. PREREQUSITE : loj - 1188; i wrote an editorial there.
  41. Solution : off-line solve, segment tree.
  42. okay lets jump into it with an example (given array):
  43. 8
  44. 1 1 1 2 3 5 1 2
  45.  
  46. first lets solve the problem if the query always starts from 0th index and ends at any index.
  47. how to approach that?
  48. using this array: 0 1 -1 0 0 0 0 1 (and make cumulative sum array of course!)
  49. query [0-7] ans = 1. correct.
  50. query [0-1] ans = 1. correct.
  51. okay let me explain how i made this array here.
  52. we marked the index where x has appeared 2nd time as 1, meaning:
  53. till this index, there is an answer.
  54.  
  55. then, as we need numbers who are present EXACTLY 2 times,
  56. we marked the the index where x has appeared 3rd time as -1, which
  57. crosses out index where x appeared 2nd time, meaning:
  58. till this point there is no answer! i hope the making of the array is clear now!
  59.  
  60. now the next part,
  61. what happens when the starting index of query is not 0th index?
  62. this is where off-line solve comes into play!
  63.  
  64. we will use this array still:
  65. 0 1 -1 0 0 0 0 1
  66.  
  67. but how do we get the answer when the query is lets say [1,2]
  68. using current array if we try to find the answer then the answer will be 0, which is wrong!
  69. so how do we find it? think about it!
  70. if we make the 1st index 0, 2nd index 1 and 6th index -1 then
  71. we can answer any query starting from 1st index! :D
  72. and the array is : 0 0 1 0 0 0 -1 1
  73.  
  74. can you say why we specifically updated the 1st,2nd,6th index?
  75. because those are the places where 1 is present.
  76. and we changed the positions where 1 is present, why?
  77. because 1 is 0th index, which is the previous 1st index.
  78.  
  79. so for example if the query is [2-7]
  80. the we would have to do the same for 0th index value, 1st index value.
  81. and the array will be like:
  82. 0 0 0 0 0 0 1 1
  83. and the answer is 2!
  84.  
  85. we simple used segment tree to update and find the query.
  86. **/
  87.  
  88. struct Qinfo /// query input goes here
  89. {
  90.     int x,y,i;
  91. };
  92.  
  93. bool QinfoCmp(Qinfo x1, Qinfo x2) /// sort by x
  94. {
  95.     if(x1.x < x2.x)return true;
  96.     else if(x1.x == x2.x)
  97.     {
  98.         if(x1.y < x2.y)return true;
  99.         return false;
  100.     }
  101.      return false;
  102. }
  103. int prevUsed[MAX]; /// to remember if it was used before!
  104. int treeBuild[MAX]; /// to initialize the values and build tree
  105.  
  106. ///**********************************************************Segment Tree Starts*****************************
  107. /// Segment Tree Type: Simple summation in range
  108. struct node
  109. {
  110.     int sum;
  111.     node()
  112.     {
  113.         sum = 0;
  114.     }
  115. };
  116.  
  117. node tree[4*MAX];
  118.  
  119. void mergeNodes(int idx,int left,int right)
  120. {
  121.     cnd.sum = (tree[left].sum + tree[right].sum);
  122. }
  123.  
  124. void build(int idx,int st,int ed)
  125. {
  126.     if(st == ed)
  127.     {
  128.         cnd.sum = treeBuild[st];
  129.         return;
  130.     }
  131.     int left = idx*2;
  132.     int right = left+1;
  133.     int mid = (st+ed)/2;
  134.  
  135.     build(left,st,mid);
  136.     build(right,mid+1,ed);
  137.     mergeNodes(idx,left,right);
  138. }
  139.  
  140. void update(int idx,int st,int ed,int i,int j,int v)
  141. {
  142.     if(i > ed || j < st)return;
  143.     if(st >= i && ed <= j)
  144.     {
  145.         cnd.sum = v;
  146.         return;
  147.     }
  148.     int left = idx<<1;
  149.     int right = left+1;
  150.     int mid = (st+ed)>>1;
  151.  
  152.     update(left,st,mid,i,j,v);
  153.     update(right,mid+1,ed,i,j,v);
  154.  
  155.     mergeNodes(idx,left,right);
  156. }
  157.  
  158. int query(int idx,int st,int ed,int i,int j)
  159. {
  160.     if(i > ed || j < st)return 0;
  161.     if(st >= i && ed <= j)
  162.     {
  163.         return cnd.sum;
  164.     }
  165.  
  166.     int left = idx<<1;
  167.     int right = left+1;
  168.     int mid = (st+ed)>>1;
  169.  
  170.     return (query(left,st,mid,i,j) + query(right,mid+1,ed,i,j));
  171. }
  172. ///**********************************************************Segment Tree Ends*****************************
  173.  
  174.  
  175. int arr[MAX]; /// input arr
  176. vector <int> vec[MAX]; /// used for next index of value X
  177. int lastIndex[MAX]; /// keeping count of how many indexed used of value X
  178. Qinfo qi[MAX]; /// storing query
  179. int ansStore[MAX]; /// storing answer
  180.  
  181. int main()
  182. {
  183. //    READ();
  184. //    WRITE();
  185.  
  186.     int t;
  187. //    sf(t);
  188.     t = 1;
  189.     int TC = 0;
  190.  
  191.     while(t--)
  192.     {
  193.         int n;
  194.         sf(n);
  195.         int q;
  196.         sf(q);
  197. //        memset(arr,0,sizeof(arr));
  198.         memset(tree,0,sizeof(tree));
  199.         memset(prevUsed,false,sizeof(prevUsed));
  200.         memset(lastIndex,0,sizeof(lastIndex));
  201.         memset(treeBuild,false,sizeof(treeBuild));
  202. //        memset(xStore,-1,sizeof(xStore));
  203.  
  204.         for(int i=0;i<MAX;i++)vec[i].clear();
  205.  
  206.         map <int,int> mp;
  207.         int cntDistVal = 1;
  208.         for(int i=1;i<=n;i++)
  209.         {
  210.             sf(arr[i]);
  211.             if(mp.find(arr[i]) == mp.end())mp[arr[i]] = cntDistVal++;
  212.         }
  213.         for(int i=1;i<=n;i++)
  214.         {
  215.             int x = mp[arr[i]];
  216.  
  217.             if(prevUsed[x] == 0)
  218.             {
  219.                 prevUsed[x]++;
  220.                 treeBuild[i] = 0;
  221.             }
  222.             else if(prevUsed[x] == 1)
  223.             {
  224.                 prevUsed[x]++;
  225.                 treeBuild[i] = 1;
  226.             }
  227.             else if(prevUsed[x] == 2)
  228.             {
  229.                 prevUsed[x]++;
  230.                 treeBuild[i] = -1;
  231.             }
  232.  
  233.             else treeBuild[i] = 0;
  234.  
  235.             vec[x].pb(i);
  236.         }
  237. //        n = cntDistVal;
  238.         build(1,1,n);
  239.  
  240.         for(int i=0;i<q;i++)
  241.         {
  242.             int x,y;
  243.             sf(x);
  244.             sf(y);
  245.             qi[i].x = x;
  246.             qi[i].y = y;
  247.             qi[i].i = i;
  248.         }
  249.         sort(qi,qi+q,QinfoCmp);
  250.  
  251. //        for(int i=0;i<q;i++)
  252. //        {
  253. //            cout << qi[i].x << " to " << qi[i].y << "  index:" << qi[i].i << endl;
  254. //        }
  255.  
  256.         int initStart = 1;
  257.         for(int i=0;i<q;i++)
  258.         {
  259. //            cout << qi[i].x << " to " << qi[i].y << "  index:" << qi[i].i << endl;
  260.             int qX = qi[i].x;
  261.             while(initStart != qX) /// sweeping from left to right
  262.             {
  263. //                int vecI = arr[initStart];
  264.                 int vecI = mp[arr[initStart]];
  265.                 int updateIndex = vec[vecI][lastIndex[vecI]];
  266. //                cout << "update 0 at: " << updateIndex << endl;
  267.                 update(1,1,n,updateIndex,updateIndex,0); /// making current index 0
  268.  
  269.                 if(vec[vecI].size() > lastIndex[vecI] + 1)
  270.                 {
  271. //                    lastIndex[vecI]++;
  272.                     updateIndex = vec[vecI][lastIndex[vecI]+1]; /// making next index 0
  273. //                    cout << "update 1 at: " << updateIndex << endl;
  274.                     update(1,1,n,updateIndex,updateIndex,0);
  275.                 }
  276.                 if(vec[vecI].size() > lastIndex[vecI] + 2)
  277.                 {
  278. //                    lastIndex[vecI]+=2;
  279.                     updateIndex = vec[vecI][lastIndex[vecI]+2]; /// making next index 1
  280. //                    cout << "update 1 at: " << updateIndex << endl;
  281.                     update(1,1,n,updateIndex,updateIndex,1);
  282.                 }
  283.                 if(vec[vecI].size() > lastIndex[vecI] + 3)
  284.                 {
  285. //                    lastIndex[vecI]+=2;
  286.                     updateIndex = vec[vecI][lastIndex[vecI]+3]; /// making next index -1
  287. //                    cout << "update 1 at: " << updateIndex << endl;
  288.                     update(1,1,n,updateIndex,updateIndex,-1);
  289.                 }
  290.                 lastIndex[vecI]++;
  291.  
  292.                 initStart++;
  293.             }
  294.             int qrr = query(1,1,n,qi[i].x,qi[i].y); /// query
  295.             ansStore[qi[i].i] = qrr; /// saving
  296. //            cout << "ans : " << qrr << endl;
  297. //            cout << endl << endl;
  298.         }
  299.  
  300. //        printf("Case %d:\n",++TC);
  301.         for(int i=0;i<q;i++)
  302.         {
  303.             printf("%d\n",ansStore[i]);
  304.         }
  305.     }
  306.     return 0;
  307. }
  308.  
  309.  
  310.  
  311.  
Success #stdin #stdout 0s 32776KB
comments (?)
stdin
copy 
5 2
1 1 1 1 1
2 4
2 3
stdout
copy 
0
1
https://ideone.com/7gmXX7
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!