題目傳送門 poj1990
題意: 農(nóng)夫的N (N∈[1, 20,000])頭牛參加了"MooFest"之后有了不同程度的耳聾, 現(xiàn)在它們排在一條直線上,每頭牛有2個(gè)屬性值: 耳聾值v[i] (v[i] ∈[1, 20,000])和坐標(biāo)x[i] (x[i]∈[1, 20,000]), 若兩頭牛之間要對話, 音量Voice = max(v[i], v[j]) * 相互的距離. 問所有N(N-1)/2對正在說話的牛產(chǎn)生的所有聲音的總和.

樸素的算法超時(shí),用的是樹狀數(shù)組解決,思路如下:
對于牛先基于耳聾值進(jìn)行排序(下述前后皆指排序過后的相對位置), 這樣做的好處是可以確定每頭牛對話時(shí), 到底考慮誰的音量: 由于是兩兩對話,我們可以對每頭牛都只考慮位于自己前方的牛.

位于自己前方的牛中,不論是坐標(biāo)比自己大還是比自己小的,音量都沒自己大,所以都以自己的音量為準(zhǔn). 用兩個(gè)樹狀數(shù)組來存儲(chǔ)2個(gè)數(shù)據(jù):
A: x坐標(biāo)比自己小的牛的個(gè)數(shù)
B: x坐標(biāo)比自己小的牛的個(gè)數(shù)的x值之和

那么在i牛之前,x軸坐標(biāo)比自己小的距離絕對值即 A * x[i] - B

問: 那對于i牛,x坐標(biāo)比自己大的怎么算呢? 首先,x坐標(biāo)比自己大的牛 數(shù)量有 i - 1 - A, 其次對于計(jì)算到牛i而言, 每次都把當(dāng)前牛的x軸坐標(biāo)加到樹狀數(shù)組中, 所以前 20000項(xiàng)和(尚不包括第x[i]項(xiàng))即所有在排序后數(shù)組中,位于牛i前面的牛x值之和, 減去B即所有x值比i大的牛x值之和. 再減去(i - 1 - A) * x[i], 即所有x值比i大的牛到第i牛的距離之和了. (這里因?yàn)榍擅钣么髷?shù)減小數(shù)去掉了絕對值)

樹狀數(shù)組: (用樹狀數(shù)組1)如何記錄A? 每一頭牛出現(xiàn)之后,把自己所在x位置+1, 那么前x[i]項(xiàng)和即A了, 因?yàn)閤位置比x[i]大的不會(huì)被統(tǒng)計(jì)進(jìn)來.

(用樹狀數(shù)組2)如何記錄B? 每一頭牛出現(xiàn)之后,把自己所在x位置+自己的x值, 那么統(tǒng)計(jì)前x[i]項(xiàng)和即B. 前20000項(xiàng)和即包括x值比自己大和比自己小的x值之和...

利用時(shí)間的先后和空間上的前后關(guān)系來統(tǒng)計(jì)..再十分啰嗦的舉個(gè)莉子.
一個(gè)數(shù)組a[1...10]有10個(gè)元素,怎么統(tǒng)計(jì)7號元素(即a[7])之前有多少個(gè)比自己小的?, 設(shè)置一個(gè)vis數(shù)組={0},從第1到第6個(gè)元素每個(gè)都設(shè)置vis[a[i]] = 1, 統(tǒng)計(jì)前a[7]項(xiàng)(不包括第a[7]項(xiàng)的)和,即比自己小的元素個(gè)數(shù)了..同理統(tǒng)計(jì)A,B,只不過樹狀數(shù)組是快速實(shí)現(xiàn)了vis數(shù)組求和功能

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> Cow;
const ll maxN = 20005, inf = 0x3f3f3f3f;
Cow cow[maxN];
ll bit[2][maxN];
ll N;

// 求前i項(xiàng) 和 第i項(xiàng)加x
ll sum(int i, int j) { ll ret = 0; while (i) { ret += bit[j][i]; i -= i & -i; } return ret; }
void add(int i, int x, int j) { while (i <= 20000) { bit[j][i] += x; i += i & -i; } }


// cow的first: volume, second: x coordinate
int main() {
    freopen("data.in", "r", stdin);
    scanf("%lld", &N);
    for (ll i = 1; i <= N; ++i)
        scanf("%lld %lld", &cow[i].first, &cow[i].second);
    sort(cow + 1, cow + 1 + N);

    ll ans = 0;
    // 對于每一頭牛 考慮排序在自己之前的牛
    for (int i = 1; i <= N; ++i) {
        // a是x坐標(biāo)比自己小的牛數(shù)量, b是x坐標(biāo)比自己小的牛的x值之和
        ll a = sum(cow[i].second, 0), b = sum(cow[i].second, 1);
        ans += (cow[i].second * a - b + sum(20000, 1) - b - (i - 1 - a) * cow[i].second) *
                cow[i].first;
        add(cow[i].second, 1, 0);
        add(cow[i].second, cow[i].second, 1);
    }
    printf("%lld\n", ans);
    return 0;
}

hduoj 4417
給定N個(gè)數(shù)字的序列，后續(xù)有M個(gè)詢問。詢問給定l,r,H, 問[l,r]中，有多少個(gè)數(shù)字小于H。
這里使用樹狀數(shù)組解決，數(shù)組和詢問都先記錄下標(biāo)，然后數(shù)組按數(shù)值從小到大排序，詢問按H從小到大排序。之后從頭遍歷詢問，每次只插入小于自己H的值的元素的下標(biāo)，那么插完時(shí)，看[l,r]內(nèi)有多少個(gè)值就可以了，為sum(r)-sum(l-1)

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

#define pii pair<int,int>
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define fi first
#define se second
const double eps = 1e-8, PI = acos(-1.0f);
const int inf = 0x3f3f3f3f, maxN = 1e5 + 5;
int N, M, T;

int bit[maxN];
int add(int i, int x) {
    while (i <= N) { 
        bit[i] += x; 
        i += i & -i;
    }
}
int sum(int i) {
    int s = 0;
    while (i > 0) {
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

pii nd[maxN];
struct Ques {
    int id, s, t, H;
} Q[maxN];
bool cmp(const Ques& a, const Ques& b) { return a.H < b.H; }

int ans[maxN];
int main() {
    // freopen("data.in", "r", stdin);
    scanf("%d", &T);
    rep(cas, 1, T + 1) {
        scanf("%d%d", &N, &M);
        rep(i, 1, N + 1) {
            scanf("%d", &nd[i].fi);
            nd[i].se = i;
        }

        int s, t, H;
        rep(i, 1, M + 1) {
            scanf("%d%d%d", &Q[i].s, &Q[i].t, &Q[i].H);
            ++Q[i].s; ++Q[i].t;
            Q[i].id = i;
        }

        sort(nd + 1, nd + 1 + N);
        sort(Q + 1, Q + 1 + M, cmp);
        mst(bit, 0);

        printf("Case %lld:\n", cas);
        // j: Ques, i: Node
        int i = 1, j = 1;
        while (j <= M) {
            while (i <= N) {
                if (nd[i].fi > Q[j].H)
                    break;
                add(nd[i].se, 1);
                ++i;
            }
            ans[Q[j].id] = sum(Q[j].t) - sum(Q[j].s - 1);
            ++j;
        }
        rep(i, 1, M + 1)
            printf("%d\n", ans[i]);
    }
    return 0;
}