AcWing 1236. インクリメント三元グループの問題解(二分+二重ポインタ+接頭辞和)

AcWing 1236. 増分三元グループ

タイトル説明

テーマ分析

二分

デュアルポインタ

接頭辞および

運転時間

原題リンク:AcWing 1236.三元组を増やす
タイトルの説明
3つの整数配列を指定
A=[A1,A2,…AN], B=[B1,B2,…BN], C=[C1,C2,…CN],
どのくらいの三元グループ(i,j,k)が満足しているかを統計してください.
1≦i,j,k≦N Aijk入力フォーマットの最初の行は整数Nを含む.
2行目はN個の整数A 1,A 2,…ANを含む.
3行目は、N個の整数B 1,B 2,...BNを含む.
4行目はN個の整数C 1,C 2,…CNを含む.
出力フォーマットの整数は答えを表します.
データ範囲1≦N≦105,0≦Ai,Bi,Ci≦105入力サンプル:

3
1 1 1
2 2 2
3 3 3

出力サンプル:

27

テーマ分析
まず暴力のやり方を考えて、3つの配列のネストの列挙、O(n 3)の時間の複雑さ、n≦105は必ずタイムアウトします.
本題を列挙の順序で最適化することを試み,まずB配列を列挙し,AではB[i]より小さい数の個数cnt 1を探索し,CではB[i]より大きい数の個数cnt 2を探索し,B[i]を持つ合法的な選択数がcnt 1*cnt 2である.
暴力で時間の合計を検索する時間の複雑さはO(n 2)であり,やはりタイムアウトする.
にぶん
ルックアップである以上,二分ルックアップを考慮することができ,ルックアップ前に3つの配列をソート前に処理し,ソート時間複雑度O(nlog 2 n),列挙Bのすべての要素+ルックアップA,Cにおける要素時間複雑度もO(nlog 2 n),総時間複雑度をO(nlog 2 n)に下げることができる.

#include 
#include 
#include 
using namespace std;

typedef long long LL;
const int N = 1e5+10;
int num[3][N];

int main() {
     
    int n;
    scanf("%d", &n);
    for(int i = 0; i < 3; ++i) 
        for(int j = 1; j <= n; ++j) 
            scanf("%d", &num[i][j]);
    for(int i = 0; i < 3; ++i)
        sort(num[i]+1, num[i]+n+1);
        
    LL ans = 0;
    //  B，  A       C       
    for(int i = 1; i <= n; ++i) {
     
        int key = num[1][i];
        //A          key     
        int pos1 = lower_bound(num[0]+1, num[0]+n+1, key)-num[0]-1;
        //C          key     
        int pos2 = upper_bound(num[2]+1, num[2]+n+1, key)-num[2];
        if(pos1 >= 1 && pos2 <= n) {
     
            ans += (LL)pos1*(n-pos2+1);
        }
    }
    cout<<ans<<endl;
    return 0;
}

ダブルポインタ
さらに検索を最適化し,配列された配列AとBについて,Aの中でB[i]未満の要素を探す個数は,ポインタごとに最大n回移動するため,検索時間の複雑度がO(n)に低下し,検索Cは検索Aと同じであり,最初のBより大きい位置を探すだけである2ポインタアルゴリズムを考慮できる.上記の二分プログラムの

//  
for(int i = 1; i <= n; ++i) {
     
	int key = num[1][i];
	//A          key     
	int pos1 = lower_bound(num[0]+1, num[0]+n+1, key)-num[0]-1;
	//C          key     
	int pos2 = upper_bound(num[2]+1, num[2]+n+1, key)-num[2];
	if(pos1 >= 1 && pos2 <= n) {
     
	    ans += (LL)pos1*(n-pos2+1);
	}
}

に変更

//   
int a = 1, c = 1;
for(int i = 1; i <= n; ++i) {
     
    int key = num[1][i];
    while(a<=n && num[0][a] < key) a++;
    while(c<=n && num[2][c] <= key) c++;
    
    ans += (LL)(a-1)*(n-c+1);
}

完全なダブルポインタプログラムは次のとおりです.

#include 
#include 
#include 
using namespace std;

typedef long long LL;
const int N = 1e5+10;
int num[3][N];

int main() {
     
    int n;
    scanf("%d", &n);
    for(int i = 0; i < 3; ++i) 
        for(int j = 1; j <= n; ++j) 
            scanf("%d", &num[i][j]);
    for(int i = 0; i < 3; ++i)
        sort(num[i]+1, num[i]+n+1);
        
    LL ans = 0;
    //  B，  A       C       
    int a = 1, c = 1;
    for(int i = 1; i <= n; ++i) {
     
        int key = num[1][i];
        while(a<=n && num[0][a] < key) a++;
        while(c<=n && num[2][c] <= key) c++;
        
        ans += (LL)(a-1)*(n-c+1);
        
    }
    cout<<ans<<endl;
    return 0;
}

接頭辞和
従来の二重ポインタアルゴリズムの時間的複雑さのボトルネックは,ソートO(nlog 2 n)がO(n)の時間内にこの問題をソートしなくてもよいかどうかを考慮することであった.
迅速なルックアップAのB[i]より小さい数の個数をソートする以上、配列Aのすべての要素が現れる回数をハッシュテーブルに格納することができます.配列中の要素の範囲はn 5しかないので、大きな配列cntaをハッシュテーブルとして開くことができます.
Bの要素を列挙する場合、B[i]より小さいすべての要素の総数をすばやく検索する必要があります.列挙する前に、テーブルの各数の接頭辞和を求めるだけです.
Cを検索することはAを検索することと同じである.
C++コード実装

//   
#include 
#include 

using namespace std;

typedef long long LL;
const int N = 1e5+10;
int A[N], B[N], C[N];
int cnta[N], cntc[N], sa[N], sc[N];

int main() {
     
    int n;
    scanf("%d", &n);
    //   i A  cntc[i] ，  cnt    sa
    for(int i = 1; i <= n; ++i) {
     
        scanf("%d", &A[i]);
        cnta[A[i]]++;
    }
    sa[0] = cnta[0];
    for(int i = 1; i < N; ++i) sa[i] = sa[i-1]+cnta[i];
    //B     
    for(int i = 1; i <= n; ++i) scanf("%d", &B[i]);
    
    //   i C  cntc[i] ，  cnt    sc
    for(int i = 1; i <= n; ++i) {
     
        scanf("%d", &C[i]);
        cntc[C[i]]++;
    }
    sc[0] = cntc[0];
    for(int i = 1; i < N; ++i) sc[i] = sc[i-1]+cntc[i]; 

    //  B  
    LL ans = 0;
    for(int i = 1; i <= n; ++i) {
     
        int b = B[i];
        //cout<
        ans += (LL)sa[b-1]*(sc[N-1]-sc[b]);
    }
    cout<<ans<<endl;
    return 0;
}

じっこうじかん
二分:725 msデュアルポインタ:454 ms接頭辞および:179 ms