liuaohanjsj's blog

By liuaohanjsj, 10 years ago, In English

第一次写英语题解,能力有限请不要见笑……

The first step in solving this problem is to understand the given program,which can be a little difficult.But once we know the thing we are going to do,things become easier.

In this case we are to count how many subarray of 'a' of length 'len' (we call it 'a1') matchs 'b'.When we say 'match' we mean that there exits a permutation of 'b'(we call it 'b1') have the property that each sum a1[i]+b1[i]>=h. The size of 'a' and 'b' is up to 150000,so it's no use iterating over all permutation and

checking whether it's right.Note that the order of b is not important,we can sort b in increasing order.For each a[i],we use dichotomy to find the min b[j] such that b[j]+a[i]>=h,which means we need to find a 'place' for a[i] in the range [j,len].We call these 'j's a new array 'border'.if we find a 'k' that there should be more than 'len-k+1' places in the range [k,len],we can be sure that it is impossible for a1 to match b1,because there are only 'len-k+1' places in this range.

Let's define a new array 'c',whose initial elements are 'len,len-1,len-2...1'.The element c[i] represents the rest palces in the range [i,len].Scan 'a' in order and make the subarray 'a1' move one step each time.For each new element of 'a1' a[i] we subtract 1 from 'c' in the range [1,border[i]],and for each element that is removed from 'a1' a[i-len],we add 1 to 'c' in the range[1,border[i-len]].Each time we check if the min element in 'c' is larger than 0,if so,ans++.Note that if 'border[i]'doesn't exit we shoud not take this new 'a1' into consideration.

The operation 'subtract','add' and 'find min element' can be done with segment tree or other data structur.The total time complexity is O(n*log(len)).

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it