P2671 [NOIP2015 初級者部門] 和の計算

この問題では、xとzの色が同じで偶奇が一致する条件を満たす要素の組み合わせで和を計算する必要がある。単純なO(n²)の解法では時間制限に間に合わないため、色と偶奇で分類する方法を採用。

色ごとに偶数・奇数グループを分けて集計し、各グループ内で次の式を適用：

実装例：

#include <bits/stdc++.h>
using namespace std;
const int MOD = 10007;

int n, m;
int value[100005];
int color[100005];
int countMap[100005][2];
long long sumMap[100005][2];

int main() {
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> value[i];
    for(int i=1; i<=n; i++) {
        cin >> color[i];
        countMap[color[i]][i%2]++;
        sumMap[color[i]][i%2] = (sumMap[color[i]][i%2] + value[i]) % MOD;
    }
    long long result = 0;
    for(int i=1; i<=n; i++) {
        int groupSize = countMap[color[i]][i%2];
        long long term1 = (i * (groupSize - 1) % MOD) * value[i] % MOD;
        long long term2 = (i % MOD) * sumMap[color[i]][i%2] % MOD;
        result = (result + term1 + term2) % MOD;
    }
    cout << result;
    return 0;
}

P2880 [USACO07JAN] バランス取れた行列 G

区間の最大値・最小値の差を求める典型的な問題。セグメントツリーの実装例：

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 50005;
int data[MAX_N];
int maxTree[MAX_N*4], minTree[MAX_N*4];

void build(int node, int left, int right) {
    if(left == right) {
        maxTree[node] = minTree[node] = data[left];
        return;
    }
    int mid = (left + right)/2;
    build(node*2, left, mid);
    build(node*2+1, mid+1, right);
    maxTree[node] = max(maxTree[node*2], maxTree[node*2+1]);
    minTree[node] = min(minTree[node*2], minTree[node*2+1]);
}

int queryMax(int node, int left, int right, int qL, int qR) {
    if(qR < left || right < qL) return INT_MIN;
    if(qL <= left && right <= qR) return maxTree[node];
    int mid = (left + right)/2;
    return max(queryMax(node*2, left, mid, qL, qR),
              queryMax(node*2+1, mid+1, right, qL, qR));
}

int queryMin(int node, int left, int right, int qL, int qR) {
    if(qR < left || right < qL) return INT_MAX;
    if(qL <= left && right <= qR) return minTree[node];
    int mid = (left + right)/2;
    return min(queryMin(node*2, left, mid, qL, qR),
              queryMin(node*2+1, mid+1, right, qL, qR));
}

int main() {
    int n, q;
    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> data[i];
    build(1, 1, n);
    while(q--) {
        int l, r;
        cin >> l >> r;
        int maxVal = queryMax(1, 1, n, l, r);
        int minVal = queryMin(1, 1, n, l, r);
        cout << (maxVal - minVal) << endl;
    }
    return 0;
}