题解 | [树状数组]坐火车

最开始我是想暴力的，用 map 类型的 l,r ，处理左边和右边对应颜色区间，二分查找到大于等于 的位置，再遍历到 ，果不其然，TLE了喵。

先不考虑 的限制，注意到，对于第 个车厢，相较于前一个变化在哪呢？其实就是其所属颜色 ，原本的右侧 减1，左边的不变，因此增加了 的情况，也就是说，变化数相当于前者 而已，输出答案后，该元素被算在左侧，因此 要加 。

然后，由于有着区间的限制，我们需要一个工具，能查询 的区间和，以及对上述两种加减操作能够进行单点修改。

单点修改，那就不用线段树了，用 树状数组 。

树状数组可参见OI-WiKi 树状数组

时间复杂度是

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

const int N = 5e5 + 10;
int c[N];
int n;

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

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

int getsum(int x) {
    int ans = 0;
    while (x > 0) {
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

int getlr(int l, int r) {
    return getsum(r) - getsum(l-1);
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    map<int, int> l;
    map<int, int> r;
    int a[n + 1][3];
    for (int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
        r[a[i][0]]++; //预先记录，right
    }
    for (int i = 0; i < n; i++) {
        int t = a[i][0];
        r[t]--; //减去右侧
        //(a-1)(b) = ab-b，此时
        add(a[i][0], -l[t]);
        cout << getlr(a[i][1], a[i][2]) << ' ';
        //(a-1)(b+1) = ab-b+(a-1)
        add(a[i][0], r[t]);
        l[t]++; //加入左侧
    }
}
// 64 位输出请用 printf("%lld")