Блог пользователя tech-pandit

spoj Problem D-query
Автор tech-pandit, 11 лет назад, По-английски

plz help me with this D-query problem .

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
11 лет назад, # |
← Rev. 5   Проголосовать: нравится +10 Проголосовать: не нравится

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;
	}
}
→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Since the problem's name contains the word "query" u had better use query-oriented language like SQL

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Does anybody know how to solve this if you can change elements also?

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

http://pastebin.com/j9g9CHAL

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А есть ли у этой задачи онлайн решение? и решение для ограничения a[i] <= 10^9?

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Можно использовать корневую декомпозицию по запросам. Тогда ограничений на числа нет (в пределах стандартных типов, естественно). Но это все равно оффлайн.
    А вот как онлайн делать — вопрос...

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Спасибо! Можно подробнее про корневую декомпозицию по запросам? В чем ее преимущество?

      → Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 5   Проголосовать: нравится +3 Проголосовать: не нравится
    • Можно сделать дерево отрезков с запросом количества различных на отрезке. Для этого сводим задачу к поиску на отрезке количества чисел меньших заданного. Для этого можно в каждой вершине дерева хранить весь подмассив целиком в отсортированном виде и по нему уже делать бинарный поиск. Только обычный lower_bound не прокатит, нужно ещё использовать технику частичного каскадирования (fractional cascading), чтобы каждый запрос был за O(log(n)), а не O(log2(n)). Последнее TL-ся :)
    • Ещё вроде можно решать online персистентным деревом отрезков, тоже за O(log(n)) на запрос.
    • Про большие числа ничего не могу сказать. Наверное их можно предварительно пожать, поскольку всего различных не больше n, тогда всё будет нормально.

    UPD: Всё-таки затолкал за O(log2(n)), только пришлось написать нерекурсивное ДО на стат массивах :)

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Можно поподробнее, как свести запрос о кол-ве различных к запросу о кол-ве меньших данного?

      → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

        Да, конечно!

        • Какие особенные числа можно взять с отрезка, чтобы правильно ответить на запрос о количестве различных чисел на данном отрезке?
        • Можно взять все такие числа, которые встречаются на этом отрезке впервые.
        • Для этого достаточно завести массив, в котором хранить позицию последнего вхождения такого же числа до позиции заданного (или -1, если оно встретилось впервые), например:
        //    0   1   2   3   4   5   6
a = [ 1,  2,  1,  5,  2,  2,  7]
b = [-1, -1,  0, -1,  1,  4, -1]
        • Теперь количество различных чисел на отрезке [l..r] в массиве a будет равно количеству чисел, меньших l, на отрезке [l..r] в массиве b.

        Принцип тот же, что писал goo.gl_SsAhv выше.

        → Ответить
        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Спасибо, почему-то до сих пор в голову было вбито, что деревом отрезков эту задачу решить нельзя.
          Кстати, для произвольных чисел оно очевидно также делается.

          → Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It can be solved online too with the same NLogn method using persistent segment tree

that's how i did it

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Mo's Algorithm which runs in O(NsqrtN) works in time and is fairly easy to code. I used C++, so some slower languages may get TLE.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

i am still getting tle

include<bits/stdc++.h>

using namespace std;

int main() { int n,p,count; scanf("%d",&n);

int a[n+1]; int pos[1000001]={0}; int cnt[n+1]={0}; for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&p); pair<int,int> q[p+1]; int ans[p+1]; for(int i=1;i<=p;i++) { scanf("%d%d",&q[i].first,&q[i].second); } for(int i=1;i<=n;i++) { if(pos[a[i]]!=0) cnt[pos[a[i]]]--; pos[a[i]]=i; cnt[pos[a[i]]]++; for(int m=1;m<=p;m++) { count=0; if(q[m].second==i) { for(int k=q[m].first;k<=q[m].second;k++) count+=cnt[k]; ans[m]=count; } } } for(int m=1;m<=p;m++) { printf("%d\n",ans[m]); } }

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    you need to use a segment tree or a Fenwick tree to calculate sum from q[m].first to q[m].second in O(log n) time.

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      it still is giving tle.

      include<bits/stdc++.h>

      using namespace std; int tree[6000000]; void build(int node, int start, int end,int *cnt) { if(start == end) { // Leaf node will have a single element tree[node] = cnt[start]; } else { int mid = (start + end) / 2; // Recurse on the left child build(2*node, start, mid,cnt); // Recurse on the right child build(2*node+1, mid+1, end,cnt); // Internal node will have the sum of both of its children tree[node] = tree[2*node] + tree[2*node+1]; } } int query(int node, int start, int end, int l, int r) { if(r < start or end < l) { // range represented by a node is completely outside the given range return 0; } if(l <= start and end <= r) { // range represented by a node is completely inside the given range return tree[node]; } // range represented by a node is partially inside and partially outside the given range int mid = (start + end) / 2; int p1 = query(2*node, start, mid, l, r); int p2 = query(2*node+1, mid+1, end, l, r); return (p1 + p2); } int main() { int n,p,count; scanf("%d",&n);

      int a[n+1]; int pos[1000001]={0}; int cnt[n+1]={0}; for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&p); pair<int,int> q[p+1]; int ans[p+1]; for(int i=1;i<=p;i++) { scanf("%d%d",&q[i].first,&q[i].second); } for(int i=1;i<=n;i++) { if(pos[a[i]]!=0) cnt[pos[a[i]]]--; pos[a[i]]=i; cnt[pos[a[i]]]++; build(1,1,i,cnt); for(int m=1;m<=p;m++) { if(q[m].second==i) { ans[m]=query(1,1,i,q[m].first,q[m].second); } } } for(int m=1;m<=p;m++) { printf("%d\n",ans[m]); } }

      → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I referred this article to make an editorial on the problem. It uses Mo's algorithm, which is offline query processing, to solve the problem in N*sqrt(N). Here is the video link.

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I'm getting WA on my code. I used MO's algorithm. Can anybody tell me why ? Link to my code

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I wrote an answer about it on Quora.

→ Ответить