Home

# Cats Transport

# 题目大意

有 mm 只小猫要在 nn 个山丘上玩耍，雇佣了 pp 个人接它们回来，这些人均在 11 号山丘出发。山丘 ii 与山丘 i−1i-1 的距离是 DiD_i 米，每时刻人们走 11 米。
小猫 ii 会在山丘 HiH_i 玩耍，并在时间 TiT_i 结束它的游玩，然后在山丘上等着有人来接它。一个人在路过这个山丘时会把在等待的小猫带上（不需要额外的时间）。
我们需要安排每个人的出发时间，使小猫们的等待时间之和最小，输出这个最少的等待时间。

# 解题思路

计算出各只小猫被接到的出发时间 tit_i，然后我们对 tit_i 排个序，于是题意转化为了有 mm 只猫，每只猫有一个权值 tit_{i}，如果出发时间大于等于 tit_{i}，则可以接到第 ii 只猫。设出发时间为 xx，则接到第 ii 只猫时，这只猫会等待 x−tix-t_{i} 的时间。

我们设计状态 f[i][j]f[i][j] 表示 轮到第 ii 个人出发，这个人选择了第 jj 只猫的最小等待时间之和。暴力枚举上一个人选择的猫的做法的时间复杂度是 O(m2p)O(m^2p)。

记 s[k]=∑i=1kt[i]s[k] = \sum\limits_{i=1}^{k} t[i]，转移方程式如下：
f[i][j] = \max_{j,k}\left\

化简式子得到：
s[k]+f[i−1][k]=tjk−jtj+s[j]+f[i][j]s[k]+f[i−1][k]=t_jk−jt_j+s[j]+f[i][j]。
然后…… 斜率优化干他。

# Code

#define Aniciry Meteorshower_Y
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define long long long
using namespace std;
const int MAXN = 1e5+10;
int n, m, p, l, r, q[MAXN];
long h[MAXN], t[MAXN], d[MAXN];
long a[MAXN], sum[MAXN], f[2][MAXN];
inline auto X(int k) -> long;
inline auto Y(int k, int i) -> long;
inline auto slope(int a, int b, int i) -> double;
auto prework() -> void;
int main()
{
    scanf("%d%d%d", &n, &m, &p);
    for(int i = 2; i <= n; i += 1)
        scanf("%lld", &d[i]);
    for(int i = 1; i <= m; i += 1)
        scanf("%lld%lld", &h[i], &t[i]);
    prework();
    for(int i = 2, c = 0; i <= p; i += 1, c ^= 1)
    {
        q[1] = 0; l = r = 1;
        for(int j = 1; j <= m; j += 1)
        {
            while(l < r and slope(q[l], q[l+1], c) < a[j]) l += 1;
            f[c][j] = f[c^1][q[l]]+a[j]*(j-q[l])-(sum[j]-sum[q[l]]);
            while(l < r and slope(q[r-1], q[r], c) >= slope(q[r-1], j, c)) r -= 1;
            q[++r] = j;
        }
    }
    printf("%lld", f[p&1][m]);
}
auto prework() -> void
{
    for(int i = 1; i <= n; i += 1)
        d[i] += d[i-1];
    for(int i = 1; i <= m; i += 1)    
        a[i] = t[i]-d[h[i]];
    sort(a+1, a+m+1);
    for(int i = 1; i <= m; i += 1)
        sum[i] = sum[i-1]+a[i];
    for(int j = 1; j <= m; j += 1)
        f[1][j] = a[j]*j-sum[j];
}
inline auto X(int k) -> long{return k;}
inline auto Y(int k, int i) -> long{return f[i^1][k]+sum[k];}
inline auto slope(int a, int b, int i) -> double{return double(Y(b, i)-Y(a, i))/(X(b)-X(a));}

# Pairwise Modulo

# 题目描述

给定一个由不同数组成的序列 aia_i，定义 pkp_k 为：
pk=∑i=1k∑j=1k(ai mod aj)p_k = \sum\limits_{i=1}^k \sum\limits_{j=1}^k (a_i \bmod a_j)
对于每个 i∈[1,n]i \in [1,n]，求出 pip_i。

# 解题思路

需要求出每个 pkp_k，考虑增量法由上个答案推出当前答案：
pk=pk−1+∑i=1k(ai mod ak)+∑i=1k(ak mod ai)p_k = p_{k-1} + \sum\limits_{i=1}^{k}(a_i \bmod a_k) + \sum\limits_{i=1}^{k}(a_k \bmod a_i)

取模不好处理，将它转化为相减的形式：

pk=pk−1+∑i=1k(ai−⌊aiak⌋ak)+∑i=1k(ak−⌊akai⌋ai)p_k = p_{k-1} + \sum\limits_{i=1}^k \left( a_i - \lfloor \frac{a_i}{a_k} \rfloor a_k \right) + \sum\limits_{i=1}^k \left( a_k - \lfloor \frac{a_k}{a_i} \rfloor a_i \right)

把式子拆开得到：

