Dylan's Blog

AtCoder Grand Contest 030 解题报告

Posted on 2019-01-01 Edited on 2022-06-05 In 解题报告

12 月 29 日 AtCoder Grand Contest 030 比赛链接：https://atcoder.jp/contests/agc030

C - Coloring Torus

思路： 如果当 $k$ 为 $4$ 的倍数时，有一种简单粗暴的方法就是奇数列填 $1 \sim k/2$ 偶数列填 $k/2+1 \sim k$，这显然是满足要求的，但因为这种方法每个数它左右两边都一样，可扩展性不强。我们可以在这个的基础上稍加变化，就是把第 $i$ 列向后移 $i$ 个，形式化的说就是：

对于奇数行 $col_{i,j} = (i+j)\mod k/2$ 对于偶数行 $col_{i,j} = (i+j)\mod k/2 +k/2$

这样构造出来的矩阵就有很好性质，对于每个数不光它上下两个数是它的 $+1$ 和 $-1$，而且它左右两个数是它的 $k/2+1$ 和 $k/2-1$。因此很自然的可以想到如果 $k$ 不是 $4$ 的倍数时，设 $n$ 为 $\lceil \frac{k}{4} \rceil * 4$，然后将多出来的 $n-k$ 个数都减去 $n/2$。因为上面提到的性质，减去 $n/2$ 后可以看成将它上下两个数与左右两个数交换，这样依旧可以保证满足题目要求

代码链接

D - Inversion Sum

思路： 先把计数转化为求期望，我们设 $f_{i,j}$ 为 $A_i>A_j$ 的概率。可以发现每一次操作会改变 $O(n)$ 个 $f_{i,j}$ 的值，因此可以直接在对应的值上面修改即可。

代码链接

E - Less than 3

思路： 如果在 $01$ 之间画上蓝线，在 $10$ 之间画上蓝线，可以发现我们的每一次操作就是将一根线向左或向右移。且红线和蓝线之间的距离不超过 $3$，红线蓝线交替出现，串的左右两段有无数条线。而我们要做的就是把第一个串的线与第二个串对应起来，因此就枚举第二个串的第一根线对应于第一个串的那一根线，然后这种情况的答案就是确定的且可以 $O(n)$ 计算出来。

代码链接

F - Permutation and Minimum

思路： 有一个脑洞很大的 $DP$，从大到小考虑每一个数，设 $f_{i,j,k}$ 为考虑数 $i$ 时，有 $j$ 没有配对的确定的数，有 $k$ 个没有配对的 $-1$ 且。接下来考虑转移：

如果数 $i$ 确定且和它一对的另一个数也确定，那么它不会对答案产生影响，有 $f_{i,j,k}=f_{i+1,j,k}$ 如果数 $i$ 确定且和它一对的另一个数是 $-1$，那么它可以不配对，有 $f_{i,j,k}=f_{i+1,j-1,k}$；这个它可以和一个 $-1$ 配对，有 $f_{i+1,j,k+1}$ 如果数 $i$ 不确定，那么它可以不配对，有 $f_{i,j,k}=f_{i+1,j,k+1}$；它也可以和一个 $-1$ 配对，有 $f_{i,j,k}=f_{i+1,j,k+1}$；它还可以和一个确定的数配对，有 $f_{i,j,k}=(j+1)*f_{i+1,j+1,k}$

我们想这个 DP 的系数是怎么来的，如果两个 $-1$ 配对我们可以先把所有的 $-1$ 看成没有区别的，系数就为 $1$，最后乘上这样配对数的阶乘;如果一个 $-1$ 和一个确定的数配对，那么它可以有 $j+1$ 种选择，系数就是 $j+1$。

代码链接

后缀自动机小结

Posted on 2018-12-31 Edited on 2022-06-05 In 学习小结

结束位置集与状态

结束位置集：

对于 $S$ 的一个子串 $t$，我们将 $S$ 中 $t$ 的所有结束位置叫做一个结束位置集，记为 $endpos(t)$。

状态：

我们将 $ S$ 的子串按照 $endpos$ 几何被分为若干个等价类，每一个等价类就对应于后缀自动机的一个状态。

性质：

我们设 $len(t_1)<=len(t_2)$，那么 $t_1$ 是 $t_2$ 的后缀当且仅当 $endpos(t_2) \subseteq endpos(t_1)$，$t_1$ 不是 $t_2$ 的后缀当且仅当 $endpos(t_1)\bigcap endpos(t_2)=\emptyset$。

