树状数组

1. 单点修改;

2. 区间求和;

原理: 用一个树上节点维护序列[l, r]的元素之和.

模板题目:

P3374 【模板】树状数组 1

P3368 【模板】树状数组 2

注意事项:

1. 数列下标从1开始;

2.

int lowbit(int x) // loxbit(x)表示在二进制下最右边的1加上后面的0的值
{
    return x & -x;
}

void insert(int x, int v) // 数列a[x] += v;
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}

int query(int x) // 返回数列a, 区别[1, x]的和
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];

    return res;
}

例题:

P1908 逆序对

解法一

1. 第一维:下标, 天然有序;

2. 第二维:值域, [1, 1e9];

3. 依次将a[1], a[2] … a[n], 插入数轴

4. 当枚举到a[i]时, 已经有i-1格元素, 下标比i小;

5. 能够与i个数形成逆序对, 只有前i-1个元素中比a[i]小的那些数;

两种解法本质一样, 只不过第二种解法给我们带来了更多的好处

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

typedef long long ll;

const int N = 5e5 + 10;
ll a[N], b[N];
ll tr[N];
int n;

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

void add(int x, int v)
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}

int query(int x)
{
    ll res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];

    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];

        b[i] = a[i];
    }

    sort(b + 1, b + n + 1);

    int m = unique(b + 1, b + n + 1) - b - 1;

    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;

    ll res = 0;
    for (int i = 1; i <= n; i++)
    {
        res += query(n) - query(a[i]);

        add(a[i], 1);
    }

    cout << res;


    return 0;
}

解法二

第一维: 值域

第二维: 下标

… 很水的

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

typedef pair<int, int> PII;
typedef long long ll;

const int N = 5e5 + 10;
PII a[N];
ll tr[N];
int n;

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

void add(int x, int v)
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}

int query(int x)
{
    ll res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];

    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].first;

        a[i].second = i;
    }

    sort(a + 1, a + n + 1);
    reverse(a + 1, a + n + 1);

    ll res = 0;
    for (int i = 1; i <= n; i++)
    {
        add(a[i].second, 1);

        res += query(a[i].second - 1);
    }

    cout << res;



    return 0;
}

🐄 🐄 🐄 🐄 🐄 🐄 🐄 🐄 🐄 🐄 🐄 🐄 🐄 🐄 🐄 🐄 🐄 🐄

U470813 POJ-2481 Cows

1. 将n个区间先按照第一维从大到小排序, e相等时, 按s从小到大;

2. 枚举每一头🐄 i, 能够罩住第i区间的牛编号一定在[1, i-1], 树状数组维护第二维;

3. 比i强壮的牛数为query(g[i].s);

4. 若g[i].s == g[i - 1].s && g[i].e == g[i - 1].e, 那么ans[g[i].id] = ans[g[i - 1].id];

5. 不管答案从何而来, 修改必做, update(g[i].s, 1);

6. 输入时, s和e都加1, 维护的是值域1e5+1, 而不是n;

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

const int N = 1e5 + 1;
int a[N + 10];
int tr[N + 10];
int n, m;

struct Cow
{
    int s, e, id, ans;
} g[N];

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

void add(int x, int v)
{
    for (int i = x; i <= N; i += lowbit(i)) tr[i] += v;
}

int query(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];

    return res;
}

bool cmp1(Cow a, Cow b)
{
    if (a.s != b.s) return a.s < b.s;

    return a.e > b.e;
}

bool cmp2(Cow a, Cow b)
{
    return a.id < b.id;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    while (cin >> n, n)
    {
        for (int i = 1; i <= n; i++)
        {
            cin >> g[i].s >> g[i].e;

            g[i].e++, g[i].id = i;
        }

        memset(tr, 0, sizeof tr);

        sort(g + 1, g + n + 1, cmp1);

        for (int i = 1; i <= n; i++)
        {
            if (g[i].s == g[i - 1].s && g[i].e == g[i - 1].e) g[i].ans = g[i - 1].ans;
            else g[i].ans = i - query(g[i].e - 1) - 1;

            add(g[i].e, 1);
        }

        sort(g + 1, g + n + 1, cmp2);

        for (int i = 1; i <= n; i++) cout << g[i].ans << ' ';

        cout << '\n';
    }


    return 0;
}

Tufurama

题目提取:

1. i <= min(a[j], j - 1) 第一个按询问维护

2. a[i] >= j; 第二个用树状数组

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

typedef pair<int, int> PII;
typedef long long ll;

const int N = 2e5 + 10;
int a[N];
PII b[N];
bool st[N];
ll tr[N];
int n;

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

void add(int x, ll k)
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += k;
}

ll query(int x)
{
    ll res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];

    return res;
}

bool cmp(PII a, PII b)
{
    return a.first < b.first;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];

        b[i] = {a[i], i};
        add(i, 1);
    }

    sort(b + 1, b + n + 1, cmp);

    ll res = 0;
    int cnt = 1;
    for (int i = 1; i <= n; i++)
    {
        if (!st[i])
        {
            st[i] = true;
            add(i, -1);
        }

        while (b[cnt].first < i && cnt <= n)
        {
            if (!st[b[cnt].second])
            {
                st[b[cnt].second] = true;
                add(b[cnt].second, -1);
            }

            cnt++;
        }

        res += query(min(n, a[i]));
    }

    cout << res;


    return 0;
}

P3605 [USACO17JAN] Promotion Counting P

1. 维护一个数轴, 统计每个值出现的节点数量;

