1

問題文：

https://www.hackerrank.com/contests/epiccode/challenges/square-array

整数 A1、A2、…AN の配列が与えられた場合、配列内で 2 種類のクエリを実行する必要があります。

  • 1×y。Ax に 1×2 を追加し、Ax+1 に 2×3 を追加し、Ax+2 に 3×4 を追加し、Ax+3 に 4×5 を追加します。

  • 2×y。インデックス x からインデックス y までのすべての整数の合計を 109+7 で法を求めて求めます。つまり、(Ax+Ax+1+⋯+Ay)mod(109+7) を求めます。

最初は配列内のすべての値が 0 であると想定できます。

入力フォーマット:

最初の行には、スペースで区切られた 2 つの整数 N と Q が含まれています。N は配列のサイズを表し、Q はクエリの数を表します。

次の各 Q 行には、1 xy または 2 x y の形式のクエリが含まれます。

制約:

1≦x≦y≦N 1≦N≦2×10^5 1≦Q≦2×10^5

出力形式 フォーム 2 xy のクエリごとに、必要な回答を出力します。

Sample Input

10 5
1 1 10
2 2 7
1 4 8
1 5 6
2 6 6

Output:
166 
60

説明：

After the first query, the array is [2,6,12,20,30,42,56,72,90,110]. 
The answer for the second query is 6+12+20+30+42=166. 
After the third query, the array is [2,6,12,22,36,54,76,102,90,110]. 
After the fourth query, the array is [2,6,12,22,38,60,76,102,90,110]. 
The answer for the fifth query is 60.

提出された解決策の1つ:

#include <bits/stdc++.h>
const int N = 2 * 100005;
const long long MOD = 1000000007;
const long long INV = 333333336;

using namespace std;

int n;
int nQuery;

struct BIT {
    int bit[N];
    BIT() {
        memset(bit, 0, sizeof(bit));
    }

    void inc(int i, int v) {
        for (; i < N; i += i & -i) {
            bit[i] += v;
            bit[i] %= MOD;
        }
    }

    void incRange(int i, int j, int v) {
        inc(i, v); inc(j + 1, MOD - v);
    }

    int get(int i) {
        int res = 0;
        for (; i > 0; i -= i & -i)
            res = (res + bit[i]) % MOD;
        return res;
    }
} First, Second, Third, Const;

int sum(long long x, long long y) {
    return ((x + y) % MOD + MOD) % MOD;
}

void update(long long l, long long r) {
    Third.incRange(l, r, 1);
    Second.incRange(l, r, MOD - sum(l - 1, sum(l - 2, l - 3)));
    First.incRange(l, r, sum((l - 1) * (l - 2) % MOD, sum((l - 2) * (l - 3) % MOD, (l - 1) * (l - 3) % MOD)));
    Const.incRange(l, r, sum(MOD - (l - 1) * (l - 2) % MOD * (l - 3) % MOD, MOD));
    Const.incRange(r + 1, n, (r - l + 1) * (r - l + 2) % MOD * (r - l + 3) % MOD);
}

int getSum(long long x) {
    return (x * x % MOD * x % MOD * Third.get(x) % MOD + x * x % MOD * Second.get(x) % MOD + x * First.get(x) % MOD + Const.get(x)) % MOD * INV % MOD;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
#ifdef _LAD_
    freopen("square-array.txt", "r", stdin);
#endif // _LAD_
    cin >> n >> nQuery;
    int x, y, type;
    while (nQuery--) {
        cin >> type >> x >> y;
        if (type == 1) {
            update(x, y);
#ifdef _LAD_
            for (int i = 1; i <= n; ++i)
                cout << ((getSum(i) - getSum(i - 1) + MOD) % MOD) << ' ';
            cout << endl;
#endif // _LAD_
        }
        else
            cout << (getSum(y) - getSum(x - 1) + MOD) % MOD << '\n';
    }
    return 0;
}
4

1 に答える 1

1

http://ayazdzulfikar.blogspot.in/2014/12/penggunaan-fenwick-tree-bit.html?showComment=1434865697025#c5391178275473818224の情報を使用してみてください。

お役に立てば幸いです。

于 2015-06-22T09:46:43.283 に答える