CWOI S C0354 C 箱子

题意

U2FsdGVkX18h0FJyX3O8BEkPx8LzabhwvwNnfXrIOqHL1SrajqZlaUXuWqq8gQ+L
d+0GC9M6tsKEwHXuLWfMFuYgvnEXPI1RP/V/d3ej/P4VswUEvlQQDutYvzyz37xO
MCn6mCcu9Sah0loQnOS7S0UKXCUoT6i6cMLWmjkTw3EkL2CUyLQStRDqI0N5Ubym
egVXBkRxm7mvJ2YMw9mm5ip8hHz4bNtcKfWZAIaLb/sTieeIsYQuIi5kAPun5TtA
pa+2HE23OedS4N/lrh+6VNJBv+1l71iOdH3YogK1Bs/B4XotpEYu3mvns3+QG4yw
HoAtYCAH+ShDc2C4sOW2aZp8Ipc0/XNI0BveRzLbsDLyh0LE3jyOmo0LjcnTgHP+
Hj02qi08uTXN5eDCS30eyMDJvqgcuBD0jZLRbIjOJt6SqzHOX43MoVOxjF/hyIaR
OCiFJsMUVCRbd/7j4gt+uUXfY1p8tqafqEa637+irkLJBuXRLj0dw0W14dOVka7W
NWmo0/zvGCBFDCEvNVSra6c8E+47psADrAQ+RBLIm4YlIe0nIFYw9z8rpyUk0JXn
xvugS4g/R4FflJ8KoKQhVii6TRkQpYYtYIMICLLBFj53ad+N1TrtJzo93MCr81TC
XwQ/w6md5J/rPjaKFXNlQIFfwa658GcjaiJh3J1wx7vqbgNMxhMJVqVOKnkqq3wB
t5PNFwyufxpJOOyDa3sGPOtXe4fUhLNdQBys2KKIni5t54HaDH1V9cHm6GKS2tKU
2tE4rieXVxcoidVu8e8pRXzv6jOnp72bLmhpAmKtWdo=

解析

首先可以考虑一个朴素的暴力，前两个询问都非常好处理。对于第三个询问，考虑求出其差分数组，根据差分计算每个位置作为端点产生的贡献，再加上两端的贡献。

发现每个位置作为端点产生的贡献只和他和前后两个位置的差分有关。我们使用一个树状数组，下标 i 存的是第 i 个三元组和第 i+1 个三元组的询问三的答案，减去两端的贡献。然后如果要计算区间答案的话，显然可以树状数组区间求和。对于第一个修改操作，更新修改位置前后的维护的答案即可。对于第二个修改，使用 std::map 维护颜色段，每次更新颜色段端点处维护的答案即可。复杂度 $O(n\log n)$。

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <string>
#include <vector>

void set_io(std::string name)
{
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}

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

struct fenwick
{
  int n;
  std::vector<long long> t;
  fenwick(int n) : n(n), t(n, 0) {}

  void add(int x, long long v)
  {
    for (x++; x <= n; x += lowbit(x)) t[x - 1] += v;
  }

  void set(int x, long long v)
  {
    add(x, v - sum(x, x + 1));
  }

  long long sum(int x) const
  {
    long long res = 0;
    for (; x > 0; x -= lowbit(x)) res += t[x - 1];
    return res;
  }

  long long sum(int l, int r) const
  {
    return sum(r) - sum(l);
  }
};

int main()
{
  set_io("box");

  int N, Q;
  std::cin >> N >> Q;
  std::vector<int> A(N), C(N), W(N);
  for (int i = 0; i < N; i++) {
    std::cin >> A[i] >> C[i] >> W[i];
  }

  std::map<int, int> color;
  for (int i = 0; i < N; i++) color[i] = C[i];
  auto split = [&color](int x)
  {
    auto p = --color.upper_bound(x);
    if (p->first == x) return p;
    auto v = p->second;
    return color.emplace(x, v).first;
  };
  auto get = [&color](int x)
  {
    auto p = --color.upper_bound(x);
    return p->second;
  };

  fenwick sum(N - 1);

  auto update_sum = [&sum, &A, &get, &W](int x)
  {
    if (get(x) == get(x + 1)) {
      int d = A[x + 1] - A[x];
      if (d < 0) {
        sum.set(x, (long long)W[x] * -d);
      } else {
        sum.set(x, (long long)W[x + 1] * d);
      }
    } else {
      sum.set(x, (long long)A[x] * W[x] + (long long)A[x + 1] * W[x + 1]);
    }
  };
  for (int i = 0; i + 1 < N; i++) update_sum(i);

  for (int i = 0; i < Q; i++) {
    int op;
    std::cin >> op;
    if (op == 1) {
      int x, v1, v2;
      std::cin >> x >> v1 >> v2;
      x--;
      A[x] = v1;
      W[x] = v2;
      if (x - 1 >= 0) update_sum(x - 1);
      if (x < N - 1) update_sum(x);
    } else if (op == 2) {
      int l, r, v;
      std::cin >> l >> r >> v;
      l--;
      auto lp = split(l);
      auto rp = split(r);
      std::vector<int> changed;
      for (auto p = lp; p != rp; ) {
        changed.emplace_back(p->first - 1);
        p = color.erase(p);
      }
      changed.emplace_back(r - 1);
      color.emplace(l, v);
      for (auto i : changed) {
        if (0 <= i && i < N - 1) {
          update_sum(i);
        }
      }
    } else if (op == 3) {
      int l, r;
      std::cin >> l >> r;
      l--;
      r--;
      long long ans = sum.sum(l, r);
      ans += (long long)A[l] * W[l];
      ans += (long long)A[r] * W[r];
      std::cout << ans << std::endl;
    }
  }
}