2022-11-9总结

精神焕发

Description

给出一棵 $n$ 个点的树，点从 $1$ 至 $n$ 编号。每个点 $u$ 上有足够多瓶加血 $w_u$ 的药水，如果原来你的血量为 $x$*，那么喝下这瓶药水后你的血量会变为 $x+w_u$。

有 $q$ 次询问。每次询问给出数 $x$ 与两个点的编号 $s$、$t$。

这次询问中，你的初始血量为 $x$，一开始在 $s$，想要走到 $t$。每次走到一个点，你就会喝下这个点上的药水（一开始来到点 $s$ 时会喝下 $s$ 上的药水）。你可以多次经过一个点，每次经过时都会喝下一瓶这个点上的药水。如果某个时刻你的血量小于 $0$，那么你就死了。你想知道你是否可以在不死的情况下从 $s$ 走到 $t$。

更形式化地，你需要判断是否存在一个点的编号组成的序列 $p_{1 \dots k}$，满足：

• $p_1=s$，$p_k=t$；
• 对于任意 $i \in [1,k-1]$，树上的点 $p_i$ 与 $p_{i+1}$ 之间有一条边。
• 对于任意 $i \in [1,k]$，有 $x+\sum_{j=1}^i w_{p_j} \ge 0$。

$p$ 的长度 $k$ 可以由你决定，并且 $p$ 中可以存在相同的元素。

Input

输入的第一行包含两个数 $n$、$q$。

第二行包含 $n$ 个数 $w_{1..n}$。

接下来 $n-1$ 行，每行包含两个数 $u$、$v$，表示树中存在连接点 $u$ 与点 $v$ 的一条边。

接下来 $q$ 行，每行包含三个数 $x$、$s$、$t$，表示一组询问，保证 $s\neq t$。

Output

输出应包含 $q$ 行，第 $i$ 行包含一个字符串 Yes 或 No，表示第 $i$ 次询问的答案。

Hint

对于 $100\%$ 的数据，$1\le n, q\le 10^6$，$|w_i|\le10^9$，$0\le x\le 10^{18}$。

Solution

从 $s$ 到 $t$ 顶多只有两种方案：要么直接 rua 过去，要么找一个能反复横跳的地方无限加血。

无限加血的地方只能是一条两端点权值和 $>0$ 的边。

如果到达这样的边的任意一个端点，那么就可以获得无限血，把这样的点标记为无限血点。

我们可以通过树形 DP 求出每个点到无限血点最少需要多少初始血量。

直接 rua 过去需要判断树上路径的前缀和最小值，容易发现前缀和最小值是整个路径或者是整个路径除去 $t$ 点，否则路径上一定会有一个无限血点，所以这一部分直接判路径和就行。

时间复杂度取决于 LCA, 最优可以做到 $O(n+k)$。

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

typedef long long ll;
const int N = 1e6+10;

int n, q;
vector<int> ver[N];

namespace HLD {
    int fa[N], dep[N], siz[N];
    int big[N], top[N];
    ll val[N], dis[N], f[N];
    int tag[N];
    
    void dfs1(int x, int fa);
    void dfs2(int x, int fa);
    ll dist(int x, int y);
    bool have(int x, int y);
}
using namespace HLD;

signed main()
{
    read(n, q);
    for(int i = 1; i <= n; i++)
        read(val[i]);
    for(int i = 1; i < n; i++)
    {
        int a, b; read(a, b);
        ver[a].push_back(b);
        ver[b].push_back(a);
    }
    
    memset(f, 0x3f, sizeof(f));
    HLD::dfs1(1, 0);
    HLD::dfs2(1, 0);
    
    for(int i = 1; i <= q; i++)
    {
        ll x; int s, t; read(x, s, t);
        ll d = dist(s, t);
        if(val[t] > 0) d -= val[t];
        if(x >= f[s])
            print("Yes\n");
        else if(!have(s, t) and x >= -d)
            print("Yes\n");
        else
            print("No\n");
    }
}

