4. Find the smallest positive integer $t$ such that: If each cell of a $100 \times 100$ grid is colored with some color, and the number of cells of each color does not exceed 104, then there exists a $1 \times t$ or $t \times 1$ rectangle containing at least three different colors in its $t$ cells.
Divide the grid paper into 100 $10 \times 10$ squares, each of the 100 small squares in each square is dyed the same color, and different squares are dyed different colors. This coloring method satisfies the problem's conditions, and it is easy to see that any $1 \times 11$ or $11 \times 1$ rectangle contains at most two colors of small squares, so $t \geqslant 12$. Below, we prove that $t=12$ has the properties described in the problem.

Lemma: Dye each small square of a $1 \times 100$ grid $X$ a certain color. If one of the following two conditions is met, then there exists a $1 \times 12$ rectangle that contains at least three colors.
(1) $X$ contains at least 11 colors;
(2) $X$ contains exactly 10 colors, and each color is used to dye exactly 10 small squares.

Proof: Use proof by contradiction, assuming the conclusion does not hold.
Take the rightmost square of each color, let them be in (from left to right) the $x_{1}100$, contradiction. Thus, the conclusion holds under condition (1);
If condition (2) holds, consider the squares from the $(x_{1}+1)$-th to the $(x_{1}+11)$-th. Since each color has at most 10 squares, these 11 squares must contain at least two colors, and neither is $c_{1}$, so from the $x_{1}$-th to the $(x_{1}+11)$-th squares, there are at least three colors, contradiction. Thus, the conclusion also holds under condition (2). In summary, the lemma is proven.
Let $c_{1}, c_{2}, \cdots, c_{k}$ be all the colors that appear. For $1 \leqslant i \leqslant k$, let $s_{i}$ be the number of small squares of color $c_{i}$, $u_{i}$ be the number of rows containing small squares of color $c_{i}$, and $v_{i}$ be the number of columns containing small squares of color $c_{i}$. By the condition, $s_{i} \leqslant 104$, and clearly $u_{i} v_{i} \geqslant s_{i}$, equality holds if and only if all the intersections of the rows and columns containing $c_{i}$-colored small squares are $c_{i}$-colored small squares.
We now prove: $u_{i}+v_{i} \geqslant \frac{1}{5} s_{i}$, equality holds if and only if $u_{i}=v_{i}=10, s_{i}=100$. If $u_{i}+v_{i} \geqslant 21$, then by $s_{i} \leqslant 104 \Rightarrow u_{i}+v_{i}>\frac{1}{5} s_{i}$; If $u_{i}+v_{i} \leqslant 20$, then $u_{i}+v_{i} \geqslant \frac{\left(u_{i}+v_{i}\right)^{2}}{20} \geqslant \frac{4 u_{i} v_{i}}{20} \geqslant \frac{s_{i}}{5}$, equality holds if and only if $u_{i}=v_{i}=10, s_{i}=100$. Thus, $\sum_{i=1}^{k}\left(u_{i}+v_{i}\right) \geqslant \sum_{i=1}^{k} \frac{1}{5} s_{i}=2000$. If $\sum_{i=1}^{k}\left(u_{i}+v_{i}\right)=2000$, then by the condition for equality, it can be known that each color is used to dye exactly 100 squares, and is the intersection of 10 rows and 10 columns, so each row and each column contains exactly 10 colors of squares, and each color of squares also has exactly 10; If $\sum_{i=1}^{k}\left(u_{i}+v_{i}\right)>2000$, by the pigeonhole principle, there exists a row or column that contains at least 11 colors of small squares.
By the lemma, both of these situations lead to the existence of a $1 \times 12$ or $12 \times 1$ rectangle containing at least three colors of small squares. In summary, the smallest $t$ is 12.