一个状态所对应的所有子串，其中短的子串一定是长的子串的一个后缀，且子串的长度是连续的。也就是说，一个状态对应的所有子串，都是其中最长子串的一系列连续后缀。

后缀链接

定义：

我们考虑 $S$ 的一个前缀 $S[1,2,…,i]$，它会有 $i$ 个连续的后缀，这组连续的后缀可能会在中间若干个地方「断掉」并分为若干段，其中每一段的连续后缀都对应一个状态。我们可以用一个叫后缀链接的东西把这若干段链接起来。

后缀链接不属于DFA（有限状态自动机）的一部分，由于它奇妙的性质和强大的功能，构造 SAM 时会需要后缀链接。

性质：

所有后缀链接构成一棵根节点为 $t_0$（初始状态）的树。后缀链接构成的树本质上是 $endpos$ 集合构成的一棵树，树的边表示 $endpos$ 集合的包含关系。

构造算法

我们先用一个结构体来储存一个状态内的信息。其中 $len$ 该为对应子串的最长长度，$fa$ 为该状态的后缀链接，$next$ 为该状态的转移。

1	struct State {int len, fa, next[26]...;} st[MAXN*2];

假设我们构造好了 $S[1,2,..,i]$ 的SAM，并向其中添加字符 $s[i+1]$，那么我们就要对 $S[1,2,..,i]$ 所有后缀所对应的状态增加相应的转移，并且可以发现所有这些状态都被一条后缀链接构成的路径连接到初始状态上。我们只需要新建一个状态 $cur$，并对这条路径上的状态增加相应的转移就好。这个转移一共有三种情况：

1	int cur=++tot; st[cur].len=st[last].len+1;

先考虑最简单的情况，就是路径上的所有状态都没有 $s[i+1]$ 的转移。在这种情况下只要简单地把路径上的状态增加一个 $s[i+1]$ 的转移并指向状态 $cur$，再将 $cur$ 的后缀链接连向初始状态。

1 2	for(; p && !st[p].next[c]; p=st[p].fa) st[p].next[c]=cur; if(!p) st[cur].fa=1;

再考虑第二种情况，路径上有一个状态 $p$ 有 $s[i+1]$ 的转移，设这个转移指向状态 $q$，且 $q$ 的 $len$ 等于 $p$ 的 $len+1$，也就是说 $q$ 对应的最长子串是 $p$ 对应的最长子串加 $s[i+1]$。这样我们只要把 $p$ 之前的状态增加一个 $s[i+1]$ 的转移并指向状态 $cur$，再将 $cur$ 的后缀链接连向 $q$。

1 2	int q=st[p].next[c]; if(st[p].len+1==st[q].len) st[cur].fa=q;

最后考虑最复杂的一种情况，路径上有一个状态 $p$ 有 $s[i+1]$ 的转移，设这个转移指向状态 $q$，但 $q$ 的 $len$ 不等于 $p$ 的 $len+1$，也就是说 $q$ 对应的最长子串不是 $p$ 对应的最长子串加 $s[i+1]$。这里我们要将状态 $q$ 分裂开，新建一份 $q$ 的拷贝 $t$，令 $t$ 状态对应的最长子串为 $p$ 对应的最长子串加 $s[i+1]$ 且令 $p$ 之后的状态的 $s[i+1]$ 转移指向的状态由 $q$ 变为 $t$，最后，将状态 $q$ 和 $cur$ 的后缀链接指向 $t$。

int t=++tot;
st[t].len=st[p].len+1;
memcpy(st[t].next, st[q].next, sizeof(st[q].next));
st[t].fa=st[q].fa;
for(; p && st[p].next[c]==q; p=st[p].fa) st[p].next[c]=t;
st[q].fa=st[cur].fa=t;

最终代码

int len, tot=1, last=1;
char s[MAXN];

struct State {int len, fa, next[26];} st[MAXN*2];

void insert(int c)
{
    int cur=++tot, p=last;
    st[cur].len=st[last].len+1;
    for(; p && !st[p].next[c]; p=st[p].fa) st[p].next[c]=cur;
    if(!p) st[cur].fa=1;
    else
    {
        int q=st[p].next[c];
        if(st[p].len+1==st[q].len) st[cur].fa=q;
        else
        {
            int t=++tot;
            st[t].len=st[p].len+1;
            memcpy(st[t].next, st[q].next, sizeof(st[q].next));
            st[t].fa=st[q].fa;
            for(; p && st[p].next[c]==q; p=st[p].fa) st[p].next[c]=t;
            st[q].fa=st[cur].fa=t;
        }
    }
    last=cur;
}

