d query spoj

Was trying to solve http://www.spoj.com/problems/DQUERY/ but could not get it how to solve it , though i know Segment tree and have read solution http://apps.topcoder.com/forums/?module=Thread&threadID=627423&start=0&mc=8#1060242 but couldnot get him???
plzzz anyone can explain it…

1 Like

there is simple `NlogN` offline solution:

``````int posOfLast[2e6] = {-1, -1 ....};
int a[n];
int cnt[n];
// input

for (int i = 0; i < n; ++i) {
if (posOfLast[a[i]] != -1)
cnt[posOfLast[a[i]]]--;
posOfLast[a[i]] = i;
cnt[posOfLast[a[i]]]++;

for (all q in Queries where q.R == i) {
sum = 0;

// { this part can be done in O(Log(n))
// using Range Sum Query structure, or fenvick tree, or segment tree
for (int j = q.L; j <= q.R; j++)
sum += cnt[j];
// }

ans[q.Id] = sum;
}
}
``````
``````#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <ctime>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <queue>
#include <memory.h>
#include <iostream>
#include <stack>
#include <complex>
#include <list>

using namespace std;

void ASS(bool b) {
if (!b) {
++*(int*)0;// crash
}
}

typedef vector<int> vi;
typedef long long LL;

#define FOR(i, n) for (int i = 0; i < (int)(n); ++i)

int posOfLast[(int)2e6]; // = {-1, -1 ....};

const int n = 6;
int a[n] = {1, 2, 3, 4, 1, 2};
int cnt[n];

struct Q {
int id;
int L, R;
};

vector<Q> qq[n];

vector<int> ans;

void AddQ(int L, int R) {
Q q;
q.L = L;
q.R = R;

q.id = (int)ans.size();
ans.push_back(0);

qq[R].push_back(q);
}

int main()
{
memset(posOfLast, 0xFF, sizeof(posOfLast)); // = {-1, -1 ....};

for (int j = 0; j < n; ++j)
printf("%d ", a[j]);
printf("\n");

for (int i = 0; i < n; ++i) {
if (posOfLast[a[i]] != -1)
cnt[posOfLast[a[i]]]--;
posOfLast[a[i]] = i;
cnt[posOfLast[a[i]]]++;

printf("i = %d\ncnt = {", i);
for (int j = 0; j < n; ++j)
printf("%d ", cnt[j]);
printf("// ");

for (int query = 0; query < (int)qq[i].size(); ++query) {
Q q = qq[i][query];
ASS(q.R == i); // always true;
int sum = 0;

for (int j = q.L; j <= q.R; j++)
sum += cnt[j];
ans[q.id] = sum;
printf("answer for [%d, %d] is %d; ", q.L, q.R, ans[q.id]);
}
printf("\n");
}

return 0;
}
``````

why i need to sort the queries according to their end index??

this is the wrong answer which is provided above…

int posOfLast[2e6] = {-1, -1 …};
int a[n];
int cnt[n];
// input

for (int i = 0; i < n; ++i) {
if (posOfLast[a[i]] != -1)
cnt[posOfLast[a[i]]]–;
posOfLast[a[i]] = i;
cnt[posOfLast[a[i]]]++;

``````for (all q in Queries where q.R == i) {
sum = 0;

// { this part can be done in O(Log(n))
// using Range Sum Query structure, or fenvick tree, or segment tree
for (int j = q.L; j <= q.R; j++)
sum += cnt[j];
// }

ans[q.Id] = sum;
}
``````

}