实用数据结构(二)

这篇博文主要介绍一下fenwick树状数组
线段树

树状数组

fenwick01
fenwick02
fenwick03

把待求的前缀和

1	exist[1] + exist[2] + ... + exist[n]

用fenwick树封装
fenwick成员函数中, $x$ 表示 $\text{exist}$ 的下标

const int maxn = 200000 + 10;

inline int lowbit(int x) {
    return x & (-x);
}

int cnt1[maxn], cnt2[maxn];
int A[maxn];

void init() {
    Set(cnt1, 0);
    Set(cnt2, 0);
}

class Fenwick {
public:
    vector<int> exist;
    int n;

    void clear() {
        fill(exist.begin(), exist.end(), 0);
    }

    void resize(int n) {
        this->n = n;
        exist.resize(n);
    }

    int sum(int x) {
        int ret = 0;
        while (x > 0) {
            ret += exist[x];
            x -= lowbit(x);
        }
        return ret;
    }

    void add(int x, int d) {
        while (x <= n) {
            exist[x] += d;
            x += lowbit(x);
        }
    }
};

Fenwick fwick;

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);

    while (T--) {
        init();
        int maxa = 0;
        int n;
        scanf("%d", &n);
        _rep(i, 1, n) {
            scanf("%d", &A[i]);
            maxa = max(maxa, A[i]);
        }

        fwick.resize(maxa);
        fwick.clear();

        _rep(i, 1, n) {
            int val = A[i];
            fwick.add(val, 1);
            cnt1[i] = fwick.sum(val - 1);
        }

        fwick.clear();
        _forDown(i, n, 1) {
            int val = A[i];
            fwick.add(val, 1);
            cnt2[i] = fwick.sum(val - 1);
            //debug(cnt2[i]);
        }

        llong ans = 0;
        _rep(i, 1, n) {
            ans += ((llong)cnt2[i] * (llong)(i - 1 - cnt1[i]) + (llong)cnt1[i] * (llong)(n - i - cnt2[i]));
        }
        printf("%lld\n", ans);
    }
}

树状数组求解区间问题(一)

CH242
CH248

const int maxm = 100000 + 10;
const int maxn = 100000 + 10;
int n, m;

llong A[maxn];

void init() {
    Set(A, 0);
}

class Fenwick {
public:
    int n;
    vector<int> h;

    void resize(int n) {
        this->n = n;
        h.resize(n);
    }

    void clear() {
        fill(h.begin(), h.end(), 0);
    }

    int sum(int x) {
        int ret = 0;
        while (x) {
            ret += h[x];
            x -= lowbit(x);
        }
        return ret;
    }

    void add(int x, int d) {
        while (x <= n) {
            h[x] += d;
            x += lowbit(x);
        }
    }
};

Fenwick fwick;

int main() {
    freopen("input.txt", "r", stdin);
    init();
    cin >> n >> m;

    _rep(i, 1, n) cin >> A[i];
    //debug(A[n]);

    //fflush(stdin);
    fwick.clear();
    fwick.resize(maxn);

    //getchar();
    _for(i, 0, m) {
        char ch;
        cin >> ch;
        //debug(ch);
        if(ch == 'C') {
            //
            int l, r, d;
            cin >> l >> r >> d;
            //debug(l);

            fwick.add(l, d);
            fwick.add(r + 1, -d);
        }
        else {
            //
            int x;
            cin >> x;
            cout << A[x] + (llong)fwick.sum(x) << endl;
        }
    }
}

树状数组求解区间问题(二)

POJ3468

POJ3468

const int maxn = 100000 + 10;
int n, m;
int A[maxn];
llong sum[maxn];

void init() {
    Set(A, 0);
    Set(sum, 0);
}

class Fwick {
public:
    llong C[2][maxn];
    int n;

    void clear() {
        memset(C, 0, sizeof(C));
    }

    void resize(int n) {
        this->n = n;
    }

    llong ask(int k, int x) {
        llong ret = 0;
        while (x) {
            ret += C[k][x];
            x -= lowbit(x);
        }
        return ret;
    }

