http://acm.hdu.edu.cn/showproblem.php?pid=4638

首先离线,按 r 从小往大排序。

由不等式 可知,集合的个数越少越好。那么这道题的关键就在于如何「合并」集合。

为了说明的方便,举个例子:

设 ID 数组为 1,3,2,5,4,我们从左往右遍历,每读到一个数,树状数组当前位置就 +1,表示新增一个集合。

然后试着合并,看当前位置 i 前面有没有 a[i]-1 和 a[i]+1,有的话树状数组 pos[a[i]-1] 和 pos[a[i]+1] 就 -1,表示合并集合。

注意,遍历到最后一个数 4 的时候,我们把 3 和 5 所在位置各 -1(合并集合),但是先前遍历 2 的时候已经把 3 所在位置 -1 了,这对结果是没有影响的,因为查询的时候,3 会与 2 相互抵消。

(只贴出与题目有关的代码,宏定义见 GitHub

/* 515 ms, 2980 KB */
const int mx = 1e5 + 5;

struct Query {
    int l, r, id;
    bool operator < (const Query &b) const {
        return r < b.r;
    }
} q[mx];

int n;
int tree[mx];
void U(int pos, int val = 1) {for (; pos <= n; pos += pos & -pos) tree[pos] += val;}
int sum(int pos) {int ans = 0; for (; pos > 0; pos &= pos - 1) ans += tree[pos]; return ans;}
int Q(int l, int r) {return sum(r) - sum(l - 1);}

int a[mx], pos[mx], ans[mx];

int main() {
    int m, i, cnt;
    TT {
        SII(n, m);
        Forr(i, 1, n + 1) SI(a[i]), pos[a[i]] = i;
        For(i, m) {
            SII(q[i].l, q[i].r), q[i].id = i;
        }
        sort(q, q + m);
        mem(tree, 0), cnt = 0;
        Forr(i, 1, n + 1) {
            U(i);
            if (a[i] > 1 && pos[a[i] - 1] < i) U(pos[a[i] - 1], -1);
            if (a[i] < n && pos[a[i] + 1] < i) U(pos[a[i] + 1], -1);
            for (cnt < m && q[cnt].r == i; ++cnt;) ans[q[cnt].id] = Q(q[cnt].l, q[cnt].r);
        }
        PAn(ans, m);
    }
    return 0;
}

Comments

comments powered by Disqus