KTT 学习笔记 / CF1830F The Third Grace 题解 / NOIP 模拟赛 #5 D 题解

Otomachi_Una_ · 2023-09-21 22:16:03 · 题解

我们首先介绍一个叫做 KTT（Kinetic Tournament Tree）的神奇算法。

1. KTT 解决的问题

我们考虑这样的问题：

考虑维护 n 个一次函数，其中第 i 个是 a_ix_i+b_i。维护一下三种操作：

求 f 区间 \max：求 \max_{l\leq i\leq r} a_ix_i+b_i。

其中需要保证 c>0。

KTT 的复杂度大概是 \mathcal O((n+q)\text{polylog }n)。其中 \text{polylog} 大概在实际上可以看做 \log\sim\log^2。跑得很快。论文上写的是 \log^3，笔者认为很难达到。

我们下面仅围绕着 CF1830F 所需要的结构进行讨论，也就是我们这里不进行 b 的区间加，我们进行 a,b 的单点赋值。实际上做到 b 的区间加试不难的。

2. KTT 的构建

KTT 的本质还是一颗线段树。我们考虑线段树的节点维护一下的信息：

使得 i 子树内某个节点维护最大值发生改变的最小增加的正整数 intr_i。

如果没看懂可以直接看下面每个操作的解释。

在构建 KTT 的过程中，如果访问到一个节点，我们就把其维护的最优线段的 x 归零，并加到 b_i 上面去。

pushdown 函数

考虑如何把懒标记下传。实际上是简单的。

void pushdown(int id){
    for(int son:{id<<1,id<<1|1}){
        val[son].b+=laz[id]*val[son].a;
        intr[son]-=laz[id];
        laz[son]+=laz[id];
    }
    laz[id]=0;
    return;
}

我们只需要更新一下两边儿子最优节点的 b 值，加一下懒标记，再右移一下最小更新点即可。

pushup 函数

这个是更加简单的。

void pushup(int id){
    val[id]=(val[id<<1]<val[id<<1|1]?val[id<<1|1]:val[id<<1]);
    intr[id]=min({intr[id<<1],intr[id<<1|1],inter(val[id<<1],val[id<<1|1])});
    return;
}

这里 inter 函数是求两个线段的交点的纵坐标（向上取整，如果小于 0 返回无穷大）。具体见下方：

ll inter(line x,line y){
    ll da=x.a-y.a,db=y.b-x.b;
    if(da>=0&&db<=0||da<=0&&db>=0) return inf;
    return (da>0?(da+db-1)/da:(-da-db+1)/(-da));
}// 求交点

rebuild 函数

考虑一个节点子树内某个节点的最大值发生变化的时候我们需要修改其子树的值。

如果一个子树的节点 intr 的是 \geq 0 的，也就是内部不会发生变化，我们应该继续递归。代码是简单的：

void rebuild(int id){
    if(intr[id]>0) return;
    pushdown(id);
    rebuild(id<<1);rebuild(id<<1|1);
    pushup(id);
    return;
}

set 函数

这是一个实现单点赋值的函数，实现也是简单的。

void set(int x,line v,int id=1,int l=1,int r=m){
    if(l==r) {val[id]=v;return;} 
    pushdown(id);
    int mid=l+r>>1;
    if(x<=mid) set(x,v,id<<1,l,mid);
    else set(x,v,id<<1|1,mid+1,r);
    pushup(id);
    return;
}

modify 函数

这个函数是实现 x 的区间加的。实现是简单的，首先像普通线段树那样递归，找到一个完整节点就按照类似 pushdown 那样去更新。然后执行一下 rebuild 函数即可。

void modify(int L,int R,ll x,int id=1,int l=1,int r=m){
    if(L<=l&&r<=R){
        laz[id]+=x;
        val[id].b+=val[id].a*x;
        intr[id]-=x;
        rebuild(id);
        return;
    }
    pushdown(id);
    int mid=l+r>>1;
    if(L<=mid) modify(L,R,x,id<<1,l,mid);
    if(mid<R) modify(L,R,x,id<<1|1,mid+1,r);
    pushup(id);
    return;
}

ask 函数

也是简单的，像普通线段树那样查询就好了。

ll ask(int L,int R,int id=1,int l=1,int r=m){
    if(L<=l&&r<=R) return val[id].b;
    pushdown(id);
    int mid=l+r>>1;ll ans=0;
    if(L<=mid) ans=max(ans,ask(L,R,id<<1,l,mid));
    if(mid<R) ans=max(ans,ask(L,R,id<<1|1,mid+1,r));
    pushup(id);
    return ans;
}