    void add(int k, int x, int d) {
        while (x <= n) {
            C[k][x] += d;
            x += lowbit(x);
        }
    }
};

Fwick fwick;

int main() {
    freopen("input.txt", "r", stdin);
    init();

    scanf("%d%d", &n, &m);
    _rep(i, 1, n) {
        scanf("%d", &A[i]);
        sum[i] = sum[i - 1] + A[i];
    }

    fwick.clear();
    fwick.resize(n);

    _for(i, 0, m) {
        char op[2];
        scanf("%s", op);

        if(op[0] == 'C') {
            //
            int l, r, d;
            scanf("%d%d%d", &l, &r, &d);

            fwick.add(0, l, d);
            fwick.add(0, r + 1, -d);

            fwick.add(1, l, l * d);
            fwick.add(1, r + 1, -(r + 1) * d);
        }
        else {
            //
            int l, r;
            scanf("%d%d", &l, &r);
            llong ans = sum[r] + (r + 1) * fwick.ask(0, r) - fwick.ask(1, r);
            ans -= (sum[l - 1] + l * fwick.ask(0, l - 1) - fwick.ask(1, l - 1));
            printf("%lld\n", ans);
        }
    }
}

树状数组解决区间第k大数问题

树状数组+二分
POJ2182
POJ2182

#define lowbit(i) (i & (-i))

const int maxn = 100000 + 10;
int A[maxn], n, ANS[maxn];

void init() {
    Set(A, 0);
    Set(ANS, 0);
}

class Fwick {
public:
    vector<int> C;
    int n;

    void resize(int n) {
        this->n = n;
        C.resize(n);
    }

    void clear() {
        fill(C.begin(), C.end(), 0);
    }

    int sum(int x) {
        int ret = 0;
        while (x) {
            ret += C[x];
            x -= lowbit(x);
        }
        return ret;
    }

    void add(int x, int d) {
        while (x <= n) {
            C[x] += d;
            x += lowbit(x);
        }
    }