namespace HLD {
    void dfs1(int x, int dad)
    {
        siz[x] = 1;
        fa[x] = dad;
        dep[x] = dep[dad]+1;
        dis[x] = dis[dad]+val[x];
        if(val[x]+val[dad] > 0)
        {
            tag[x] = tag[dad] = 1;
            f[x] = min(f[x], max(0ll, -val[x]));
            f[dad] = min(f[dad], max(0ll, -val[dad]));
        }
        for(auto y : ver[x])
        {
            if(y == dad) continue;
            dfs1(y, x); siz[x] += siz[y];
            if(siz[y] > siz[big[x]]) big[x] = y;
            f[x] = min(f[x], max(0ll, f[y]-val[x]));
        }
    }
    void dfs2(int x, int tp)
    {
        for(auto y : ver[x])
        {
            if(y == fa[x]) continue; 
            tag[y] += tag[x];
            f[y] = min(f[y], max(0ll, f[x]-val[y]));
        }
        top[x] = tp;
        if(big[x]) dfs2(big[x], tp);
        for(auto y : ver[x])
            if(y != big[x] and y != fa[x])
                dfs2(y, y);
    }
    int lca(int x, int y)
    {
        while(top[x] != top[y])
        {
            if(dep[top[x]] < dep[top[y]]) swap(x, y);
            x = fa[top[x]];
        }
        return dep[x] < dep[y] ? x : y;
    }
    ll dist(int x, int y)
    {
        int f = lca(x, y);
        return dis[x]+dis[y]-dis[f]-dis[fa[f]];
    }
    bool have(int x, int y)
    {
        int f = lca(x, y);
        return tag[x]+tag[y]-tag[f]-tag[fa[f]];
    }
}

顺逆序对

Description

对于一个 $1,\dots,n$ 的排列 $a_1,\dots,a_n$，定义 $i$ 处的顺序对数 $f(i)$ 为满足 $1\leq j<i$ 且 $a_j<a_i$ 的 $j$ 的数量，定义 $i$ 处的逆序对数 $g(i)$ 为满足 $i<j\leq n$ 且 $a_j<a_i$ 的 $j$ 的数量。

给定 $n$，对于每个 $k=0,1,\dots,n-1$，求出满足 $\max_{i=1}^n|f(i)-g(i)|=k$ 的 $a_1,\dots,a_n$ 的数量模 $10^9+7$ 的值。

Input

输入数据一行包含一个整数 $n$。

Output

输出一行 $n$ 个整数，分别表示 $k=0,1,\dots,n-1$ 时的答案，对 $10^9+7$ 取模。

Hint

对于 $100\%$ 的数据，$n\leq 10^6$。

Solution

先转化为对每个 $k = 0 \sim n-1$ 求出 $\max_{i=1}^n|f(i)-g(i)| \le k$ 的答案。

考虑从 $1 \sim n$ 依次插入，这样可以考虑到所有的排列。

假设已经插入了 $1 \sim n$，现在要插入 $i+1$，如果 $i+1$ 插在了第 $p$ 个数和第 $p+1$ 个数之间($0 \le p \le i$)，$i+1$ 最终对应的顺序对数为 $p$ ，逆序对数就是 $i-p$，我们只需要保证 $|p-(i-p)| \le k$ 即可。

记插入 $i+1$ 时满足条件的 $p$ 的数量为 $c(i)$，那么可以得到:

$$c(i) = \begin{cases} i+1, & i < k \\ k+[i \equiv k \pmod 2], & i \ge k \end{cases}$$

于是转化为对每个 $k$ 算 $\prod\limits_{i=0}^n c(i)$。

求完之后差分一下就是 $\max_{i=1}^n |f(i)-g(i)| = k$ 的答案。

对单个 $k$ 容易 $O(\log n)$ 计算，总时间复杂度 $O(n \log n)$。

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

typedef long long ll;
const int N = 1e6+10;
const int P = 1e9+7;

int n;
ll ans[N];
ll fact[N];

void prework(int n);
ll qpow(ll a, ll b);

int main()
{
    cin >> n;
    prework(n);
    for(int k = 0; k < n; k++)
    {
        ans[k] = fact[k];
        (ans[k] *= qpow(k+1, (n-k+1)/2)) %= P;
        (ans[k] *= qpow(k, (n-k)/2)) %= P;
    }
    for(int i = n-1; i > 0; i--)
        ans[i] = (ans[i]-ans[i-1]+P)%P;
    for(int i = 0; i < n; i++)
        cout << ans[i] << " ";
}

