1924B. Space Harbour

题意：

n个点排成一行，其中某些点上面建有港湾，港湾有一个权值，对每个点我们定义点的权值为“左边（包括自己）第一个港湾上的权值 \(\times\) 到右边（包括自己）第一个港湾的距离”（保证在一开始1号和n号点上都有港湾）。
有q次操作：操作1给定x和v，表示在x点上建立权值为v的港湾（保证同一个点不会重复建）；操作2给定l和r，要求[l, r]区间上每个点的权值和。

数据范围：

n, q ~ 3e5 TL: 2s
港湾的权值范围 (0, 1e7]

思路：

看起来就很像线段树。需要支持区间查询和区间修改。
本题的关键在于如何确定我们要维护的东西 & 如何修改。

对于每次修改，在点x上建立权值为v的港湾，设这个港湾左边第一个港湾在L位，右边第一个港湾在R位。则区间[x, R-1]上的点的左边第一个港湾权值变为v，点权同时乘以一个分数，区间[L+1, x]上的点到右边第一个港湾的距离减少了（R - x），点权同时减小一个数。如果直接写一个支持乘法与加法的线段树可能会有精度问题/速度问题，所以考虑对每一个节点多记录一个“当前左边第一个港湾的权值”，来避免使用浮点数，思路依然是线段树。

对每个节点我们记录val（点的权值），lef（左边第一个港湾的权值），add（懒标记）。若这个区间中并非所有点的lef都相同的话，将lef设为-1.
我们有两种修改操作：

1. 将lef改成v，同时节点的val也改变了
2. 将val加上一个值
   同理也就应该有两个懒标记，但这里lef可以直接当做修改\(1\)的懒标记使用，就只用add一个懒标记就够了。详见代码。

注意事项：

懒标记叠加这一块有点搞，需要理清楚叠加方式&两个懒标记的顺序。这里是先应用lef懒标记再应用add懒标记
本题需要用两个修改操作，如果写两个modify函数会比较麻烦，因此直接用一个函数实现，比较简洁。

代码：

#include<bits/stdc++.h>

using namespace std;

int n,m,q;
const int N = 3e5+10;
typedef long long ll;
struct node
{
    int l,r;
    ll val,add;
    int lef;
}tr[N<<2];
int a[N],p[N],v[N];
set<int> alls;

void update(node &t, int lef, ll more)
{
    if(lef == -1 && more == 0) return;
    if(lef == -1)
    {
        t.val += more * (t.r-t.l+1);
        t.add += more;
        return;
    }
    t.val = t.val / t.lef * lef + more*(t.r-t.l+1);
    t.add = t.add / t.lef * lef + more;
    t.lef = lef;
}

void pushdown(int u)
{
    auto &now = tr[u], &L = tr[u<<1], &R = tr[u<<1|1];
    update(L,now.lef,now.add);
    update(R,now.lef,now.add);
    now.add = 0;
}

void pushup(int u)
{
    auto &now = tr[u], &L = tr[u<<1], &R = tr[u<<1|1];
    now.lef = (L.lef == R.lef ? L.lef : -1);
    now.val = L.val + R.val;
}

void build(int u,int l,int r)
{
    tr[u] = {l,r,0,0,a[1]};
    if(l == r)
    {
        tr[u].val = (ll)a[1] * (n-l);
        if(l == 1) tr[u].val = 0;
        return;
    }
    int mid = l + r >> 1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
}

void modify(int u,int l,int r,int lef,ll more)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        update(tr[u],lef,more);
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if(l <= mid) modify(u<<1,l,r,lef,more);
    if(r > mid) modify(u<<1|1,l,r,lef,more);
    pushup(u);
}

ll query(int u,int l,int r)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].val;
    }

    pushdown(u);
    ll ret = 0;
    int mid = tr[u].l + tr[u].r >> 1;
    if(l <= mid) ret = query(u<<1,l,r);
    if(r > mid) ret += query(u<<1|1,l,r);
    return ret;
}