int main()
{
    scanf("%s", s+1);
    len=strlen(s+1);
    for(rint i=1; i<=len; ++i) insert(s[i]-'a');
    /*
    进行操作
    */
    return 0;
}

例题

1.hihocoder1445 重复旋律5

代码链接

2.hihocoder1457 重复旋律7

代码链接

3.BZOJ3998 弦论

代码链接

4.hihocoder1465 重复旋律8

代码链接

5.BZOJ4566 找相同字符

代码链接

6.hihocoder1449 重复旋律6

代码链接

7.BZOJ2882 工艺

代码链接

8.hihocoder1449 重复旋律9

代码链接

快速傅里叶变换小结

Posted on 2018-12-30 Edited on 2022-06-05 In 学习小结

离散傅里叶变换

定义：

是将 $\omega_n^1,\omega_n^2,…,\omega_n^n$ 带入多项式所得到的一种特殊的多项式点值表示

性质：

考虑将 $A(x)$ 的每一项按下标的奇偶分成两个多项式之和：

$A(x) = (a_0 + a_2x^2 + … + a_{n - 2}x^{n - 2}) + (a_1x + a_3x^3 + … + a_{n-1}x^{n-1})$

如果设：

$A_1(x) = a_0 + a_2x + … + a_{n - 2}x^{\frac{n}{2} - 1}$

$A_2(x) = a_1 + a_3x + … + a_{n - 1}x^{\frac{n}{2} - 1}$

那么：

$A(x) = A_1(x^2) + xA_2(x^2)$

于是我们把 $x = \omega_n^k$ 带入$A(x)$：

当 $k\subseteq \lbrace 0,1,2,… ,\frac{n}{2}-1\rbrace $ 时：

$A(\omega_{n}^{k})=A_1(\omega_{\frac{n}{2}}^{k}) + \omega_n^kA_2(\omega_{\frac{n}{2}}^{k})$

$A(\omega_{n}^{k+\frac{n}{2}})=A_1(\omega_{\frac{n}{2}}^{k}) - \omega_n^kA_2(\omega_{\frac{n}{2}}^{k})$

这样如果我们知道了 $A_1(x),A_2(x)$ 的离散傅里叶变换表示就可以 $O(n)$ 地求出 $A(x)$ 的离散傅里叶变换。

快速傅里叶变换

根据上面所提的离散傅里叶变换的性质，我们就可以递归地在 $O(nlogn)$的时间内将多项式的系数表示转换为点值表示。下面就介绍一下优化和实现上的细节：

蝴蝶操作：

有一个很神奇的性质：将一个多项式按下标的奇偶分为两部分，并将奇数部分放在偶数部分之后，然后不断递归下去。那么多项式下标为 $i$ 的数在这个操作之后的下标就变成了「将 $i$ 二进制翻转所得的数」。

1	for(rint i=0; i<lim; ++i) pos[i]=(pos[i>>1]>>1)\|((i&1)<<(l-1));

根据这个性质，我们可以先预处理出多项式中每个数操作之后的位置，并将它放到这个位置。然后类似于递归时回溯的操作，不断向上还原求出点值表示。

for(rint i=0; i<lim; ++i)
    if(i<pos[i]) swap(a[i], a[pos[i]]);
for(rint i=1; i<lim; i<<=1)
{
    Complex del(cos(PI/i), sin(PI/i));
    for(rint j=0; j<lim; j+=(i<<1))
    {
        Complex t(1, 0);
        for(rint k=0; k<i; ++k, t=t*del)
        {
            Complex x=a[j+k], y=t*a[j+k+i];
            a[j+k]=x+y; a[j+k+i]=x-y;
        }
    }
}

傅里叶逆变换

按照上述方法我们在 $O(nlogn)$ 内将多项式的系数表示转换成了点值表示，然后我们在 $O(n)$ 的时间内将两个多项式的点值表示相乘，得到了乘积的点值表示。利用傅里叶逆变换就可以同样在 $O(nlogn)$ 内将点值表示转换成系数表示。