pk=pk−1+∑i=1kak−ak∑i=1k⌊aiak⌋+kak−∑i=1k⌊akai⌋aip_k = p_{k-1} + \sum\limits_{i=1}^{k}a_k - a_k\sum\limits_{i=1}^k \lfloor \frac{a_i}{a_k} \rfloor + ka_k - \sum\limits_{i=1}^k \lfloor \frac{a_k}{a_i} \rfloor a_i

  1. 对于 ∑i=1k⌊aiak⌋Σ\sum\limits_{i=1}^k \lfloor \frac{a_i}{a_k} \rfloor\Sigma，直接枚举倍数就好，时间复杂度 O(nln⁡n)O(n \ln n).

  2. 对于 ∑i=1k⌊akai⌋ai\sum\limits_{i=1}^k \lfloor \frac{a_k}{a_i} \rfloor a_i，考虑每一组值相同的 ⌊akai⌋\lfloor \frac{a_k}{a_i} \rfloor 的贡献。区间加 和 前缀和维护一下。

# Code

#define Aniciry Meteorshower_Y
#include<iostream>
#include<cstdio>
#define lowbit(i) (i&-i)
using namespace std;
/* 此处省略快读快写 */
#define long long long
const int A = 300000;
const int MAXN = 3e5+10;
int n, a[MAXN]; long ans;
long tr1[MAXN], tr2[MAXN];
inline auto query1(int x) -> long;
inline auto query2(int x) -> long;
inline auto add1(int x, int k) -> void;
inline auto add2(int x, int k) -> void;
int main()
{
    read(n);
    for(int i = 1; i <= n; i += 1)
        read(a[i]);
    long sum = 0;
    for(int i = 1; i <= n; i += 1)
    {
        ans += sum; sum += a[i];
        for(int j = a[i]; j <= A; j += a[i])
            ans -= j*(query1(min(j+a[i]-1, A))-query1(j-1));
        add1(a[i], 1);
        ans += (i-1ll)*a[i]-query2(a[i]);
        for(int j = a[i]; j <= A; j += a[i]) add2(j, a[i]);
        print(ans, ' ');
    }
}
inline auto add1(int x, int k) -> void
{
    for(int i = x; i <= A; i += lowbit(i))
        tr1[i] += k;
}
inline auto add2(int x, int k) -> void
{
    for(int i = x; i <= A; i += lowbit(i))
        tr2[i] += k;
}
inline auto query1(int x) -> long
{
    long ans = 0;
    for(int i = x; i; i -= lowbit(i))
        ans += tr1[i];
    return ans;
}
inline auto query2(int x) -> long
{
    long ans = 0;
    for(int i = x; i; i -= lowbit(i))
        ans += tr2[i];
    return ans;
}

# Decinc Dividing

# 题目描述

定义一个序列 aia_i 是好的，仅当可以通过删除 aia_i 的一个单调递减子序列（可以为空）使得 aia_i 单调递增。
给定一个 1∼n1\sim n 的排列 pip_i，你需要求出 pip_i 中有多少子段是好的。

# 解题思路

首先，答案是单调的，对于一个合法区间 [l,r][l, r]，它的子区间一定合法；对于一个非法区间 [l,r][l, r]，包含它的区间一定非法。

对于每一个位置 ii，我们定义 rir_i 为最大的值满足区间 [i,ri][i, r_i] 合法。

考虑分治，对于区间 [l,r][l,r]，我们先求出 rlr_l 和 rrr_r，若 rl=rrr_l=r_r
，则将满足 l≤i≤rl\le i\le r 的 rir_i 都赋值为 rlr_l，否则设 mid=⌊l+r2⌋mid=\lfloor \frac{l+r}{2} \rfloor，并递归处理 [l,mid][l,mid] 和 [mid,r][mid,r]。最后的答案即为 (∑i=1nri)−n(n−1)2(\sum\limits_{i=1}^n r_i)-\frac{n(n-1)}{2}.

# Code

#define Aniciry Meteorshower_Y
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
using namespace std;
const int N = 2e5+10;
int n, a[N], f[N][2], rt[N];
long long ans;
auto calc(int x) -> void;
auto solve(int l, int r) -> void;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i += 1)
        scanf("%d", &a[i]);
    calc(1), calc(n); solve(1, n);
    for(int i = 1; i <= n; i += 1)
        ans += rt[i];
    printf("%lld", ans-n*(n-1ll)/2);
    return 0;
}
auto solve(int l, int r) -> void
{
    if(r-l <= 1) return ;
    if(rt[l] == rt[r])
    {
        for(int i = l; i <= r; i += 1) 
            rt[i] = rt[l]; return ;
    }
    int mid = (l+r)>>1; calc(mid);
    solve(l, mid); solve(mid, r);
}
auto calc(int x) -> void
{
    f[x][0] = n+1; f[x][1] = 0;
    for(int i = x+1; i <= n; i += 1)
    {
        f[i][0] = 0; f[i][1] = n+1;
        if(a[i-1] < a[i]) f[i][0] = f[i-1][0];
        if(a[i-1] > a[i]) f[i][1] = f[i-1][1];
        if(f[i-1][1] < a[i]) f[i][0] = max(f[i][0], a[i-1]);
        if(f[i-1][0] > a[i]) f[i][1] = min(f[i][1], a[i-1]);
        if(f[i][0] == 0 and f[i][1] == n+1) return (void)(rt[x] = i-1);
    }
    rt[x] = n;
}