累積和配列を $P_i = \displaystyle \sum_{1 \leq j \leq i} A_j \quad (P_0 = 0)$ としたとき、 $P_{x-1}$ までは値が変化しないのは当然として、 $P_x + P_{x+1}$ の値が不変なことから、 $P_{x+1}$ 以降も値が変化しないことがわかる。

よって、 $A_x$ と $A_{x+1}$ をswapした後、

$P_x \leftarrow P_{x-1} + A_{x}$

と更新すればよい。

上位のデータ構造で殴る

慣れている人は、このクエリの形式を見た時点で、とあるデータ構造が思い浮かぶかもしれない。

クエリ1では「区間の1点更新を2回行う」、クエリ2では「任意の区間和を求める」という操作を行っている。

このような操作を高速に行うデータ構造として、Segment Tree や BIT(Fenwick Tree) があるので、これらを用いることで簡単に実装することができる。

実装例

考察1

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.using ll = long long;
7. 
8.// ======================================== //
9. 
10.int main()
11.{
12.    int N, Q;
13.    cin >> N >> Q;
14.    vector<int> A(N);
15.    rep(i, 0, N) cin >> A[i];
16. 
17.    vector<ll> ps(N + 1, 0);
18.    rep(i, 0, N) ps[i + 1] = ps[i] + A[i];
19. 
20.    while (Q--)
21.    {
22.        int t;
23.        cin >> t;
24. 
25.        if (t == 1)
26.        {
27.            int x;
28.            cin >> x;
29.            x--;
30. 
31.            swap(A[x], A[x + 1]);
32.            ps[x + 1] = ps[x] + A[x];
33.        }
34.        else
35.        {
36.            int l, r;
37.            cin >> l >> r;
38.            l--;
39. 
40.            cout << ps[r] - ps[l] << endl;
41.        }
42.    }
43. 
44.    return 0;
45.}

Submission #72769528 - JPRS Programming Contest 2026#1 (AtCoder Beginner Contest 442)

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

考察2

実装例ではACLのSegtreeを用いている。

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#if __has_include(<atcoder/all>)
5.#include <atcoder/all>
6.using namespace atcoder;
7.#endif
8. 
9.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
10. 
11.using ll = long long;
12. 
13.// ======================================== //
14. 
15.ll op(ll a, ll b)
16.{
17.    return a + b;
18.}
19. 
20.ll e()
21.{
22.    return 0LL;
23.}
24. 
25.int main()
26.{
27.    int N, Q;
28.    cin >> N >> Q;
29.    vector<ll> A(N);
30.    rep(i, 0, N) cin >> A[i];
31. 
32.    segtree<ll, op, e> seg(A);
33. 
34.    while (Q--)
35.    {
36.        int t;
37.        cin >> t;
38. 
39.        if (t == 1)
40.        {
41.            int x;
42.            cin >> x;
43.            x--;
44. 
45.            ll a = seg.get(x);
46.            ll b = seg.get(x + 1);
47.            seg.set(x, b);
48.            seg.set(x + 1, a);
49.        }
50.        else if (t == 2)
51.        {
52.            int l, r;
53.            cin >> l >> r;
54. 
55.            cout << seg.prod(l - 1, r) << endl;
56.        }
57.    }
58. 
59.    return 0;
60.}