离散傅里叶变换的另一个性质：把多项式 $A(x)$ 的离散傅里叶变换作为另一个多项式 $B(x)$ 的系数，并将 $\omega_{n}^{0}, \omega_{n}^{-1}, \omega_{n}^{-2}, …, \omega_{n}^{-(n - 1)}$ 代入多项式 $B(x)$ ，得到的每个数除 $n$，这样的 $n$ 个数就恰好是多项式 $A(x)$ 的系数。

根据上面的性质，我们在求离散傅里叶变换的代码上稍作修改，就能在 $O(nlogn)$ 内将点值表示转换成系数表示。

最终代码

下面是用 FFT 优化的高精度乘法代码（BZOJ2179）

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 200005
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

const double PI=acos(-1);

int n, m, len, pos[MAXN], ans[MAXN];
char sa[MAXN], sb[MAXN];

struct CP
{
    double x, y;
    CP(double a=0, double b=0)
    {
        x=a; y=b;
    }
    friend CP operator * (CP a, CP b)
    {
        return CP(a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x);
    }
    friend CP operator + (CP a, CP b)
    {
        return CP(a.x+b.x, a.y+b.y);
    }
    friend CP operator - (CP a, CP b)
    {
        return CP(a.x-b.x, a.y-b.y);
    }
} a[MAXN], b[MAXN];

void fft(CP a[], int op)
{
    for(rint i=0; i<n; ++i)
        if(i<pos[i]) swap(a[i], a[pos[i]]);
    for(rint i=1; i<n; i<<=1)
    {
        CP omg(cos(PI/i), op*sin(PI/i));
        for(rint j=0; j<n; j+=(i<<1))
        {
            CP t(1, 0);
            for(rint k=0; k<i; ++k, t=t*omg)
            {
                CP x=a[j+k], y=t*a[j+k+i];
                a[j+k]=x+y; a[j+k+i]=x-y;
            }
        }
    }
}

int main()
{
    scanf("%d", &len);
    scanf("%s%s", sa, sb);
    for(rint i=0; i<len; ++i)
    {
        a[i].x=sa[len-1-i]-'0';
        b[i].x=sb[len-1-i]-'0';
    }
    for(n=1; n<(len*2); ) n<<=1, m++;
    for(rint i=0; i<=n; ++i) pos[i]=(pos[i>>1]>>1)|((i&1)<<(m-1));
    fft(a, 1);
    fft(b, 1);
    for(rint i=0; i<n; ++i) a[i]=a[i]*b[i];
    fft(a, -1);
    for(rint i=0; i<n; ++i)
    {
        ans[i]+=(int)(a[i].x/n+0.5);
        ans[i+1]+=ans[i]/10;
        ans[i]%=10;
    }
    len=len*2-1;
    while(!ans[len] && len>=1) len--;
    for(rint i=len; i>=0; i--) printf("%d", ans[i]);
    return 0;
}

例题

1.BZOJ3771 Triple 2.BZOJ4259 残缺的字符串 3.AGC005F Many Easy Problems

计算几何小结

Posted on 2018-12-26 Edited on 2022-06-05 In 学习小结

刚接触一点计算几何，就把一些知识点记录在这里，后面会不断补充。

一、点向量

这两个东西都可以用一对 double 来表示且运算基本相同，于是就放在一起。

0.储存

struct Vector
{
    int x, y;
    Vector(int _x, int _y) {x=_x, y=_y;}
};

1.加

Vector add(Vector a, Vector b)
{
    return Vector(a.x+b.x, a.y+b.y);
}

2.减

Vector add(Vector a, Vector b)
{
    return Vector(a.x+b.x, a.y+b.y);
}

3.点积

double dot(Vector a, Vector b)
{
    return a.x*b.x+a.y*b.y;
}

4.叉积

double cross(Vector a, Vector b)
{
    return a.x*b.y-a.y*b.x;
}

二、线段

0.储存

struct Line
{
    int k, b;
    int cal(int x) {return k * x + b;}
};

1.跨立实验

2.李超线段树 算法：用线段树标记永久化维护平面内线段覆盖情况

