寻找一种有效的算法来回答给定方阵的子矩阵中的查询

Question

我正在尝试解决2013年12月CodeChef竞赛中的"矩形查询"问题:

给定方阵N x N,用{1,... 10}的整数填充.给定Q(10 ^ 5)个查询如下给定x1,y1,x2,y2找到给定子矩阵中的唯一元素的数量.

限制:N <= 300 Q(10 ^ 5)x1 <= x2 <= N y1 <= y2 <= N时限1秒.

我尝试过使用std :: set获取唯一性的方法,但是获得了TLE ...我的方法很天真...从左上角到右下角循环查询并添加元素到set..then printing std :: set.size ().

Answer 1

有两种可能的方法: -

1. 自己解决问题并获得难以获得的积分.

2. 等待比赛结束并在社论中查看解决方案.

祝好运.