Dylan's Blog
0%

Posted on Edited on In

问题描述

给定长度为 $n$ 的序列：$a_1,a_2,…,a_n$，记为 $a[1:n]$。有 $q$ 个询问，每个询问给定两个数 $l,r$，求 $a[l:r]$ 中所有子序列的最小值之和。

输入

第一行包含两个整数 $n$ 和 $q$，分别代表序列长度和询问数。

接下来一行，包含 $n$ 个整数，第 $i$ 个整数为 $a_i$。

接下来 $q$ 行，每行包含两个整数 $l$ 和 $r$，代表一次询问。

输出

对于每次询问，输出一行，代表询问的答案。

思路

有一种比较直观的方法就是使用莫队，队中维护一个单调栈，并且记录栈中元素到前一个元素这段区间的答案。当插入元素时，更新单调栈，通过记录的信息可以比较容易的求出答案。

这题还有一个很妙的 Idea。考虑类似于上面莫队的方法，先处理出右端点为 $i$ 的所有 $a[l,i]$ 的最小值的和，记为 $pre_i$，再处理一个 $pre_i$ 的前缀和 $spre_i$，这样 $spre_i$ 即是 $a[1,i]$ 的答案。类似的再处理出 $suf_i$，表示所有左端点为 $i$ 的序列的最小值之和，以及 $ssuf_i$ 表示 $suf_i$ 的后缀和。

预处理完这些东西后，考虑如何回答区间 $a[l,r]$ 的答案，我们设 $a[l,r]$ 中最小值位于 $pos$，这个可以利用 ST 表求出。经过 $pos$ 这一点的所有区间对答案的贡献可以直接计算出来，考虑剩下 $a[l,pos-1]$ 及 $a[pos+1,r]$ 这两段的贡献如何计算。我们发现 $spre[r]-spre[pos]$ 就包含了 $a[pos+1,r]$ 这一段的答案和右端点在 $[pos+1,r]$ 左端点在 $[1,pos-1]$ 的区间最小值之和。而后面一部分由于跨过了 $pos$，它的贡献可以等价为 $(r-pos)*pre[pos]$，将它们相减就可以计算出 $a[pos+1,r]$ 的贡献，类似的可以同样计算出 $a[l,pos-1]$ 的贡献。

这样我们可以在 $O(1)$ 的时间内回答每一个询问，而算法复杂度的瓶颈在 $O(n \log n)$ 的 ST 表预处理上，而如果使用笛卡尔树或者用一些 $O(n)$ RMQ 的高级姿势，就可以在线性复杂度内完成这个操作。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 100005
#define P 998244353
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, q, top, a[MAXN], f[MAXN][20], sta[MAXN], Log[MAXN];
LL pre[MAXN], spre[MAXN], suf[MAXN], ssuf[MAXN];

int query(int x, int y)
{
    int k=Log[y-x+1];
    if(a[f[x][k]]<a[f[y-(1<<k)+1][k]]) return f[x][k];
    else return f[y-(1<<k)+1][k];
}

int main()
{
    scanf("%d%d", &n, &q);
    for(rint i=1; i<=n; ++i)
    {
        scanf("%d", &a[i]);
        f[i][0]=i;
    }
    for(rint i=1; i<20; ++i)
        for(rint j=1; j+(1<<i)-1<=n; ++j)
        {
            if(a[f[j][i-1]]<a[f[j+(1<<i-1)][i-1]]) f[j][i]=f[j][i-1];
            else f[j][i]=f[j+(1<<i-1)][i-1];
        }
    for(rint i=2; i<=n; ++i) Log[i]=Log[i/2]+1;
    sta[top=0]=0;
    for(rint i=1; i<=n; ++i)
    {
        while(top && a[sta[top]]>=a[i]) top--;
        pre[i]=pre[sta[top]]+1LL*a[i]*(i-sta[top]);
        sta[++top]=i;
        spre[i]=spre[i-1]+pre[i];
    }
    sta[top=0]=n+1;
    for(rint i=n; i>=1; --i)
    {
        while(top && a[sta[top]]>=a[i]) top--;
        suf[i]=suf[sta[top]]+1LL*(sta[top]-i)*a[i];
        sta[++top]=i;
        ssuf[i]=ssuf[i+1]+suf[i];
    }
    for(rint i=1, l, r; i<=q; ++i)
    {
        LL ans=0;
        scanf("%d%d", &l, &r);
        int pos=query(l, r);
        ans+=1LL*(pos-l+1)*(r-pos+1)*a[pos];
        ans+=ssuf[l]-ssuf[pos]-1LL*(pos-l)*suf[pos];
        ans+=spre[r]-spre[pos]-1LL*(r-pos)*pre[pos];
        printf("%lld\n", ans);
    }
    return 0;
}