void ins(int u,int val)
{
    auto it = alls.lower_bound(u);
    int R = *it;
    int L = *(prev(it));

    modify(1,L+1,u,-1,(ll)(u-R)*a[L]);

    modify(1,u,R-1,val,0);
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n>>m>>q;
    vector<pair<int,int> > need;

    for(int i = 1; i <= m; ++i)
        cin>>p[i];
    for(int i = 1; i <= m; ++i) cin>>v[i],need.push_back({p[i],v[i]});
    sort(need.begin(),need.end());
    a[1] = need[0].second;
    a[n] = need.back().second;

    build(1,1,n);

    alls.insert(1);alls.insert(n);

    for(int i = 1; i < m-1; ++i)
    {
        ins(need[i].first,need[i].second),alls.insert(need[i].first),a[need[i].first] = need[i].second;
    }

    while(q--)
    {
        int op,x,v;
        cin>>op>>x>>v;
        if(op == 1)
        {
            ins(x,v);
            a[x] = v;
            alls.insert(x);
        }
        else cout<<query(1,x,v)<<'\n';
    }
    return 0;
}

正好再复习一下线段树的原理：

线段树的基本想法：

线段树将区间分成很多块，然后把很多小区间拼起来得到答案，以高效地实现区间查询。
在修改时，若为单点修改直接将相关的logn个区间都修改即可，若为区间修改，则需要使用“延迟修改”的技巧。
下面讨论区间修改线段树。

线段树的流程（修改与查询）：

当我们查询一个区间[\(l\), \(r\)]时，我们从上（最上方的节点是[\(1\), \(n\)]，最下方的节点是[\(i\), \(i\)]）往下找一群小区间，正好不重不漏地覆盖了[\(l\), \(r\)]，将这些小区间的权值合并，就得到了答案。复杂度 ~ 4logn
当我们修改一个区间[\(l\), \(r\)]时，为了保证复杂度在log级别，我们依然像查询操作那样找到一群不重不漏的小区间，对这些区间应用更改，然后先不对下面的区间应用修改，而是给被修改的区间打上懒标记。
懒标记的意思是：“这个标记下面的节点（子孙节点）当前处于 还没有应用此修改的状态 ，因此如果需要查询/修改^[1]子孙节点的信息，需要先把懒标记代表的修改下放，也就是先用这些懒标记对两个子节点进行区间修改，并给儿子打上懒标记，在进行查询/修改”。我们可以将其看做“迟到的区间修改”。
因此，对于每个节点来说，他维护的是当前时间点（父节点上懒标记还没有应用）时的权值，以及他自己身上的懒标记（就是被这个区间拦截住还没来得及下放的修改操作）。

由此，我们可以写出线段树的一些关键函数的伪代码。

eval(int u,int add)  //用于应用修改
{
  用add来维护tr[u]的权值。
}
pushdown(int u); //用于懒标记下放
{
  用u的懒标记维护u的儿子的权值（eval函数）
  将u的懒标记传给儿子。
  清空u的懒标记。
}

modify(int u,int l,int r,int d);  //区间修改
{
  if（u这个区间完全被[l, r]包含）
  {
    eval(u,d);
    return;
  }
  pushdown;
  如果u的左/右儿子与[l, r]有交，那就对左/右儿子modify
  pushup;
}
query(int u,int l,int r);  //区间查询
{
  if（u这个区间完全被[l, r]包含）
  {
    return u的权值
  }
  pushdown;
  如果u的左/右儿子与[l, r]有交，那就对左/右儿子query
  将对儿子query的结果合并后return
}

线段树的使用条件：

1. 在modify和pushdown操作时，我们需要对整个区间进行修改，得在大约\(O(1)\)的时间内完成修改。（只有区间修改线段树有这个要求）
2. 在区间修改后，我们需要叠加懒标记，因此懒标记得是可叠加的。（只有区间修改线段树有这个要求）
3. 在pushup操作中，需要用子节点信息维护父节点信息，因此维护的信息需要是可以拆分&合并的。

反过来想，只要可以快速对区间的权值进行修改、可以叠加懒标记、可以pushup维护信息，就可以用线段树来实现！