    int find(int l, int r, int val) {
        while (l < r) {
            int mid = (l + r) >> 1;
            if(sum(mid) < val) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};

Fwick fwick;

int main() {
    freopen("input.txt", "r", stdin);
    init();

    scanf("%d", &n);

    fwick.resize(n);
    fwick.clear();

    fwick.add(1, 1);
    _rep(i, 2, n) {
        scanf("%d", &A[i]);
        fwick.add(i, 1);
    }

    _forDown(i, n, 1) {
        int val = A[i] + 1;
        int p = fwick.find(1, n, val);
        ANS[i] = p;
        fwick.add(p, -1);
    }

    _rep(i, 1, n) cout << ANS[i] << endl;
}

POJ2828

const int maxn = 200000 + 10;
int n;

class Peo {
public:
    int p, v;
};

Peo peo[maxn];
int ans[maxn];

void init() {
    Set(ans, 0);
}

class Fwick {
public:
    vector<int> C;
    int n;

    void resize(int n) {
        this->n = n;
        C.resize(n);
    }

    void clear() {
        fill(C.begin(), C.end(), 0);
    }

    int sum(int x) {
        int ret = 0;
        while (x) {
            ret += C[x];
            x -= lowbit(x);
        }
        return ret;
    }

    void add(int x, int d) {
        while (x <= n) {
            C[x] += d;
            x += lowbit(x);
        }
    }

    int find(int l, int r, int val) {
        while (l < r) {
            int mid = (l + r) >> 1;
            if(sum(mid) < val) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};

Fwick fwick;


int main() {
    freopen("input.txt", "r", stdin);
    while (~scanf("%d", &n)) {
        //debug(n);
        init();
        fwick.resize(n);
        fwick.clear();

        _rep(i, 1, n) {
            //debug(i);
            scanf("%d%d", &peo[i].p, &peo[i].v);
            //debug(peo[i].p);
            //debug(peo[i].v);
            fwick.add(i, 1);
        }

        _forDown(i, n, 1) {
            int val = peo[i].p;
            int pos = fwick.find(1, n, val + 1);
            //debug(pos);

            ans[pos] = peo[i].v;
            fwick.add(pos, -1);

            //debug(peo[i].v);
        }
        _rep(i, 1, n) {
            if(i != n) printf("%d ", ans[i]);
            else printf("%d\n", ans[i]);
        }
    }
}

树状数组处理栈(扩展域)

LA5902

LA5902

#define lowbit(i) (i & (-i))

const int maxn = 100000 + 10;
int n, m;
int pos[maxn];

void init() {
    Set(pos, 0);
}


class Fwick {
public:
    vector<int> C;
    int n;

    void resize(int n) {
        C.resize(n + 1);
        this->n = n;
    }

    void clear() {
        fill(C.begin(), C.end(), 0);
    }

    int sum(int x) {
        int ret = 0;
        while (x) {
            ret += C[x];
            x -= lowbit(x);
        }
        return ret;
    }

    void add(int x, int d) {
        while (x <= n) {
            C[x] += d;
            x += lowbit(x);
        }
    }
};

Fwick fwick;

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);

    while (T--) {
        //init();

        scanf("%d%d", &n, &m);

        fwick.resize((maxn + 1) * 2);
        fwick.clear();

        int st = maxn;

        _rep(i, 1, n) {
            pos[i] = st + i;
            fwick.add(pos[i], 1);
        }

        _for(i, 0, m) {
            int x;
            scanf("%d", &x);
            printf("%d%c", fwick.sum(pos[x] - 1), i == m - 1 ? '\n' : ' ');

            fwick.add(pos[x], -1);
            pos[x] = st--;
            fwick.add(pos[x], 1);
        }
    }
}

树状数组和康托尔排列

UVA11525
P11525

const int maxn = 50000 + 10;
int n;

class Fwick {
public:
    vector<int> C;
    int n;

    void resize(int n) {
        this->n = n;
        C.resize(n + 1);
    }

    void clear() {
        fill(C.begin(), C.end(), 0);
    }

    int sum(int x) {
        int ret = 0;
        while (x) {
            ret += C[x];
            x -= lowbit(x);
        }
        return ret;
    }

    void add(int x, int d) {
        while (x <= n) {
            C[x] += d;
            x += lowbit(x);;
        }
    }

    int find(int l, int r, int val) {
        while (l < r) {
            int mid = (l + r) >> 1;
            if(sum(mid) < val) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};

Fwick fwick;

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);

    while (T--) {
        scanf("%d", &n);
        fwick.resize(n);
        fwick.clear();

        _rep(i, 1, n) fwick.add(i, 1);

        _rep(i, 1, n) {
            int x;
            scanf("%d", &x);

            int pos = fwick.find(1, n, x + 1);
            printf("%d%c", pos, i == n ? '\n' : ' ');

            fwick.add(pos, -1);
        }
    }
}

并查集练习

并查集和坐标离散化

BZOJ4195

const int maxn = 100000 + 10;

class Con {
public:
    int i, j;
    int e;
};

Con cons[maxn];
int n;

int pa[maxn * 2];
int arr[maxn * 2];

void init() {
    _for(i, 0, maxn) pa[i] = i;
    Set(arr, 0);
}

int find(int x) {
    return x == pa[x] ? x : (pa[x] = find(pa[x]));
}

void discrete(int* arr, int m, int& n) {
    sort(arr, arr + m);
    n = unique(arr, arr + m) - arr;
}

int query(int* arr, int n, int x) {
    return lower_bound(arr, arr + n, x) - arr;
}

void solve() {
    int m = n * 2;
    int n2 = 0;
    discrete(arr, m, n2);

    _rep(i, 0, n2) pa[i] = i;

    _for(i, 0, n) {
        int p = find(query(arr, n2, cons[i].i)), q = find(query(arr, n2, cons[i].j));
        if(cons[i].e) pa[p] = q;
    }

    _for(i, 0, n) {
        int p = find(query(arr, n2, cons[i].i)), q = find(query(arr, n2, cons[i].j));
        if(!cons[i].e && p == q) {
            printf("NO\n");
            return;
        }
    }
    printf("YES\n");
}

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);