Posted on Edited on In

分治FFT 1

已知函数 $g(x)$，且 $f(x),g(x)$ 存在如下关系，求 $f(x)$

可以利用 CDQ 分治的思想，将一段区间分为两半递归处理，并统计左半部分对右部分的贡献。具体地说，当我们要计算 $f(l \sim r)$ 时，先计算出 $f(l \sim mid)$ 的值，然后将这部分和 $g(1 \sim r-l)$ 卷积起来，就可以得到这部分对后半贡献。递归的边界应该是 $f(0)=1$，然后向上合并就可以计算出 $f(x)$ 的每一项，这样的复杂度是 $O(n \log^2 n)$ 的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void divide(int l, int r)
{
    if(l==r) return;
    int mid=(l+r)>>1, bit=0;
    divide(l, mid);
    while((1<<bit)<=((r-l+1)<<1)) bit++;
    for(rint i=0; i<(1<<bit); ++i)
    {
        pos[i]=(pos[i>>1]>>1)|((i&1)<<(bit-1));
        a[i]=b[i]=0;
    }
    for(rint i=l; i<=mid; ++i) a[i-l]=f[i];
    for(rint i=0; i<=r-l; ++i) b[i]=g[i];
    ntt(a, 1<<bit, 1), ntt(b, 1<<bit, 1);
    for(rint i=0; i<(1<<bit); ++i) a[i]=1LL*a[i]*b[i]%P;
    ntt(a, 1<<bit, -1);
    for(rint i=mid+1; i<=r; ++i) f[i]=add(f[i], a[i-l]);
    divide(mid+1, r);
}

分治FFT 2

对于给定数组 $a,b$，且 $f(x)$ 有如下形式，求 $f(x)$