void prework(int n)
{
    fact[0] = 1;
    for(int i = 1; i <= n; i++)
        fact[i] = fact[i-1]*i%P;
}
ll qpow(ll a, ll b)
{
    ll ans = 1;
    for(; b; b >>= 1, a = a*a%P)
        if(b&1) ans = ans*a%P;
    return ans;
}

串串

Description

FAT 想要烫串串。

现在有一个长度为 $n$ 的字符串 $S$ 与一个长度为 $m$ 的字符串 $T$。

定义字符串 $S_i$ 表示将从 $S$ 的第 $i$ 个字符后断开得到 $A$，$B$，将 $B$ 从尾到头形成的字符串设为 $B'$，将 $B'$ 接在 $A$ 后面得到的字符串。

对于每个 $i$，FAT 想知道 $T$ 在 $S_i$ 中出现的次数。

Input

第一行包含一个字符串 $S$。

第二行包含一个字符串 $T$。

Output

输出 $n$ 行每行一个整数，第 $i$ 行的数表示 $T$ 在 $S_i$ 中出现的次数。

Hint

对于 $100\%$ 的数据，$1\le m \le n\le 2\times 10^6$。

Solution

$T$ 在 $Si=AB′$ 中的出现次数是 $T$ 在 $A$ 中的出现次数 + $T$ 在 $B'$ 中的出现次数 + $T$ 跨过 $A$ 和 $B′$ 的出现次数。

前两个很好处理，考虑最后一个。

$T$ 的一个后缀要与 $B′$ 的前缀匹配，剩余的前缀要与 $A$ 的后缀匹配。

可以先处理出所有跟 $B′$ 的前缀匹配的 $T$ 后缀，然后询问它们剩的前缀有多少个是 $A$ 的后缀。

可以建出 KMP 的 fail tree 解决。

时间复杂度 $O(n \log n)$。

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

const int N = 2e6+10;

int n, m;
char s[N], t[N];
int nxt[N], len[N];
int ans[N], suf[N];
int ldfn[N], rdfn[N], cnt;
vector<int> ver[N];

void dfs(int x);
void get_next(char *s, int *nxt);

namespace bit {
    int a[N];
    #define lowbit(i) (i&-i)
    void add(int x, int v) { for(; x <= cnt; x += lowbit(x)) a[x] += v; }
    int query(int x) { int ans = 0; for(; x >= 1; x -= lowbit(x)) ans += a[x]; return ans; }
}

int main()
{
    cin >> (s+1) >> (t+1);
    n = strlen(s+1);
    m = strlen(t+1);
    
    get_next(t, nxt);
    
    for(int i = 1, j = 0; i <= n; i++)
    {
        while(j and t[j+1] != s[i]) j = nxt[j];
        if(t[j+1] == s[i]) j++;
        len[i] = j;
        ans[i] = ans[i-1]+(j==m);
    }
    
    for(int i = 1; i <= m; i++)
        ver[nxt[i]].push_back(i);
    
    dfs(0);
    
    reverse(t+1, t+m+1);
    get_next(t, nxt);
    int j = 0;
    for(int i = 1; i <= n; i++)
    {
        while(j and t[j+1] != s[i]) j = nxt[j];
        if(t[j+1] == s[i]) j++;
        if(j == m) suf[i-m+1] = 1;
    }
    if(j == m) j = nxt[j];
    
    vector<int> f;
    for(; j; j = nxt[j])
        f.push_back(j);
    
    for(int i = n; i >= 1; i--)
    {
        while(!f.empty() and i+f.back() <= n)
        {
            bit::add(ldfn[m-f.back()], 1);
            bit::add(rdfn[m-f.back()]+1, -1);
            f.pop_back();
        }
        
        suf[i] += suf[i+1];
        ans[i] += bit::query(ldfn[len[i]]);
    }
    
    for(int i = 1; i <= n; i++)
        cout << ans[i]+suf[i+1] << "\n";
}

void dfs(int x)
{
    ldfn[x] = ++cnt;
    for(auto y : ver[x]) dfs(y);
    rdfn[x] = ++cnt;
}

void get_next(char *s, int *nxt)
{
    int n = strlen(s+1);
    nxt[1] = 0;
    for(int i = 2, j = 0; i <= n; i++)
    {
        while(j and s[j+1] != s[i]) j = nxt[j];
        if(s[j+1] == s[i]) j++;
        nxt[i] = j;
    }
}