    while (T--) {
        init();

        scanf("%d", &n);
        _for(i, 0, n) {
            scanf("%d%d%d", &cons[i].i, &cons[i].j, &cons[i].e);

            arr[i * 2] = cons[i].i;
            arr[i * 2 + 1] = cons[i].j;
        }

        // then solve the problem
        solve();

    }
}

并查集+贪心

POJ1456

POJ1456

const int maxn = 10000 + 10;
int pa[maxn];
int n;

void initPa(int n) {
    _rep(i, 0, n) pa[i] = i;
}

int find(int x) {
    return x == pa[x] ? x : (pa[x] = find(pa[x]));
}

class Stuf {
public:
    int prof, day;
    bool operator< (const Stuf& rhs) const {
        return prof > rhs.prof;
    }
};

Stuf stufs[maxn];

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d", &n) != EOF) {

        int maxd = 0;
        _for(i, 0, n) {
            scanf("%d%d", &stufs[i].prof, &stufs[i].day);
            maxd = max(maxd, stufs[i].day);
        }

        sort(stufs, stufs + n);

        initPa(maxd);
        int ans = 0;
        _for(i, 0, n) {
            int d = find(stufs[i].day);
            if(d) {
                ans += stufs[i].prof;
                pa[d] = d - 1;
            }
        }

        printf("%d\n", ans);
    }
}

并查集按秩压缩

并查集执行

1	Union(int rootp, int rootq)

操作之后

1
2
3

pa[rootp] = rootq
rootp及其后代元素都成为rootq的子节点
这个时候sz[rootq] += sz[rootp]

另外

1	std::ios::sync_with_stdio(false);

比scanf好用

CH4101

const int maxn = 30000 + 1;
int pa[maxn];
int d[maxn];
int sz[maxn];

void init() {
    _for(i, 0, maxn) sz[i] = 1;
    _for(i, 0, maxn) d[i] = 0;
}

void initPa(int n) {
    _rep(i, 0, n) pa[i] = i;
}

int find(int x) {
    if(x == pa[x]) return x;
    int root = find(pa[x]);
    d[x] += d[pa[x]];
    return pa[x] = root;
}

void Union(int p, int q) {
    pa[p] = q;
    d[p] = sz[q];
    sz[q] += sz[p];
}

int main() {
    std::ios::sync_with_stdio(false);
    freopen("input.txt", "r", stdin);
    int T;
    cin >> T;

    initPa(maxn);
    init();
    while (T--) {
        char cmd;
        cin >> cmd;

        int i, j;
        cin >> i >> j;
        //debug(i);
        //debug(j);

        int p = find(i), q = find(j);
        //debug(p);
        //debug(q);

        if(cmd == 'C') {
            //
            if(p == q) cout << abs(d[i] - d[j]) - 1 << endl;
            else cout << "-1" << endl;
        }
        else {
            //
            Union(p, q);
        }
    }
}

并查集处理奇偶运算

POJ1733
POJ1733

const int maxn = 10000 + 10;

struct Query {
    int l, r, ans;
};
Query query[maxn];

void discrete(int* arr, int n, int& n2) {
    sort(arr + 1, arr + 1 + n);
    n2 = unique(arr + 1, arr + 1 + n) - arr - 1;
}

int getid(int* arr, int n2, int x) {
    return lower_bound(arr + 1, arr + 1 + n2, x) - arr;
}

int arr[maxn], n, m;
int pa[maxn], d[maxn];

void init() {
    Set(arr, 0);
}

void initPa(int n) {
    _rep(i, 0, n) pa[i] = i;
    _rep(i, 0, n) d[i] = 0;
}

int find(int x) {
    if(x == pa[x]) return x;
    int root = find(pa[x]);

    d[x] ^= d[pa[x]];
    return pa[x] = root;
}


