NFLSHC集训Day1

· · 算法·理论

安排：

大概就是早八上课，下午做题，中午睡一下

今日大纲：

复习前缀和

前缀和思想和基本模型：

前缀和，顾名思义就是左边端点为1，右边端点不限（一维）的思想，多维前缀和在理论上也是可以实现的

一维前缀和请助手小李给个图例：

那么根据图例可以知道一维前缀和的递推公式为：

二维前缀和及多维前缀和也一样，小李给个图例： ![](https://cdn.luogu.com.cn/upload/image_hosting/vhrc4aep.png) 那么根据图例也可以知道，二维前缀和的递推公式为： $S[i][j]$ = $S[i - 1][j]$ + $S[i][j - 1]$ - $S[i-1][j-1]$ + $a[i][j]

三维前缀和需要画立方体，四维及以上小李也画不出来，而且比较麻烦，就不出示了

前缀和的局限性

前缀和有一个很大的要求，数组中的元素是改不了 的，有一个元素的改动对前缀和来说都是毁灭性打击，尤其是第一项

前缀和只能在有逆运算的情况下使用，你说求最大值这种东西没有逆运算，前缀和是无法完成的

差分的思想与应用：

小李可以放假了

差分在区间修改问题里非常常见，例如有数组a，那么差分数组b存储的就是a[i]和a[i - 1]的差值，所以在区间内统一进行加减时，因为同增同减差不变，所以区间内的差是没有变化的，不用改，而不使用差分时就要用循环改，事倍功半

差分的应用场景广泛，随便看一道，例如二维差分的“地毯覆盖”什么的，而且模型和前缀和差不了多少，都是容斥原理，小李你就可以退下了，不用画图

差分的局限性：

差分和前缀和最大的不同点在于前缀和改不了，但差分可以区间改，但是这两种算法都挺卡时间复杂度的，其实都可以用线段树解决 ，但是我不想，累

学习树上差分

经典例题

老师说的基础题，上链接：

Here

树上差分其实就是把差分思想用在树上，避免逐个暴力修改，使用DFS求差分数组的前缀和，就可以达到降低复杂度的目的，但前提是你得会做LCA（最近公共祖先）

教练：LCA你们不会有人不会背吧

我：你报我身份证号得了

int LCA(int x, int y)//这是LCA最常用的倍增算法
{
    if(depth[x] > depth[y]) swap(x, y);
    int t = depth[y] - depth[x];
    for(int i = 0; i < 18; i++)
    {
        if(t&(1<<i)) y = fa[y][i];
    }
    if(x == y) return x;
    for(int i = 17; ~i; i--)
    {
        if(fa[x][i] != fa[y][i])
        {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}

在此之前先讲一下LCA的倍增实现：

注意到u，v走到最近公共祖先之前，u，v所在结点不相同。

而到达最近公共祖先后，再往上走仍是u，v的公共祖先，即u，v走到同一个结点，这具有二分性质。

于是可以预处理出一个2k的表，

不妨假设$depth[u]$ < $depth[v]

①将 v 往上走 d = depth[v] - depth[u] 步，此时u，v所在结点深度相同，该过程可用二进制优化。

由于 d 是确定值，将 d 看成2的次方的和值， d = 2k1 + 2k2 + ... + 2km ，利用 fa 数组，如 v = fa[k1][v] ， v = fa[k2][v] 加速。

②若此时 u = v ，说明LCA已找到

③利用 fa 数组加速 u ， v 一起往上走到最近公共祖先的过程。

令 d = depth[u] - depth[w] ，虽然 d 是个未知值，但依然可以看成2的次方的和。

从高位到低位枚举 d 的二进制位，设最低位为第0位，若枚举到第k位，有 fa[k][u] != fa[k][v] ，则令 u = fa[k][u] ， v = fa[k][v] 。

最后，最近公共祖先为 fa[0][u] = fa[0][v]

接下来的DFS代码就好理解了，上链接：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 200100;
int n, fa[N][20];
int tag[N], depth[N];
struct edge
{
    int to;
    ll v1, v2;
};
ll ans = 0;
vector<edge> g[N];
void dfs(int u)
{
    for(edge e:g[u])
    {
        int v = e.to;
        if(v == fa[u][0]) continue;
        depth[v] = depth[u] + 1;
        fa[v][0] = u;
        dfs(v);
    }
}
void pre()
{
    for(int j = 1; j <= 17; j++)
    {
        for(int i = 1; i <= n; i++)
        {
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
        }
    }
}
void dfs2(int u)
{
    for(edge e:g[u])
    {
        int v = e.to;
        if(v == fa[u][0]) continue;
        dfs2(v);
        ans += min(e.v1 * tag[v], e.v2);
        tag[u] += tag[v];
    }
}
int LCA(int x, int y)
{
    if(depth[x] > depth[y]) swap(x, y);
    int t = depth[y] - depth[x];
    for(int i = 0; i < 18; i++)
    {
        if(t&(1<<i)) y = fa[y][i];
    }
    if(x == y) return x;
    for(int i = 17; ~i; i--)
    {
        if(fa[x][i] != fa[y][i])
        {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}

int main()
{
    int u, v;
    ll v1, v2;
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        cin >> u >> v >> v1 >> v2;
        g[u].push_back(edge{v, v1, v2});
        g[v].push_back(edge{u, v1, v2});
    }
    fa[1][0] = 0, depth[1] = 0;
    dfs(1);
    pre();
    for(int i = 1; i < n; i++)
    {
        int y = LCA(i, i + 1);
        tag[i]++; tag[y]--;
        tag[i + 1]++; tag[y]--;
    }
    dfs2(1);
    cout << ans;
    return 0;
}

这一题总结起来一句话新闻：

要加tag啊！在LCA的上方打-1的tag，在下方打+1的tag，由点化边更简单

倍增和ST表

小李我需要你

倍增的思想

话说倍增是什么东西，其实说白了就是跳石头，由一个大跳转变为多个小跳的过程，而每一次的转变都是2的k次方级别的

倍增有一些特点：

好算！只是O(nlogn)级别的，而且完全符合递推思想，每一种倍增问题都可以转变为 T[T[i][j-1]][j-1] 的形态，话说怎么有点像套娃呢？没关系，小李给图例：

倍增的应用场景也是很有限制的，主要有三点：规则是固定的，执行若干次；要找满足条件的最近项；终点未知

倍增的应用

前文说过的LCA，我不赘述了

以及一些老师给的经典例题：

P1

使用ST表预处理区间块的最值，支持O(1)查询。

把RMQ放进冰箱要多少步？两步：

1.先预处理 f[i][j] 

   for (int i = 2; i <= n; i++) //lg[i]记录i转成二进制的位数
        lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; i++) f[i][0] = a[i];
    for (int j = 1; j <= lg[n]; j++)
        for (int i = 1; i <= n - (1 << j) + 1; i++)
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
    }

2.再查询区间最值

    for (int x, y, i = 1; i <= m; i++) {
        cin >> x >> y;
        int l = lg[y - x + 1];
        cout << max(f[x][l], f[y - (1 << l) + 1][l]) << '\n';
    }

写完，AC代码记得背（数据太大不用快读过不去，这是板子）：

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m, x, y, a[N], lg[N], f[N][20];

int main()
{
    cin >> n >> m;
    lg[1] = 0;
    for(int i=2;i<=n;i++) 
    {
        lg[i]=lg[i>>1]+1;
    }
    for (int i=1;i<=n;i++) 
    {
        cin>>f[i][0];
    }
    for (int j=1;j<=lg[n];j++)
    {
        for (int i=1;i<=n-(1<<j)+1;i++)
        {
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
    for (int i=1;i<=m;i++)
    {
        cin>>x>>y; 
        int l=lg[y-x+1];
        cout<<max(f[x][l],f[y-(1<<l)+1][l])<<endl;
    }
}

P2

这题就是为了做倍增而做倍增，还套了差分，没啥意义，当板子练练手好了

如果 f[i][j] 表示从 i 进行 2j 次操作得到的数，则 f 是好预处理的。同时 i 的上界也是确定的，由于范围要求，故 log2(i) 不超过 20，即修改后的 i 不超过 2.1×1e6 。

代码连老师都没写，我也不放了

P3

这题要是用普通的圆环统计你不完了吗，来试一下在环上的倍增大跳，小李给个图例：

只能在向左或者向右的 len/2 个点中寻找（貌似不说也是这么干）。

可以发现有一个性质，一个区间内，一旦一个端点被固定下之后，这个区间内的最大值会随着区间的扩大而非严格单调递增，那么就找到这个区间的单调性了，现在多了一个二分可以选择。

维护区间最大值，看数据范围，可以用 ST 表进行维护。

现在就有了一种做法，确定一个位置，然后向前向后分别二分进行查找。

时间复杂度为 O(nlogn) 。

P4

我发现这题有图例，太好了

我看到好多人都用单调栈，但倍增也不错

不难发现，盘子溢出的水只会流到直径比它大的盘子里，但前提是体积之和要大于 V[i] ，利用倍增的思想求出从下往上第 j 个盘子往下流，流过2的i次方个盘子之后会停留在哪里

for(int i=1;i<=size;i++){//倍增万能公式
    for(int j=1;j<=m;j++){
        next[j][i]=next[next[j][i-1]][i-1];
    }
}

还是利用倍增的思想，求出从下往上第j个盘子流过2的i次方个盘子需要多少，最后处理询问，完结撒花

int need[N][M];//在万能公式上稍微改一下
void init_need(){
    for(int i=1;i<=m;i++)need[i][0]=c[i];
    for(int i=1;i<=size;i++){
        for(int j=1;j<=m;j++){
            need[j][i]=need[j][i-1]+need[next[j][i-1]][i-1];
        }
    }
}

最后就是老师带着我们写的标程

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100010;
const int M = 25;

inline void read(int &wh)
{
    wh=0;
    int f=1;
    char w=getchar();
    while(w<'0'||w>'9')
    {
      if(w=='-')f=-1;
      w=getchar();
    }
    while(w<='9'&&w>='0')
    {
      wh=wh*10+w-'0';
      w=getchar();
    }
    wh*=f;
    return;
}

int m,n,size,w[N],c[N];

int next[N][M];
struct node
{
  int number,data;
};
stack<node>sta;
void init_next()
{
    sta.push((node){0,1e18});
    for(int i=1;i<=m;i++)
    {
        while(!sta.empty()&&sta.top().data<=w[i])sta.pop();
        next[i][0]=sta.top().number;
        sta.push((node){i,w[i]});
    }
    while(!sta.empty())sta.pop();
    for(int i=1;i<=size;i++)
    {
        for(int j=1;j<=m;j++)
        {
            next[j][i]=next[next[j][i-1]][i-1];
        }
    }
}

int need[N][M];
void init_need()
{
    for(int i=1;i<=m;i++)need[i][0]=c[i];
    for(int i=1;i<=size;i++)
    {
        for(int j=1;j<=m;j++)
        {
            need[j][i]=need[j][i-1]+need[next[j][i-1]][i-1];
        }
    }
}

signed main()
{

    read(m);
    read(n);
    while((1<<size)-1<m)
    {
      size++;
      size--;
    }
    for(int i=1;i<=m;i++)
    {
        read(w[m-i+1]);
        read(c[m-i+1]);
    }
    init_next();
    init_need();
    while(n--)
    {
        int wh,th;
        read(wh);read(th);
        wh=m-wh+1;
        int now=0;
        for(int i=size;i>=0;i--)
        {
            if(now+need[wh][i]<th)
            {
                now+=need[wh][i];
                wh=next[wh][i];
            }
        }

        if(wh==0) printf("0\n");
        else printf("%lld\n",m-wh+1);
    }
    return 0;
}

其实快读我自己都不想写，但是为了时间复杂度我还是努力了

以及我发现的事