//维护线段的下凸壳
void insert(int &root, int l, int r, Line x) //插入线段
{
    if (!root) {t[root = ++tot] = x; return;}
    int lx=x.cal(l), rx=x.cal(r), ly=t[root].cal(l), ry=t[root].cal(r);
    if(lx<=ly && rx<=ry) {t[root]=x; return;}
    if(lx>ly && rx>ry) return;
    double p = 1.0 * (t[root].b - x.b) / (x.k - t[root].k);
    if(lx<ly)
    {
        if(p<=mid) insert(ls[root], l, mid, x);
        else insert(rs[root], mid+1, r, t[root]), t[root]=x;
    }
    else
    {
        if(p<=mid) insert(ls[root], l, mid, t[root]), t[root]=x;
        else insert(rs[root], mid+1, r, x);
    }
}

int query(int root, int l, int r, int x) //询问下凸壳纵坐标
{
    int temp = INF;
    if (root) temp = t[root].cal(x);
    if (l == r) return temp;
    if (x <= mid) temp = min(temp, query(ls[root], l, mid, x));
    else temp = min(temp, query(rs[root], mid + 1, r, x));
    return temp;
}

三、多边形

1.多边形面积 算法：取一点进行三角形剖分，然后用叉积求出三角形面积

double area()
{
    double ans=0;
    for(rint i=2; i<=n; ++i) ans+=cross(con[i-1], con[i])/2;
    return ans;
}

2.凸包 性质：所有邻边的叉积符号相同算法：Graham扫描法

void Graham()
{
    sta[++top]=con[1];
    for(rint i=2; i<=n; ++i)
    {
        while(top>1 && cross(sub(con[i], sta[top]), sub(sta[top-1], sta[top]))<=0) top--;
        sta[++top]=con[i];
    }
    int lim=top;
    for(rint i=n; i>=1; --i)
    {
        while(top>lim && cross(sub(con[i], sta[top]), sub(sta[top-1], sta[top]))<=0) top--;
        sta[++top]=con[i];
    }
}

Educational Codeforces Round 56

Posted on 2018-12-21 Edited on 2022-06-05 In 解题报告

11月15日 Educational Codeforces Round 56 题目链接：https://codeforces.com/contest/1093

D - Beautiful Graph

思路： 一个简单的计数题。

首先根据题意可以得知，一条边两端的奇偶性一定要是不同的，因此只有二分图是存在可行方案的。考虑计数，先二分图染色（假设染成黑白两色），那么对于每一个连通块可行的方案就是 $2^{白色点数}+2^{黑色点数}$，然后总方案就是每个连通块方案的乘积。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 300005
#define p 998244353
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int T, n, m, ans, num, tot, cnt, head[MAXN], col[MAXN], Pow[MAXN];

struct Edge {int next, to;} edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

int ksm(int x, int y)
{
    LL sum=1;
    while(y)
    {
        if(y&1) sum=1LL*sum*x%p;
        x=1LL*x*x%p; y>>=1;
    }
    return sum;
}

bool dfs(int x, int color)
{
    col[x]=color; tot++;
    if(color==0) num++;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(col[to]==-1)
        {
            if(!dfs(to, 1-color)) return false;
        }
        else if(col[to]==col[x]) return false;
    }
    return true;
}

void solve()
{
    cnt=0; ans=1;
    scanf("%d%d", &n, &m);
    for(rint i=1; i<=n; i++) head[i]=0, col[i]=-1;
    for(rint i=1; i<=m; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    for(rint i=1; i<=n; ++i)
    {
        if(col[i]>=0) continue;
        tot=num=0;
        if(dfs(i, 0)) ans=1LL*ans*(Pow[num]+Pow[tot-num])%p;
        else {printf("0\n"); return ;}
    }
    printf("%d\n", ans);
}

int main()
{
    scanf("%d", &T);
    Pow[0]=1;
    for(rint i=1; i<=300000; ++i) Pow[i]=Pow[i-1]*2%p;
    while(T--) solve();
    return 0;
}

E -Intersection of Permutations

思路： E 题就是个这么毒瘤的数据结构。。正解似乎是树套树，但是 CDQ 显然能做。

先可以将问题转化一下，处理出数组 $b$ 中的数字在数组 $a$ 中的位置记为数组 $c$，那么询问操作就是询问 $c[lb~rb]$ 中有多少个数的值在 $la~ra$ 内。这是一个二维数点问题，可以使用树状数组维护，由于有修改操作，那么就用 CDQ 基于时间一维进行分治就好了。时间复杂度也是 $O((n+m)log^2n)$。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 200005
#define MAXM
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, m, cnt, a[MAXN], b[MAXN], pos[MAXN], t[MAXN], ans[MAXN];

struct Act
{
    int id, x, y, val;
    Act(int a=0, int b=0, int c=0, int d=0)
    {
        id=a; x=b; y=c; val=d;
    }
} act[MAXN*5], temp[MAXN*5];

bool CMP(Act x, Act y)
{
    return x.x<y.x;
}

void add(int x, int y)
{
    for(; x<=200001; x+=(x&-x)) t[x]+=y;
}

int ask(int x)
{
    int sum=0;
    for(; x; x-=(x&-x)) sum+=t[x];
    return sum;
}

void cdq(int l, int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l, mid); cdq(mid+1, r);
    int L=l, R=mid+1;
    for(; R<=r; ++R)
    {
        if(!act[R].id) continue;
        while(act[L].x<=act[R].x && L<=mid)
        {
            if(!act[L].id) add(act[L].y, act[L].val);
            L++;
        }
        ans[act[R].id]+=act[R].val*ask(act[R].y);
    }
    for(int i=l; i<L; i++)
        if(!act[i].id) add(act[i].y, -act[i].val);
    merge(act+l, act+mid+1, act+mid+1, act+r+1, temp+l, CMP);
    for(int i=l; i<=r; i++) act[i]=temp[i];
}


