2020牛客寒假算法基础集训营4 H- 坐火车 (桶，树状数组)

链接：https://ac.nowcoder.com/acm/contest/3005/H
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

牛牛是一名喜欢旅游的同学，在来到渡渡鸟王国时，坐上了颜色多样的火车。

牛牛同学在车上，车上有 n 个车厢，每一个车厢有一种颜色。

他想知道对于每一个正整数 x∈[1, n]x \in [1,\ n]x∈[1, n] ，集合 {(i, x, j) ∣ i<x<j, lx≤coli=colj≤rx}{ (i,\ x,\ j)\ |\ i < x < j,\ l_x \le col_i = col_j \le r_x }{(i, x, j) ∣ i<x<j, lx≤coli=colj≤rx} 中包含多少个元素。

换句话说，就是要求每一个车厢两边有多少对颜色相同的车厢，并且这一对车厢的颜色要在 lx 到 rx 之间。其中 coli 代表 i 号车厢的颜色，lx,rx 代表颜色的限制。

输入描述:

第一行一个正整数n。
第二行 n 个三元组，每个三元组包括三个正整数 (coli, li, ri)，输入中没有括号，这 3n 个正整数之间均只用空格隔开，详见样例。

输出描述:

输出一行 n 个非负整数代表答案。

示例1

输入

[复制](javascript:void(0)😉

5
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

输出

[复制](javascript:void(0)😉

0 3 4 3 0

备注:

1≤n≤5⋅1051 \le n \le 5 \cdot 10^51≤n≤5⋅105
1≤coli, li, ri≤5⋅1051 \le col_i,\ l_i,\ r_i \le 5 \cdot 10^51≤coli, li, ri≤5⋅105

思路：

我们从左到右，每一个位置i，用树状数组维护每种颜色的该车厢左右的对数。

因为树状数组有维护动态前缀和的功能，ask(r) 代表0~r颜色中，有多少相同颜色的车厢左右的对数。

所以每一个位置i的答案是 \(ask(r)-ask(l-1)\)

再来看如何用树状数组维护每种颜色的该车厢左右的对数

我们用数组\(cnt2[j]\) 代表第i个位置之后有多少个j颜色。

用数组\(cnt1[j]\) 代表第i个位置之前有多少个j颜色。

我们知道 i=1 的位置答案肯定为0。

思考如何向右转移：

从第i-1个位置移动到了第i位置时，如果i-1左边有颜色为\(col[i]\) 的，应该在颜色为\(col[i]\)的车相对中减去\(cnt1[a[i]]\)个

接着\(cnt2[col[i]]\)减去1，\(cnt1[col[i - 1]]\) 加上1.

有因为原本的i-1位置变成了i位置左边的颜色，所以应该在颜色为\(col[i-1]\)的车相对中减去\(cnt2[col[i]]\)个.

对cnt1和cnt2的操作直接对数组修改即可，对颜色组成的车相对数用树状数组单点更新即可。

即从第i个位置的答案 \(O(logn)\) 时间复杂度内转移到第i+1位置，同时得到第i+1位置的答案，

这样总体时间复杂度就是\(O(n*logn)\)

代码：

int l[maxn];
int r[maxn];
int a[maxn];
int cnt1[maxn];
int cnt2[maxn];
ll tree[maxn];
int n;
int lowbit(int x)
{
    return x & (-x);
}
void add(int x, ll val)
{
    while (x < maxn)
    {
        tree[x] += val;
        x += lowbit(x);
    }
}
ll ask(int x)
{
    ll res = 0ll;
    while (x)
    {
        res += tree[x];
        x -= lowbit(x);
    }
    return res;
}
ll ans[maxn];
 
int main()
{
    //freopen("D:\\code\\text\\input.txt","r",stdin);
    //freopen("D:\\code\\text\\output.txt","w",stdout);
    n = readint();
    repd(i, 1, n)
    {
        a[i] = readint();
        l[i] = readint();
        r[i] = readint();
    }
    ll num = 0ll;
    repd(i, 2, n)
    {
        cnt2[a[i]]++;
    }
    repd(i, 2, n - 1)
    {
        if (cnt1[a[i]])
            add(a[i], -cnt1[a[i]]);
        cnt2[a[i]]--;
        cnt1[a[i - 1]]++;
        if (cnt2[a[i - 1]])
            add(a[i - 1], cnt2[a[i - 1]]);
        ans[i] = ask(r[i]) - ask(l[i] - 1);
    }
    repd(i, 1, n)
    {
        printf("%lld%c", ans[i], i == n ? '\n' : ' ');
    }
 
    return 0;
}