您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

Codeforces 86D Powerful Array 莫隊算法區間頻次平方和

編輯：關於C++

問題

數組長度 n≤200,000，查詢 Q≤200,000。每查詢 [l,r] 求 Σ cnt[x]² * x，其中 cnt[x] 為 x 在區間內出現次數。

莫隊算法核心思想

將查詢按塊分組：block = l / B，B = √n
塊內按 r 升序，塊間按 block 升序
維護當前區間 [L,R] 和答案，移動邊界時 O(1) 更新

添加/移除元素的增量更新

當元素 x 加入區間：

ans -= 1LL * cnt[x] * cnt[x] * x;
cnt[x]++;
ans += 1LL * cnt[x] * cnt[x] * x;

移除時反向操作（先減後加）。

完整代碼框架

struct Query { int l, r, id, block; };
bool cmp(Query a, Query b) {
    if (a.block != b.block) return a.block < b.block;
    return (a.block & 1) ? a.r > b.r : a.r < b.r; // 奇偶塊優化
}

int cnt[MAXA];
long long ans, curAns;
int L=1, R=0;

void add(int pos) {
    int x = a[pos];
    curAns -= 1LL * cnt[x] * cnt[x] * x;
    cnt[x]++;
    curAns += 1LL * cnt[x] * cnt[x] * x;
}
void remove(int pos) {
    int x = a[pos];
    curAns -= 1LL * cnt[x] * cnt[x] * x;
    cnt[x]--;
    curAns += 1LL * cnt[x] * cnt[x] * x;
}

int main() {
    // 讀入、分塊、排序查詢
    for (auto& q : queries) {
        while (L > q.l) add(--L);
        while (R < q.r) add(++R);
        while (L < q.l) remove(L++);
        while (R > q.r) remove(R--);
        ans[q.id] = curAns;
    }
    // 輸出答案
}