子数组中两个数字的相同出现（连续）

Question

int get_total(int* a,int x,int y,int n){
    int result=0;
    for(int i=0;i<n;i++){
        int x_c=0,y_c=0;
        for(int j=i;j<n;j++){
            if(a[j]==x){
                x_c++;
            }
            if(a[j]==y){
                y_c++;
            }
            if(x_c==y_c){
                result++;
            }
        }
    }
    return result;
}

int main(){
    int n,q;
    cin >>n >>q;
    int a[n];
    for(int i=0;i<n;i++){
        cin >>a[i];
    }
    while(q--){
        int x,y;
        cin >>x >>y;
        cout <<get_total(a,x,y,n)<<"\n";
    }
}

对于每个查询，它都在n^2中运行。最大数组大小为8*10^3，最大查询数为10^5

Answer 1

创建辅助数组x_y_diffs，其实质是：

#(times_x_appeared_thus_far) - #(times_y_appeared_thus_far)

并且可以计算为：

x_y_diffs[0] = 0
x_y_diffs[i] = x_y_diffs[i-1] + 1         if array[i-1] == x
               x_y_diffs[i-1] - 1         if array[i-1] == y
               x_y_diffs[i-1]             otherwise

很容易看出它可以在线性时间内计算出来。

std::map<int, int> histogram;
int count = 0;
for (int x : x_y_diffs) {
  count += histogram[x];
  histogram[x] = histogram[x] + 1;
}