日企面试题

最近面试了一个日企，online test时一道算法题没做出来，没有思路，应该也凉了，现求教地里的大神能否给一个思路，谢谢！本人惭愧，都不清楚这个题目要考什么，所以也没法归类…………

There's a hidden array arr, given its length n and a set of queries [L, R]. The query [L, R] means that we have already known the sum between arr[L] and arr[R] both inclusively, e.g. arr[L]+arr[L+1]+...+arr[R-1]+arr[R], return all possible indexes that we can get the corresponding value of arr. Here's an example:

If we set n = 3, queries = [[1,3], [2,2], [3,3]], then the answer should be [1,2,3]. Because from the queries, we have known the sum of arr[1]+arr[2]+arr[3], [2,2] and [3,3] means we also have known the value of arr[2] and arr[3], so we can finally get the value of arr[1].

Both the n and the number of queries satisfies: 1 <= n, the length of queries <= 10^5.

想客观地了解一下这道题难度大概什么水平？日企都是考这种难度的题目吗？谢了！

AtCoder（日本的编程竞赛网站）不太久之前出过几乎一模一样的题
ABC238-E https://atcoder.jp/contests/abc238/tasks/abc238_e

补充内容 (2022-05-06 07:54 +08:00):
https://kenkoooo.com/atcoder/#/table/
难度1577，折算成LeetCode的话大概是hard里中等的程度。OA正常不应该这么难

可以用Union Find.

uf = UF(100001).

Given [1,3], [2,2], [3,3] --> uf.Union(1, 4), uf.Union(2,3), uf.Union(3,4) --> [1,2,3,4] --> iterate element if adjacent difference is 1, then ret + 1;
One more example: [3,3], [4, 7], [8, 11], [3, 12], [15,15] --> union(3,4), union(4, 8), union(8, 12), union(3, 13), union(15, 16) --> [ [3,4,8,12, 13], [15, 16]] --> iterate this two vectors (other 100001 - 2 are size 1 vector) --> return 3.

Mark 一下

boltzmann 发表于 2022-5-5 02:55
可以用Union Find.

uf = UF(100001).

感谢提供思路！

"抱歉，您不能对匿名帖评分"

感觉可以用矩阵行变换化简，最后选出只有1的那些行里1所对应的列？

如果query是：
[2,3], [1,2], [3,4]

楼上的UF能得到：1，2，3，4，5。那么return 4.

可是我怎么一个数都求不出来？

fanshering 发表于 2022-5-5 21:17
感觉可以用矩阵行变换化简，最后选出只有1的那些行里1所对应的列？

这是个O(n^2)的方法吧？

插个眼 不会做 还没开始刷lc的算法小白上来强答一波
虽然我第一个反应也是UF 但是木有看懂楼上大哥的UF
我现在能想清楚的是 这道题有解的边界条件 是存在[n,n]
所以如果用暴力解法是先对[l,r]按照l从高到低排序？排序完后，l从低到高开始判断。如果对任一l，对所有的[l,r']，存在任意一个[l+1,r']，则l有解？
不行了，脑子不转了。等能看懂的答案。

补充内容 (2022-05-06 07:19 +08:00):
刚刚又想到的
不需要排序 用一个二维数组来存储读取的每个[l,r] 即s[l][r]=1，然后，然后我又不会了😂

补充内容 (2022-05-06 07:40 +08:00):
继续暴力解法，补充想到的
读取完成后，从小到大开始对每个[l.r]的时候做个判断，如果存在[l',r]，那么[l,l']=1
啊 好像复杂度还是n平方
好丑陋的解法