アルゴリズム-1 D 2 D配列の差分と接頭辞と

*1 D差分
1つのnの長さの歌のリストがあって、ある集まりは1ラウンドごとに歌を聞いてkの所(kを含む)が終わることを聞いて、今m個のkを与えて、mラウンドを聞いたことを表して、1曲ごとに何回聞いたことがあることを聞きます——抽象はxdoj 1276から
構想

暴力シミュレーション解決:サイクルを利用して、各ラウンドのkと前の数を1つ追加し、結果を出力します.--TLE

一次元配列差分:各kの位置を記録し、その後、一次元配列の差分を用いて解き、重複カウントを回避する.

観察する
1.nを4とし,m輪の後に1,2,3,4曲を止める回数をa,b,c,d回とする.逆さまに見ると、最後に出力されるのは4番目:d 1=d 3番目:c 1=c+d 1 2番目:b 1=b+c 1番目:a 1=a+b 1
げんり
言いにくいしかし、3曲目と4曲目の差はc、2曲目と3曲目の差はbと考えることができ、このように、1曲あたりの聴く回数は次の曲を聴く回数に加えて停止する回数となる.多分これが原理か差分名の由来なのでしょう.
c言語実装

#include
#include
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    int list[n];
    memset(list, 0, sizeof(list));
    while(m--)
    {
        int k;
        scanf("%d", &k);
        list[k-1]++;
    }
    for(int i = n-2; i >= 0 ; i--)
    {
        list[i] += list[i+1];
    }
    for(int i = 0; i < n; i++)
    {
        printf("%d
", list[i]);
    }
    return 0;
}

サンプル入力

5 4
5
1
2
3

サンプル出力

4
3
2
1
1

*2 D差分
1つのn*mの歌謡リストがあって、毎回歌を聞いて、ある集まりは1つのノード(i,j)を選んで、このノードの前のすべての歌(u,v),(u<=i,v<=j)はすべて1回(実は左上のあの点とその点を選んで対角線の所在する矩形の内の歌を構成します).各ラウンドのノードを与え、Hラウンドを求めた後、各曲を何回か聞いた.--抽象はxdoj 1378から
構想

暴力シミュレーション-TLE

二次元差分

観察する
数字代表第几首歌应对字母代表听了几次1 2 3——a b c 4 5 6——d e f 7 8 9——g h i第9首:i 1=i第8首:h 1=h+i第7首:g 1=g+h 1第6首:f 1=f+i 1第5首(ここで注意):e 1=e+f+h+i=e+f 1+h 1-i 1......以下省略
げんり
同じ次元の差分ですが右下に2回加算されているので、1回減らします.
注意!
差分時の右下角の数が重複するため、計算時に一度減算すべきである.
c言語実装

#include
int a[1001][1001] = {0};
int main()
{
    int n, m, h;
    scanf("%d%d%d", &n, &m, &h);
    while(h--)//    
    {
        int u, v;
        scanf("%d%d", &u, &v);
        a[u-1][v-1]++;
    }

    for(int i = n-1; i >= 0; i--)//    
    {
        for(int j = n-1; j >= 0; j--)
        {
            a[i][j] += a[i+1][j] + a[i][j+1] - a[i+1][j+1];
        }
    }

    for(int i = 0; i < n; i++)//    
    {
        for(int j = 0; j < m; j++)
        {
            printf("%d
", a[i][j]);
        }
    }
    return 0;
}

サンプル入力

3 3 9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

サンプル出力

9
6
3
6
4
2
3
2
1

締めくくり
差分法は演算量を大幅に減らすことができ、TLEの出現を巧みに回避した.
拡張と思考
1 D 2 D配列で2つのポイントを選択して、この2つのポイント内の曲ごとに聞いた回数を判断できますか?