Algorithms-and-Data-structure/Dquery0.cpp at master · atulbi/Algorithms-and-Data-structure · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define mod 1000000007
using namespace std;

vector<int> v;
vector<int> cnt(1000010,0);
int q;
int BLOCK ;
int answer = 0;

class node
{
public:
	int i,l,r;
	node(int left , int right, int index )
	{
		i = index;//ORIGINAL INDEX OF QUERY
		l = left ;
		r = right;
	}
	friend ostream& operator<<(ostream &out , node &a)
	{
		out<<a.l<<" "<<a.r<<" "<<a.i<<" "<<endl;
	}

};

//******************COMPARISON FOR SORT*****************
bool mycomparison(node& a, node& b)
{
	if(a.l/BLOCK ==b.l/BLOCK)
	{
		return a.r<b.r;
	}
	else
	{
		return a.l/BLOCK<b.l/BLOCK;
	}
}
//*****************************************************


void add(int index)
{
	cnt[v[index]]++;
	if(cnt[v[index]]==1)
	{
		answer++;
	}
}
void rem(int index)
{
	cnt[v[index]]--;
	if(cnt[v[index]]==0)
	{
		answer--;
	}
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	scanf("%i",&n);


	for (int i = 0; i <n; ++i)
	{
		int k;
		scanf("%i",&k);
		v.push_back(k);
	}


	scanf("%i",&q);
	BLOCK = sqrt(q);
//********* QUERY RE-ARRANGEMENT PART MOH'S ALGORITHM *********
	vector<node> query;
	for(int i = 0; i<q;i++)
	{
		int a, b;
		scanf("%i%i",&a,&b);
		query.push_back(node(a-1,b-1,i));
	}

	sort(query.begin() , query.end(),mycomparison);

//**************************************************************

	int left_move = 0;
	int right_move = 0;

	int ans[q] ;
	for(auto x : query)
	{
		int left = x.l;
		int right = x.r;

		while(left_move < left)
		{
			rem(left_move);
			left_move++;
		}
		while(left_move > left)
		{
			add(left_move-1);
			left_move--;
		}
		while(right_move <= right)
		{
			add(right_move);
			right_move++;
		}
		while(right_move > right+1)
		{
			rem(right_move-1);
			right_move--;
		}
		ans[x.i] = answer;
	}

	for (auto p : ans)
		printf("%i\n",p);
}