可以利用分治的思想，将这个 $n+1$ 个多项式每次分为两部分，递归处理完后再将两部分合并。具体地说，当计算 $\prod_{i=l}^{r} (a_ix+b_i)$ 时，可以分别递归计算 $l \sim mid$ 和 $mid+1 \sim r$ 这两部分多项式的积，然后再用一遍 FFT 合并，这样复杂度也是 $O(n \log^2 n)$ 的。在一些情况下可以利用倍增的思想将复杂度优化至 $O(n \log n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
void divide(int a[], int l, int r)
{
    if(l==r) {a[0]=l, a[1]=1; return;}
    int mid=(l+r)>>1, bit=0;
    while((1<<bit)<=(r-l+1)) bit++;
    int b[(1<<bit)+5], c[(1<<bit)+5];
    for(rint i=0; i<1<<bit; ++i) b[i]=c[i]=0;
    divide(b, l, mid), divide(c, mid+1, r);
    for(rint i=0; i<1<<bit; ++i) pos[i]=(pos[i>>1]>>1)|((i&1)<<(bit-1));
    ntt(b, 1<<bit, 1), ntt(c, 1<<bit, 1);
    for(rint i=0; i<1<<bit; ++i) a[i]=1LL*b[i]*c[i]%P;
    ntt(a, 1<<bit, -1);
}

多项式求逆

如果多项式 $f(x),g(x)$ 满足如下关系，我们就记 $g(x)$ 为 $f(x)$ 的逆元。

我们可以递归地求解这个问题，首先考虑 $n=1$ 时，不妨设 $f(x) \equiv c \pmod x$，此时显然有 $f^{-1}(x)=c^{-1}$；

当 $n>1$ 时，我们假设 $f(x)$ 在 $\mod x^{\lceil \frac{n}{2} \rceil}$ 意义下的逆元 $g’(x)$ 已经求出，那么就有

根据定义可以知道

两式相减得到：

将左边的多项式平方后放在模 $x^n$ 意义下，这个多项式每一项可以写成原多项式的卷积，这个卷积的每一项一定包含一个原多项式的 $0 \sim \lceil \frac{n}{2} \rceil$ 次项，并且原多项式的 $0 \sim \lceil \frac{n}{2} \rceil$ 次项均为 $0$，所以这个 $n$ 次的多项式每一项也一定都为 $0$。即：

将两边同时乘上 $f(x)$ 后可以得到：

这样以来，我们就可以用 $O(n \log n)$ 的时间从 $g’(x)$ 推到 $g(x)$，根据主定理可以知道总时间复杂度依然为 $O(n \log n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void inv(int a[], int b[], int n)
{
    if(n==1) {b[0]=ksm(a[0], P-2); return;}
    inv(a, b, (n+1)>>1);
    int bit=0;
    while((1<<bit)<(n<<1)) bit++;
    for(rint i=0; i<(1<<bit); ++i) pos[i]=(pos[i>>1]>>1)|((i&1)<<(bit-1));
    for(rint i=0; i<n; ++i) c[i]=a[i];
    for(rint i=n; i<(1<<bit); ++i) c[i]=0;
    ntt(c, 1<<bit, 1), ntt(b, 1<<bit, 1);
    for(rint i=0; i<(1<<bit); ++i) b[i]=1LL*sub(2, 1LL*c[i]*b[i]%P)*b[i]%P;
    ntt(b, 1<<bit, -1);
    for(rint i=n; i<(1<<bit); ++i) b[i]=0;
}

Posted on Edited on In

问题描述

小A在平面上 $(0,0)$ 点的位置，第 $i$ 栋楼房可以用一条连接 $(i,0)$ 和 $(i,H_i)$ 的线段表示，其中 $Hi$为第 $i$ 栋楼房的高度。如果这栋楼房上任何一个高度大于 $0$ 的点与 $(0,0)$ 的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。

施工队的建造总共进行了 $M$ 天。初始时，所有楼房都还没有开始建造，它们的高度均为 $0$。在第 $i$ 天，建筑队将会将横坐标为 $X_i$ 的房屋的高度变为 $Y_i$ (高度可以比原来大—修建，也可以比原来小—拆除，甚至可以保持不变—建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后，他能看到多少栋楼房？

输入

第一行两个正整数 $N,M$

接下来 $M$ 行，每行两个正整数 $X_i,Y_i$

输出

$i$ 行一个整数表示第 $i$ 天过后小A能看到的楼房有多少栋

思路

如果从分块的角度入手，思路会比较简单。对于每一个块维护一个栈，栈内存放这一个块中能够看见的楼房（不考虑该块外部的楼房）。对于修改操作，直接将所在块的栈删去重构；对于询问操作，以前面的最大值在每一个栈中二分。当每一块大小为 $\sqrt{n \log size}$ 时，复杂度为 $n\sqrt{n\log size}$。

其实这个也可以用线段树维护。每一个节点维护区间最大值和该区间中的答案，考虑如果将两个区间的答案合并。左区间的答案肯定要全部算上，而右区间的答案就与左区间最大值有关，我们设这个值为 $val$。如果右区间的左子区间的最大值小于 $val$，显然这个区间的答案为 $0$，我们只需要递归计算右区间的答案；如果右区间的左子区间的最大值大于 $val$，那么原先右区间的贡献不会变，我们只需要递归计算左区间的答案。因此对于每一个区间都需要向下再递归 $\log n$ 层合并答案，那么总复杂度就是 $O(n\log^2 n)$。

代码

分块：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 100005
#define P 998244353
#define INF 0x3f3f3f3f
#define eps 1e-11
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, m, siz, bel[MAXN], top[400];
LD h[MAXN], sta[400][405];

int main()
{
    scanf("%d%d", &n, &m);
    siz=400;
    for(rint i=1; i<=n; ++i) bel[i]=(i-1)/siz+1;
    for(rint i=1, x, y; i<=m; ++i)
    {
        scanf("%d%d", &x, &y);
        int pos=bel[x], ans=0;
        top[pos]=0, h[x]=1.0*y/x;
        for(rint j=(pos-1)*siz+1; j<=pos*siz; ++j)
            if(h[j]>sta[pos][top[pos]]) sta[pos][++top[pos]]=h[j];
        LD maxn=0;
        /*
        for(rint j=1; j<=bel[n]; ++j)
        {
            printf("%d:", j);
            for(rint k=1; k<=top[j]; ++k) printf("%lf ", sta[j][k]);
            printf("\n");
        }
        */
        for(rint j=1; j<=bel[n]; ++j)
        {
            int l=1, r=top[j], p=top[j]+1;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(sta[j][mid]>maxn+eps) p=mid, r=mid-1;
                else l=mid+1;
            }
            ans+=top[j]-p+1;
            maxn=max(maxn, sta[j][top[j]]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

线段树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 100005
#define P 998244353
#define INF 0x3f3f3f3f
#define eps 1e-11
#define rint register int
#define LL long long
#define LD long double
#define ls (root<<1)
#define rs (root<<1|1)
#define mid ((l+r)>>1)
using namespace std;

int n, m, sum[MAXN*4];
LD maxn[MAXN*4];

int cal(int root, int l, int r, LD k)
{
    if(l==r) return maxn[root]>k;
    if(maxn[ls]>k) return cal(ls, l, mid, k)+sum[root]-sum[ls];
    else return cal(rs, mid+1, r, k);
}

void update(int root, int l, int r, int x, LD k)
{
    if(l==r)
    {
        sum[root]=1, maxn[root]=k;
        return;
    }
    if(x<=mid) update(ls, l, mid, x, k);
    else update(rs, mid+1, r, x, k);
    maxn[root]=max(maxn[ls], maxn[rs]);
    sum[root]=sum[ls]+cal(rs, mid+1, r, maxn[ls]);
}

int main()
{
    scanf("%d%d", &n, &m);
    for(rint i=1, x, y; i<=m; ++i)
    {
        scanf("%d%d", &x, &y);
        update(1, 1, n, x, 1.0*y/x);
        printf("%d\n", sum[1]);
    }
    return 0;
}

Posted on Edited on In

2 月 19 日 Educational Codeforces Round 60 比赛链接：https://codeforces.com/contest/1117

F - Crisp String

思路：

首先我们考虑删去哪些字符集是合法的。有一种很直观的做法就是枚举字符集，然后再用 $O(n)$ 判断是否合法，但这复杂度显然是不符合要求的。考虑统计非法的情况，可以对于每一个字母枚举与它产生矛盾的字符对，那么让这两个字母相邻的所有字符集都是非法的。这个的可以 $O(nq^2)$ 预处理，$(2^qq^2)$ 统计得到。

知道了那些字符集合法后，我们就需要计算出经过题目所给操作，能得到的答案最小的字符集。这个对合法字符集进行简单的 DP 即可得到。

代码链接

G - Recursive Queries

思路：

每一个询问其实要求的就是 $\sum_{i=l}^r(max(l_i, l)+min(r_i, r))$，$l,r$ 就是该询问的左右端点，$l_i,r_i$ 表示一个过点 $i$ 的一个极长区间，该区间的所有元素都小于等于 $p_i$。

发现这个东西不好维护，但我们可以换一个角度，考虑每个点对询问的贡献。那么对于询问 $l,r$，答案应该就是 $l \sim r$ 中每一个点对 $r$ 的贡献减去对 $l$ 的贡献之和。我们考虑点 $i$ 对于位置 $pos$ 的贡献，如果$pos < l_i$ 贡献为 $l_i$；如果$l_i < pos < r_i$ 贡献为 $pos$；如果$r_i < pos$ 贡献为 $r_i$。于是我们用线段树维护这个的和就可以在 $O(n \log n)$ 内得出答案。

代码链接

Posted on Edited on In

2 月 14 日 Codeforces Global Round 1 题目链接：https://codeforces.com/contest/1110

F - Nearest Leaf

思路：

考虑用线段树维护当前点到叶子节点的距离，那么对于询问就是查询区间最小值。我们从根节点开始，按照 dfs 序依次维护在每一个点上的线段树。当从点 $x$ 走到点 $son_x$ 且边权为 $dis$ 时，$son_x$ 子树内点的距离减少了 $dis$，其余点点距离增加了 $dis$，由于一棵子树的 dfs 序是连续的，因此就对应于线段树的区间修改。

代码链接

G - Tree-Tac-Toe

思路：

首先发现黑色是不可能赢的。为了简化情况，我们先假设所有点都是没有涂色的，然后考虑有哪些情况白色必定赢。比较简单的一种就是存在度数大于 4 的节点，然后发现如果一个点度数为 3 且有两个相邻的非叶节点时，白色也同样必胜。排除掉这两种情况后，剩下的树的形态就比较简单了。如下图一样，就是中间一条长链，两端可能会有度数为 3 的点，当然也可能没有度数为3的点。

Tree-Tac-Toe 1

然后考虑这种情况下白色怎样才能获胜，可以发现只有两端都有度数为 3 的端点且链长为偶数时，白色才能获胜。然后其余的所有情况都会是平局。

如果一开始树上有些点已经是白色了，考虑如何处理这种情况。比较巧妙的方式就是将一个白点按照下图的方式，拆成 4 个无色的点，可以发现这两种是完全等价的。然后就按照开始所讲的情况进行讨论即可。

Tree-Tac-Toe 2

代码链接