2. dfs遍历到点i时, 统计比a[i]大的元素个数sum1;

3. 递归遍历点i的子树, 递归后, 统计比a[i]大的元素个数sum2, sum1-sum2答案;

4. 统计完sum1-sum2之后, add(a[i], 1);

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

typedef long long ll;

const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
int a[N], b[N];
ll tr[N];
ll f[N];
int n;

void Add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

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

void add(int x)
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i]++;
}

int query(int x)
{
    ll res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];

    return res;
}

void dfs(int u)
{
    f[u] -= query(n) - query(a[u]);

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];

        dfs(j);
    }

    f[u] += query(n) - query(a[u]);

    add(a[u]);
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];

        b[i] = a[i];
    }

    sort(b + 1, b + n + 1);

    int m = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;

    memset(h, -1, sizeof h);

    for (int i = 2, v; i <= n; i++)
    {
        cin >> v;

        Add(v, i);
    }

    dfs(1);

    for (int i = 1; i <= n; i++) cout << f[i] << '\n';


    return 0;
}

P5094 [USACO04OPEN] MooFest G 加强版

1. 按照v值从小到大排序, 好处是v[i] * dist(i, j);

2. 统计牛i与前i-1头牛的音量之和;

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

typedef long long ll;
typedef pair<ll, ll> PLL;

const int N = 5e4 + 10;
PLL g[N];
ll tr1[N << 2], tr2[N << 2];
int n;

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

void add1(ll x)
{
    for (int i = x; i <= N; i += lowbit(i)) tr1[i]++;
}

void add2(ll x)
{
    for (int i = x; i <= N; i += lowbit(i)) tr2[i] += x;
}

int query1(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr1[i];

    return res;
}

int query2(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr2[i];

    return res;
}

bool cmp(PLL a, PLL b)
{
    return a.first < b.first;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    ll a, b;
    for (int i = 1; i <= n; i++)
    {
        cin >> a >> b;

        g[i] = {a, b};
    }

    sort(g + 1, g + n + 1, cmp);

    ll res = 0, sum = 0;
    for (int i = 1; i <= n; i++)
    {
        a = query1(g[i].second), b = query2(g[i].second);

        res += (a * g[i].second - b) * g[i].first;
        res += (sum - b - (i - a - 1) * g[i].second) * g[i].first;
        sum += g[i].second;

        add1(g[i].second);
        add2(g[i].second);
    }

    cout << res;


    return 0;
}

P1972 [SDOI2009] HH的项链

1. 离线解决, 按区间右端点从小到大排序;

2. 维护一个关于下标的树状数组, 数值是1或0;

3. 维护一个左右指针L和R, 每次R跑到询问的右端点( 这里其实可以发现L没用 );

4. 维护pos[val]表示元素val最后一次出现的位置

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

const int N = 1e6 + 10;
int a[N];
int ne[N], pre[N];
int tr[N], ans[N];
int n;

struct Cow
{
    int l, r, id;
} g[N];

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

void add(int x)
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i]++;
}

int query(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];

    return res;
}

bool cmp(Cow a, Cow b)
{
    if (a.l == b.l) return a.r < b.r;

    return a.l < b.l;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; i++) cin >> a[i];

    int k = 0;
    for (int i = n; i; i--)
    {
        ne[i] = pre[a[i]];
        pre[a[i]] = i;
        k = max(k, a[i]);
    }

    int m;
    cin >> m;

    for (int i = 1; i <= m; i++)
    {
        cin >> g[i].l >> g[i].r;

        g[i].id = i;
    }

    sort(g + 1, g + m + 1, cmp);

    for (int i = 1; i <= k; i++)
        if (pre[i]) add(pre[i]);

    int cnt = 1;
    for (int i = 1; i <= m; i++)
    {
        while (cnt < g[i].l)
        {
            if (ne[cnt]) add(ne[cnt]);

            cnt++;
        }

        ans[g[i].id] = query(g[i].r) - query(g[i].l - 1);
    }

    for (int i = 1; i <= m; i++) cout << ans[i] << '\n';


    return 0;
}

UVA12983 The Battle of Chibi

1. 状态: f[i][j]表示长度恰好为i, 且以第j个数为结尾的上升子序列个数;

2. 答案: ans += f[m][i];

3. 状态转移:

if (a[k] < a[j])
    f[i][j] = (f[i][j] + f[i - 1][k]) % mod;

4. 初始化: f[1][i] = 1;

5. 传说好像不用开long long, 好像有些人开long long还会TLE

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

typedef long long ll;

const int N = 2010, mod = 1e9 + 7;
int a[N], b[N];
ll f[N][N];
ll tr[N];
int n, m;

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

void add(int x, ll k)
{
    for (int i = x; i <= N; i += lowbit(i)) tr[i] = (tr[i] + k) % mod;
}

int query(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res = (res + tr[i]) % mod;

    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;

    int Case = 0;
    while (t--)
    {
        cin >> n >> m;

        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];

            b[i] = a[i];
        }

        sort(b + 1, b + n + 1);

        for (int i = 1; i <= n; i++)
            a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b + 1;

        f[0][0] = 1;

        add(1, 1);

        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                f[i][j] = query(a[j] - 1);
                add(a[j], f[i - 1][j]);
            }

            memset(tr, 0, sizeof tr);   
        }

        ll res = 0;
        for (int i = 1; i <= n; i++)
            res = (res + f[m][i]) % mod;

        cout << "Case #" << ++Case << ": " << res << '\n';
    }


    return 0;
}