我們如何找到給定子矩陣中不同元素的數量？

-7

給定相同給定矩陣的N * N矩陣和Q查詢。每個查詢的形式爲x1，y1，x2，y2。我們必須找到由（x1，y1）和（x2，y2）定義的子矩陣中不同元素的數量分別爲左上角和右下角。約束條件：N < = 300 Q < = 10^5 我正在使用樸素方法迭代每個查詢的子矩陣。有沒有更好的方法？我們如何找到給定子矩陣中不同元素的數量？

來源

2013-12-10 SuperCoder

最後一個發佈此問題的人包括的是，每個單元的可能條目數量也受到限制。在上一篇文章中，數值介於1和10之間。如果您有類似的限制，它會使問題更容易。是的，有了足夠的預先計算，您可以將問題簡化爲O（1）。最後一個人還發布了原始問題的鏈接，這裏是：[codechef.com]（http://www.codechef.com/DEC13/problems/RECTQUER） – woolstar

這個問題來自於正在進行的codechef競賽。來自codechef網站：「討論CodeChef的問題或任何其他問題的方面，在任何其他平臺上的身份識別，可能導致禁用各自的帳戶和禁止從社區。」 –

終於我自己解決了。然而，感謝所有你們堅守「codechef行爲準則」的追隨者。 – SuperCoder

這取決於您可以期待多少個查詢，以及您可以預期的相同查詢的數量。

一種方法是「記憶」查詢，簡單地存儲每個查詢和結果，並在進行更嚴肅的工作之前查看該查詢。

更具體的問題的方法–可能你的老師在–之後是爲每個（右，底）=（x，y）計算不同的（0，0，x，y）元素。然後，它是簡單的集合論來處理每個查詢。但做原始計算是耗時的。

請記住添加對此SO回答的引用。

來源

2013-12-10 06:22:07

時間限制爲1秒，問題中提到的查詢數量爲10^5。矩陣的每個元素都是僅在1到10範圍內的數字。所以我認爲這些appproaches都不足以被接受。你能建議任何與分段樹有關的東西嗎？ – SuperCoder

那麼在上面的答案中的建議很好地工作（有一點闡述）。但是，Codechef問題中的示例與描述不一致，顯然他是矩陣中的x和y。顯然，可能的輸入值的描述也是錯誤的。無論如何，我編寫了一個例子，它在本地工作，但嘗試各種不同的協調系統等，所有變種只是在網站上產生「錯誤的答案」。 –

好吧，終於得到正確的答案，但在抽象成本，服務器上運行時間0.21秒。主要信息：如例子中的座標系統，x向右和y向右。 –

我們如何找到給定子矩陣中不同元素的數量？

回答

相關問題