Получите количество отдельных элементов в подматрице

Question

Это было a problem from the December 2013 CodeChef Challenge, и конкурс закончился.

Постановка задачи:

Вход: квадратная матрица порядка п и запрос, который будет обозначать подматрицы.

(x1, y1, x2, y2)

x1, y1 обозначает верхний левый и x2, y2 обозначает нижний правый конец подматрицы.

Выход: Количество различных элементов в этой подматрице.

Ограничения:

• Ограничение по времени = 1 сек
• 1 ≤ N ≤ 300
• 1 ≤ Q ≤ 10^5
• 1 ≤ Ai, J ≤ 10
• 1 ≤ X1 ≤ X2 ≤ N
• 1 ≤ Y1 ≤ Y2 ≤ N

Это то, что я пробовал:

#include<stdio.h> 
//#include<conio.h> 
int main() 
{ 
    //clrscr(); 
    int a[300][300], test[100000], count[10], m, n, c, j, p, q, r, s; 
    long qu, re, i; 

    scanf("%d", &n); 

    for (i = 0; i < n; i++) 
    { 
    for (j = 0; j < n; j++) 
    { 
     scanf("%d", &a[i][j]); 
    } 
    } 

    scanf("%ld", &qu); 
    for (re = 0; re < qu; re++) 
    { 
    c = 0; 
    for(i = 0; i < 10; i++) 
    { 
     count[i] = 0; 
    } 

    scanf("%d %d %d %d", &p, &q, &r, &s); 
    for (i = (p-1); i < r; i++) 
    { 
     for (j = (q-1); j < s; j++) 
     { 
     m = a[i][j]; 
     count[--m]++; 
     } 
    } 

    for (i = 0; i < 10; i++) 
    { 
     if (count[i] != 0) 
     { 
     c++; 
     } 
    } 
    test[re] = c; 
    } 

    for(i = 0; i < qu; i++) 
    { 
    printf("%d\n", test[i]); 
    } 

    //getch(); 
    return 0; 
} 

Но я получил TLE (ограничение превышено время) ошибка.

Он должен что-то делать с суммарной частотой каждого номера.

Может кто-нибудь предложить эффективный алгоритм для решения этой проблемы?

Answer 1

Инициализировать и отслеживать карту хэша.

Итерация по записям в подматрицы, и для каждой записи,

• проверить, если он находится в уже хэш-карте;
• если нет, добавьте total_distinct_entries на 1 и добавьте эту запись в хэш-карту.

См. http://en.wikipedia.org/wiki/Hash_table.

Редактировать: См. Также http://en.wikipedia.org/wiki/Set_data_structure, в частности раздел о реализации. В C++ структура данных std::set доступна в стандартной библиотеке.

Answer 2

EDITED

(работа с 1 индекс, основанный)

Первая попытка:

ли перебор, хранение подсчет каждого числа в графской массиве, как вопрос плакат дал, но это, безусловно, тайм-аут на множество тестовых случаев.

Second: Поскольку мы знаем, что записи могут быть только до 10, мы можем попытаться сохранить количество раз, которое каждое число появляется в подматрице (1,1) до (i, j). Предположим, что эта матрица Q. Q [i] [j] [k] дает число раз k появляется в подматрице i, j.

Это может быть вычислено эффективно следующим образом:

for i from 1 to n 
    for j from 1 to n 
     for k from 0 to 10 
      Q[i][j][k] = Q[i-1][j][k] + Q[i][j-1][k] - Q[i-1][j-1][k] 
     Q[i][j][A[i][j]]++ 

Это может быть сделано в O (N^2 * (к)) времени. Так как k меньше 10, это довольно эффективно.

Теперь отвечать на запросы довольно просто:

Для запроса (x1, y1) - (x2, y2)

int count[10] 
for k from 0 to 10 
    // x is row and y is column 
    count[k] = Q[x2][y2][k] - Q[x1-1][y2][k] - Q[x2][y1-1][k] + Q[x1-1][y1-1][k] 

Это отвечает на все запросы в O (к) время. Так как k от 0 до 10. Это хорошо в пределах срока.