至此我们实现了 KTT 的所有操作。很好理解

3. 关于 KTT 复杂度

我不会证明。具体的可以看 EI 2020 年集训队论文。反正跑得很快。可以当做一个 \mathcal O((n+q)\log^2 n) 的东西用，常数较小。

4. 例题：CF1830 的解法

考虑 dp 方程式，f_i 表示只取了 i 和 i 前面某些点能达到的最大权值（不能计算 i 的贡献，因为 i 的贡献和后面的那个点有关）。

那么每次求得一个 f 值之后，就要对所有 r_j=i 的点，对所有的 k\in[l_j,r_j],f_k\leftarrow f_k+a_k。

我们发现这个东西可以用 KTT 维护，做完了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=1e6+5;
const ll inf=1e18;
int n,m;ll a[MAXN];
vector<int> vec[MAXN];
struct line{
ll a,b;// rep the line is ax+b 
};
bool operator <(line x,line y){
    if(x.b!=y.b) return x.b<y.b;
    return x.a<y.a;
}
ll inter(line x,line y){
    ll da=x.a-y.a,db=y.b-x.b;
    if(da>=0&&db<=0||da<=0&&db>=0) return inf;
    return (da>0?(da+db-1)/da:(-da-db+1)/(-da));
}// 求交点 
struct segt{
line val[MAXN<<2];
ll laz[MAXN<<2],intr[MAXN<<2];// intr 记录交点 
void init(int id=1,int l=1,int r=m){
    laz[id]=0;val[id]={-inf,-inf};intr[id]=inf;
    if(l==r) return;
    int mid=l+r>>1;
    init(id<<1,l,mid);init(id<<1|1,mid+1,r);
}
void pushdown(int id){
    for(int son:{id<<1,id<<1|1}){
        val[son].b+=laz[id]*val[son].a;
        intr[son]-=laz[id];
        laz[son]+=laz[id];
    }
    laz[id]=0;
    return;
}
void pushup(int id){
    val[id]=(val[id<<1]<val[id<<1|1]?val[id<<1|1]:val[id<<1]);
    intr[id]=min({intr[id<<1],intr[id<<1|1],inter(val[id<<1],val[id<<1|1])});
    return;
}
void rebuild(int id){
    if(intr[id]>0) return;
    pushdown(id);
    rebuild(id<<1);rebuild(id<<1|1);
    pushup(id);
    return;
}
void modify(int L,int R,ll x,int id=1,int l=1,int r=m){
    if(L<=l&&r<=R){
        laz[id]+=x;
        val[id].b+=val[id].a*x;
        intr[id]-=x;
        rebuild(id);
        return;
    }
    pushdown(id);
    int mid=l+r>>1;
    if(L<=mid) modify(L,R,x,id<<1,l,mid);
    if(mid<R) modify(L,R,x,id<<1|1,mid+1,r);
    pushup(id);
    return;
}
void set(int x,line v,int id=1,int l=1,int r=m){
    if(l==r) {val[id]=v;return;} 
    pushdown(id);
    int mid=l+r>>1;
    if(x<=mid) set(x,v,id<<1,l,mid);
    else set(x,v,id<<1|1,mid+1,r);
    pushup(id);
    return;
}
ll ask(int L,int R,int id=1,int l=1,int r=m){
    if(L<=l&&r<=R) return val[id].b;
    pushdown(id);
    int mid=l+r>>1;ll ans=0;
    if(L<=mid) ans=max(ans,ask(L,R,id<<1,l,mid));
    if(mid<R) ans=max(ans,ask(L,R,id<<1|1,mid+1,r));
    pushup(id);
    return ans;
}
}T;
void solve(){
    cin>>n>>m;
    for(int i=1;i<=m;i++) vec[i].clear();
    for(int i=1;i<=n;i++){
        int l,r;cin>>l>>r;
        vec[r].push_back(l);
    } 
    for(int i=1;i<=m;i++) cin>>a[i];
    T.init();
    for(int i=1;i<=m;i++){
        ll ans=(i==1?0:T.ask(1,i-1));
        T.set(i,{a[i],ans});
        for(int j:vec[i]) T.modify(j,i,1);
    }
    cout<<T.ask(1,m)<<endl;
    return;
}
int main(){
    ios::sync_with_stdio(false);
    int _;cin>>_;
    while(_--) solve();
}