int main()
{
    memset(ans, -1, sizeof(ans));
    scanf("%d%d", &n, &m);
    for(rint i=1; i<=n; ++i)
    {
        scanf("%d", &a[i]);
        pos[a[i]]=i;
    }
    for(rint i=1; i<=n; ++i)
    {
        scanf("%d", &b[i]);
        act[++cnt]=Act(0, i+1, pos[b[i]]+1, 1);
    }
    for(rint i=1; i<=m; ++i)
    {
        int op, la, ra, lb, rb, x, y;
        scanf("%d", &op);
        if(op==1)
        {
            ans[i]=0;
            scanf("%d%d%d%d", &la, &ra, &lb, &rb);
            act[++cnt]=Act(i, lb, la, 1);
            act[++cnt]=Act(i, lb, ra+1, -1);
            act[++cnt]=Act(i, rb+1, la, -1);
            act[++cnt]=Act(i, rb+1, ra+1, 1);
        }
        else
        {
            scanf("%d%d", &x, &y);
            act[++cnt]=Act(0, x+1, pos[b[x]]+1, -1);
            act[++cnt]=Act(0, y+1, pos[b[y]]+1, -1);
            swap(b[x], b[y]);
            act[++cnt]=Act(0, x+1, pos[b[x]]+1, 1);
            act[++cnt]=Act(0, y+1, pos[b[y]]+1, 1);
        }
    }
    cdq(1, cnt);
    for(int i=1; i<=m; i++)
        if(ans[i]!=-1) printf("%d\n", ans[i]);
}

F - Vasya and Array

思路： 是一个很有趣的 DP。

如果不考虑限制可以得到转移：$f[i][j]=\sum_{x=1}^{k} f[i-1][x]$，其中如果 $a[i]=-1$ 那么 $j$ 可以取 $1~k$ 所有数，否则 $j$ 只能取 j。接下来就是要把不合法的状态减去，我们记录一个数组 $pre[i]$ 表示从下标 $pre[i]$ 开始全可以取数字 $i$，由此我们就可以判断一个状态是否合法。如果数字 $j$ 在位置 $i$ 上不合法，那么我们就应该减去 $\sum_{x!=j} f[i-len][x]$。

代码：

#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, k, len, ans, a[MAXN], f[MAXN][105], pre[105], sum[MAXN];

void add(int &x, int y)
{
    x=(x+y>=p)?x+y-p:x+y;
}

int main()
{
    scanf("%d%d%d", &n, &k, &len);
    for(rint i=1; i<=n; ++i) scanf("%d", &a[i]);
    memset(pre, -1, sizeof(pre));
    sum[0]=1;
    for(rint i=1; i<=n; ++i)
    {
        if(a[i]!=-1)
        {
            f[i][a[i]]=(i==1)?1:sum[i-1];
            for(rint j=1; j<=k; ++j)
            {
                if(j!=a[i]) pre[j]=-1;
                else if(pre[j]==-1) pre[j]=i;
            }
            if(pre[a[i]]!=-1 && i-pre[a[i]]+1>=len)
                add(f[i][a[i]], p-sum[i-len]), add(f[i][a[i]], f[i-len][a[i]]);
                //f[i][a[i]]=(f[i][a[i]]-sum[i-len]+f[i-len][a[i]]+p)%p;
        }
        else
        {
            for(rint j=1; j<=k; ++j)
            {
                if(pre[j]==-1) pre[j]=i;
                f[i][j]=(i==1)?1:sum[i-1];
            }

            for(rint j=1; j<=k; ++j)
                if(i-pre[j]+1>=len) add(f[i][j], p-sum[i-len]), add(f[i][j], f[i-len][j]);
                    //f[i][j]=(f[i][j]-sum[i-len]+f[i-len][j]+p)%p;
        }
        for(rint j=1; j<=k; j++) add(sum[i], f[i][j]);
            //sum[i]=(sum[i]+f[i][j])%p;
    }
    printf("%d\n", sum[n]);
}