int main() {
    freopen("input.txt", "r", stdin);
    std::ios::sync_with_stdio(false);

    cin >> n >> m;

    int k = 0;
    _rep(i, 1, m) {
        char str[5];
        cin >> query[i].l >> query[i].r;

        scanf("%s", str);
        if(str[0] == 'o') query[i].ans = 1;
        else query[i].ans = 0;

        arr[++k] = query[i].l - 1;
        arr[++k] = query[i].r;
    }
    discrete(arr, k, n);
    //debug(n);
    // [0, m - 1] is all query

    initPa(n);
    _rep(i, 1, m) {
        int x = getid(arr, n, query[i].l - 1);
        int y = getid(arr, n, query[i].r);
        int p = find(x), q = find(y);

        if(p == q) {
            //
            if( (d[x] ^ d[y]) != query[i].ans ) {
                cout << i - 1 << endl;
                return 0;
            }
        }
        else {
            pa[p] = q;
            d[p] = d[x] ^ d[y] ^ query[i].ans;
        }
    }
    cout << m << endl;
    return 0;
}

并查集扩展域

POJ1733-02

const int maxn = (10000 + 1) * 2;

struct Query {
    int l, r, ans;
};
Query query[maxn];

void discrete(int* arr, int n, int& n2) {
    sort(arr + 1, arr + 1 + n);
    n2 = unique(arr + 1, arr + 1 + n) - arr - 1;
}

int getid(int* arr, int n2, int x) {
    return lower_bound(arr + 1, arr + 1 + n2, x) - arr;
}

int arr[maxn], n, m;
int pa[maxn];

void init() {
    Set(arr, 0);
}

void initPa(int n) {
    _rep(i, 0, n) pa[i] = i;
}

int find(int x) {
    return x == pa[x] ? x : find(pa[x]);
}



int main() {
    freopen("input.txt", "r", stdin);
    cin >> n >> m;

    int k = 0;
    _rep(i, 1, m) {
        char str[5];
        cin >> query[i].l >> query[i].r;
        scanf("%s", str);

        if(str[0] == 'o') query[i].ans = 1;
        else query[i].ans = 0;

        arr[++k] = query[i].l - 1;
        arr[++k] = query[i].r;
    }
    discrete(arr, k, n);

    initPa(n * 2);

    _rep(i, 1, m) {
        int x = getid(arr, n, query[i].l - 1);
        int y = getid(arr, n, query[i].r);

        int xodd = x, xeven = x + n;
        int yodd = y, yeven = y + n;

        if(query[i].ans == 0) {
            if(find(xodd) == find(yeven)) {
                cout << i - 1 << endl;
                return 0;
            }
            pa[find(xodd)] = find(yodd);
            pa[find(xeven)] = find(yeven);
        }
        else {
            if(find(xodd) == find(yodd)) {
                cout << i - 1 << endl;
                return 0;
            }
            pa[find(xodd)] = find(yeven);
            pa[find(xeven)] = find(yodd);
        }
    }
    cout << m << endl;
}

扩展域多节点

POJ1182

const int maxn = 50000 + 10;

int pa[maxn * 3];
int n, k;

// usage: initPa(n * 3)
void initPa(int n) {
    _rep(i, 0, n) pa[i] = i;
}

int find(int x) {
    return x == pa[x] ? x : pa[x] = find(pa[x]);
}

// x: self   x + n: eat   x + 2n: enemy

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &k);

    initPa(n * 3);
    int ans = 0;

    _for(i, 0, k) {
        int cmd, x, y;
        scanf("%d%d%d", &cmd, &x, &y);

        if(cmd == 2 && (x == y)) {
            ans++;
            continue;
        }

        if(x > n || y > n) {
            ans++;
            continue;
        }

        if(cmd == 1) {
            //
            if((find(x + n) == find(y)) || (find(x) == find(y + n))) {
                ans++;
                continue;
            }
        }
        if(cmd == 2) {
            //
            if((find(x) == find(y)) || (find(x) == find(y + n))) {
                ans++;
                continue;
            }
        }

        if(cmd == 1) {
            //
            pa[find(x)] = find(y);
            pa[find(x + n)] = find(y + n);
            pa[find(x + n * 2)] = find(y + n * 2);
        }
        else if(cmd == 2) {
            //
            pa[find(x)] = find(y + n * 2);
            pa[find(x + n)] = find(y);
            pa[find(x + n * 2)] = find(y + n);
        }
    }

    cout << ans << endl;
}

