查詢大小爲K

Question

的所有連續子陣列讓我們定義一個大小爲K的數組B[1:K]的運算，即計算子陣列B[2:K]中小於B[1]的元素數。

現在我有一個大小爲N的數組A[1:N]，我的目標是對大小爲K的所有連續子數組執行上述操作。

例

A = [4, 3, 6, 2, 1] and K = 3有很多3大小的3鄰接子陣列。

1. B = [4, 3, 6]count = 1[(3 < 4)]
2. B = [3, 6, 2]count = 1[(2 < 3)]
3. B = [6, 2, 1]count = 2[(2 < 6), (1 < 6)]

蠻力方法的時間複雜度將是O((N-K+1)*K)由於在尺寸的連續子陣列執行上述操作K是O(K)。

我能做到在Nlog(M)有效，即如果我可以設計，其具有以下性質

1. 插入在比X較小的元素的log(M)
2. 缺失在log(M)
3. 計數數目的數據結構 在log(M)

我是C++用戶，我不認爲有任何數據結構可以滿足所有提及的要求。還有其他方法可以改進嗎？請幫忙。

Answer 1

這有幫助嗎？

#include <iostream> 
#include <cstdio> 
#include <set> 
using namespace std; 
int bit[100005]={0}; 
// using BIT since numbers can repeat and set won't work 
void update(int idx, int val, int n){ 
    while(idx < n){ 
     bit[idx] += val; 
     idx += (idx & -idx); 
    } 
} 
int get(int idx){ 
    int ret = 0; 
    while(idx > 0){ 
     ret += bit[idx]; 
     idx -= (idx & -idx); 
    } 
    return ret; 
} 
int main() { 
    int n, a[100005] = {0}, i, ans=0, k, maxx = -1; 
    scanf("%d%d", &n, &k); 
    for(i=0; i<n; i++){ 
     scanf("%d", &a[i]); 
     if(maxx < a[i]){ 
      maxx = a[i]; 
     } 
    } 
    maxx++; 
    for(i=0;i<n;i++){ 
     a[i] = maxx - a[i]; 
    } 

    // now the problem becomes the opposite of what it initially was 
    // now a[i] would contribute to ans if we can find an element a[j] where a[j] < a[i] and (i-j)<=k 

    for(i=0;i<n;i++){ 
     if(i-k>=0){ 
      // remove i-k'th element from the BIT since it doesn't contribute 
      update(a[i-k], -1, maxx); 
     } 
     if(i >= k-1){ 
      // add how a[i] is gonna contribute to the final answer, it would be the number of elements less than a[i] 
      ans += get(a[i]); 
     } 
     // add a[i] to the BIT 
     update(a[i], 1, maxx); 
    } 
    printf("%d\n", ans); 
    return 0; 
} 

Answer 2

您可能想要使用set來計算小於k的元素的附加操作。這可以實現爲二叉搜索樹（經典集合實現），並在每個節點中具有附加統計量（基本上樹中節點的大小）。

更多細節在這裏：https://stackoverflow.com/a/15321444/1391392 這裏的一些實施：https://sourceforge.net/projects/orderstatistics/

其他選項，這可能看起來更簡單明瞭是使用skiplists。 https://en.wikipedia.org/wiki/Skip_list