HOJ 2430 Counting the algorithms：樹狀數組維護動態排名

問題描述

長度 2N 序列，每個數 1..N 恰好出現兩次。每次操作選一個數，刪除其兩次出現，得分 = 兩位置差。刪除後前面空位自動前移。求最大總分。N ≤ 100000。

貪心 + 樹狀數組

最優策略：從左到右掃描，遇到首次出現的數，直接刪除它與其配對的第二次出現。得分 = 當前兩位置在「剩餘序列」中的距離。用樹狀數組維護「當前位置 → 原始位置」的映射：初始每位置權值 1，刪除時置 0，前綴和即為當前排名。

代碼實現

int a[200005], bit[200005], pos[200005];
bool vis[200005];

int lowbit(int x) { return x & -x; }
void add(int i, int v) { for(;i<=2*n;i+=lowbit(i)) bit[i]+=v; }
int sum(int i) { int r=0; for(;i>0;i-=lowbit(i)) r+=bit[i]; return r; }

int main() {
    int n;
    while (scanf("%d",&n)==1) {
        memset(vis,0,sizeof(vis));
        memset(bit,0,sizeof(bit));
        for (int i=1;i<=2*n;i++) {
            scanf("%d",&a[i]);
            if (!pos[a[i]]) pos[a[i]]=i;
            else pos[a[i]]=i; // 記錄第二次位置
            add(i,1);
        }
        long long ans=0;
        for (int i=1;i<=2*n;i++) {
            if (vis[i]) continue;
            int v=a[i], j=pos[v];
            vis[i]=vis[j]=1;
            ans += sum(j) - sum(i);
            add(i,-1); add(j,-1);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

關鍵點

• 貪心證明：先刪除最左配對不劣於任何策略（交換論證）。
• 樹狀數組維護動態排名，O(log n) 查詢區間元素個數。
• pos 數組記錄第二次出現位置，需在輸入時正確賦值（第二次覆蓋第一次）。

總結

HOJ 2430 結合貪心策略與樹狀數組動態排名，優雅解決「刪除後位置變化」的計分問題。核心洞見：最優策略即順序刪除最左未處理配對，樹狀數組實時維護當前序列中的相對距離。