并查集删除与扩展域

CH4901

CH4901

const int maxn = 20000 + 10;
const int maxm = 100000 + 10;
int pa[maxn * 2];
int n, m;

void initPa(int n) {
    _rep(i, 0,n) pa[i] = i;
}
// usage initPa(n * 2);

class Cfl {
public:
    int x, y, val;

    bool operator< (const Cfl& rhs) const {
        return val > rhs.val;
    }
};

Cfl cfl[maxm];

int find(int x) {
    return x == pa[x] ? x : pa[x] = find(pa[x]);
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);


    _for(i, 0, m) {
        scanf("%d%d%d", &cfl[i].x, &cfl[i].y, &cfl[i].val);
    }

    initPa(n * 2);

    sort(cfl, cfl + m);

    _for(i, 0, m) {
        Cfl& cur = cfl[i];
        //debug(cur.x);
        if(find(cur.x) == find(cur.y)) {
            printf("%d\n", cur.val);
            return 0;
        }
        pa[find(cur.x)] = find(cur.y + n);
        pa[find(cur.y)] = find(cur.x + n);
    }
    printf("0\n");
    return 0;
}

POJ2912
POJ2912

const int maxn = 500 + 10;
const int maxm = 2000 + 10;

int pa[maxn * 3];

void initPa(int n) {
    _rep(i, 0, n) pa[i] = i;
}
// usage: initPa(n * 3)
// self: x  lower: x + n   greater: x + n * 2

class Expr {
public:
    int x;
    char op;
    int y;
};

Expr expr[maxm];
int n, m;
int line[maxm];

void init() {
    Set(line, 0);
}

int find(int x) {
    return x == pa[x] ? x : pa[x] = find(pa[x]);
}


bool conflict(const Expr& expr) {
    int x = expr.x, y = expr.y;
    char op = expr.op;
    //debug(op);

    if(op == '>') {
        //puts("ok");
        if((find(x) == find(y)) || (find(x) == find(y + n * 2))) return 1;

        pa[find(x + n * 2)] = find(y);
        pa[find(x)] = find(y + n);
        pa[find(x + n)] = find(y + n * 2);
    }

    if(op == '<') {
        //puts("ok");
        if((find(x) == find(y)) || (find(x) == find(y + n))) return 1;

        pa[find(x + n)] = find(y);
        pa[find(x)] = find(y + n * 2);
        pa[find(x + n * 2)] = find(y + n);
    }

    if(op == '=') {
        //puts("ok");
        if((find(x) == find(y + n)) || (find(x + n) == find(y))) return 1;

        pa[find(x)] = find(y);
        pa[find(x + n)] = find(y + n);
        pa[find(x + n * 2)] = find(y + n * 2);
    }

    return 0;
}

void Rochambeau() {
    //
    _for(i, 0, m) scanf("%d%c%d", &expr[i].x, &expr[i].op, &expr[i].y);
    //debug(expr[0].op);

    init();

    int cnt = 0, id = 0;
    _for(i, 0, n) {
        // i is judge
        bool fail = 0;
        _rep(k, 0, n * 3) pa[k] = k;

        _for(j, 0, m) {
            Expr cur = expr[j];

            //debug(cur.x);
            //debug(cur.y);
            if(cur.x != i && cur.y != i && conflict(cur)) {
                fail = 1;
                if(j > line[i]) line[i] = j + 1;
                break;
            }
        }

        if(!fail) {
            id = i;
            cnt++;
        }
    }

    //debug(cnt);
    if(!cnt) puts("Impossible");
    else if(cnt == 1) {
        int ans = 0;
        _for(i, 0, n) if(line[i] > ans) ans = line[i];
        printf("Player %d can be determined to be the judge after %d lines\n", id, ans);
    }
    else puts("Can not determine");
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d%d", &n, &m) != EOF) Rochambeau();
}