G - Multidimensional Queries

思路： G 题与 E 题比反而是一个比较简单的数据结构题。

考虑 $k$ 比较小，于是我们可以对一个点枚举在每一维上对答案的贡献情况，即在公式 $\sum \limits_{i = 1}^{k} |a_{x, i} - a_{y, i}|$ 去掉绝对值时的符号。对于我们枚举的每一种情况，由于去掉了绝对值，答案便是求一个区间内最大值与最小值之差，这个可以很简单的用线段树去维护。

为了减小码量，对于每一棵线段树可以只维护最小值。而最大值与最小值之差就是当前状态下的最小值与相反状态下最小值的和。

代码：

Copy
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 200005
#define ls (root<<1)
#define rs (root<<1|1)
#define mid ((l+r)>>1)
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, k, q, w[6], sum[32];

struct Segtree
{
    int val[MAXN*4], num[MAXN];

    void up(int root)
    {
        val[root]=min(val[ls], val[rs]);
    }

    void build(int root, int l, int r)
    {
        if(l==r)
        {
            val[root]=num[l];
            return;
        }
        build(ls, l, mid);
        build(rs, mid+1, r);
        up(root);
    }

    void update(int root, int l, int r, int x, int k)
    {
        if(l>x || r<x) return;
        if(l==r)
        {
            val[root]=k;
            return;
        }
        update(ls, l, mid, x, k);
        update(rs, mid+1, r, x, k);
        up(root);
    }

    int query(int root, int l, int r, int x, int y)
    {
        if(l>y || r<x) return INF;
        if(l>=x && r<=y) return val[root];
        return min(query(ls, l, mid, x, y), query(rs, mid+1, r, x, y));
    }
} t[32];


int main()
{
    scanf("%d%d", &n, &k);
    for(rint i=1; i<=n; ++i)
    {
        for(rint j=0; j<k; ++j) scanf("%d", &w[j]);
        for(rint sta=0; sta<(1<<k); ++sta)
            for(rint j=0; j<k; ++j)
            {
                if((sta>>j)&1) t[sta].num[i]+=w[j];
                else t[sta].num[i]-=w[j];
            }
    }
    for(rint sta=0; sta<(1<<k); ++sta) t[sta].build(1, 1, n);
    scanf("%d", &q);
    while(q--)
    {
        int op, x, y, ans=0;
        scanf("%d", &op);
        if(op==2)
        {
            scanf("%d%d", &x, &y);
            for(rint sta=0; sta<(1<<k); ++sta)
                sum[sta]=t[sta].query(1, 1, n, x, y);
            for(rint sta=0; sta<(1<<k); ++sta)
                ans=max(ans, -(sum[sta]+sum[(1<<k)-1-sta]));
            printf("%d\n", ans);
        }
        else
        {
            scanf("%d", &x);
            for(rint i=0; i<k; ++i) scanf("%d", &w[i]);
            for(rint sta=0; sta<(1<<k); ++sta)
            {
                int temp=0;
                for(rint i=0; i<k; ++i)
                {
                    if((sta>>i)&1) temp+=w[i];
                    else temp-=w[i];
                }
                t[sta].update(1, 1, n, x, temp);
            }
        }
    }
}

C - Coloring Torus

D - Inversion Sum

E - Less than 3

F - Permutation and Minimum

结束位置集与状态

后缀链接

构造算法

最终代码

例题

离散傅里叶变换

快速傅里叶变换

傅里叶逆变换

最终代码

例题

一、点 向量

二、线段

三、多边形

D - Beautiful Graph

E -Intersection of Permutations

F - Vasya and Array

G - Multidimensional Queries

一、点向量