头像

ytczy666




离线:1天前


新鲜事 原文

ytczy666
21天前
明天月考,自闭啊



ytczy666
25天前

个人感觉atcoder上的题质量确实很高,比较偏向于竞赛的题型。

A

$\;$
$n$个人,$m$道题,每道题有两个选项。现在给出了这$n$个人的作答,用$n$个长度为$m$的01串来表示。
问:有多少个$(i,j)$,满足第$i$个人和第$j$个人做对的题目数量不可能相同。
$n\leq 10^5,m\leq 20$
$\;$
显然,如果两个人有奇数道题的答案不一样,他们做对的题目数量不可能相同。
把每个人的答案看成二进制数,问题转化为:异或后有奇数个1的数对有多少个
然后我们发现,如果两个数满足一个有偶数个1,另一个有奇数个1,则一定是满足条件的。
否则一定不行。
简单试试就看出来了。
$\;$

B

$\;$
给定$n \times n$的矩阵$C$
问:能否构造出两个数组$A,B$,满足:$C_{i,j}=A_i+B_j$
$n \leq 500$
$\;$
显然$A$是每一行的最小值,$B$就是这行每一列的数与这行最小值的差
$O(n^2)$简单判断一下是否是无解情况就行了
$\;$

C

$\;$
要求构造出长度为$n$的序列,使得对于任意$i|j$的情况,$a_i\neq a_j$
要求序列的最大值最小。
$n\leq 10^5$
$\;$
考虑一个位置的数,限制条件就是它的因数们。
考虑dp,那么一个位置应填的数,一定要比它所有因数下标中,填的数最大的那个+1
即:$dp_i=max {dp_j } +1$,这里$j$是$i$的因数
所以我们也可以直接枚举倍数去dp,复杂度为调和级数:$O(n log n)$
$\;$

D

$\;$
给定$n$个点,$m$条边的无向图(不保证联通)。
从$m$条边中选出一些边,与$n$个点所构成的图叫做生成子图
问:对于$k=0,1\cdots ,n$
有$k$个点的度数为奇数的生成子图有多少个。
$n\leq 5000$
$\;$
对于$k$为奇数的情况,答案就是0
然后考虑的情况:
我们发现$ans_k=C_n^k$
为什么?
我们从这$n$个点中选出$k$个点,然后一定保证有且只有一种构造(选边)方案,使得这$k$个点度数都为奇数。
下面我们把那$k$个点称作关键点
证明:因为是$k$是偶数,所以我们进行两两配对。这样路径的两个端点奇偶性一定会发生变化,且路径中间的点奇偶性不会变。
而且我们必须从下往上逐渐进行配对,每次找到深度最深的点$x$,满足它至少有两个子树中都有1个关键点
然后两两配对。又发现,配对的过程,必须是选这些关键点与$x$之间的路径上的边。
感性理解一下就好。
$\;$
然后考虑非树(即)的情况
我们一定可以从中找到一颗生成树,剩下$m-n+1$条边不是树上的边。
这$m-n+1$条边可以随便选。然后剩下的边又变成了树的情况
虽然选非树边会改变某些点的奇偶性,但是由于变成奇点的数量也一定是偶数个,而$k$也是偶数。
你会发现这两个玩意合并起来,只考虑树边使要变为奇点的(这里的奇点是只考虑树边贡献的度数)数量也一定是偶数。
这其实与$A$的思路有些类似。
因此,图的情况即是$C_n^k \times 2^{m-n+1}$
$\;$
若有多个连通图,那么只需进行一次简单的dp。
怎么dp就比较显然了。
看起来dp的复杂度是$O(n^3)$的(也有可能是我自己sb了),实际上是$O(n^2)$




ytczy666
1个月前

博客食用更佳~ https://www.cnblogs.com/czyty114/p/14432462.html

$\;$
莫队是一类离线区间询问问题,经常应用于需要维护的信息无法合并时(如线段树等)
其核心思想是:维护两个指针$l,r$。在已知$[l,r]$这段区间的信息的前提下,两个指针分别移动到$l’,r’$的过程中,实时地维护答案。从而算出区间$[l,r]的信息$
$\;$

引入

$\;$
因为题目没有强制在线,所以莫队算法是将所有的询问按一定顺序排好序,并且一次询问是以上一次询问为基础。
我们可以把一次询问$l,r$看作二维平面上的一个点$(l,r)$,那我们在两次询问间$l,r$指针一共移动的距离,实质上是$(l_1,r_1)$,$(l_2,r_2)$间的曼哈顿距离
但求最小哈密尔顿路径又是无法做到的。所以我们需要找到一个合适的顺序,使得两指针移动的距离尽可能的小。
$\;$

普通莫队

$\;$

核心

$\;$
假设现在给定你一个长为$n$的序列,$m$次询问,每次询问求$[l,r]$这段区间不同数的数量。
$n,m\leq 10^5$
对于这个问题来说,用线段树是很难去维护的。因为区间不同数的数量并不能很轻松地由左右子区间转移而来。
考虑将整个序列分块,每段长度为$\sqrt n$
这样每段询问区间的左右端点必定位于某个块中。
我们把区间左端点所属的块的编号作为第一关键字,右端点的位置作为第二关键字,将询问区间排序。
按照莫队的思想,我们按此顺序依次处理每一个区间,在两个指针的移动的过程中维护一个数组cnt,表示每一个数出现的次数。
若发现某个数cnt为由1减为0了,将答案减1,反之则加1
$\;$

时间复杂度

$\;$
我们发现算法中时间的瓶颈就在于,左右指针总共会移动多少次。我们分开来看:
(注意:这里我们假设m与n同阶)
$\;$
左端点
$\;$
因为第一关键字是按左端点所在块排序的,所以左端点所在块是单调不降的。
对于目前左端点与上一个左端点同属一个块的情况:最多出现$n$次,但每一次两个点之间移动的距离不超过$\sqrt n$
因此:$O(n\sqrt n)$
对于目前左端点与上一个左端点不同属一个块的情况:最多出现$\sqrt n$次,但每一次两个点之间移动的距离不超过$n$
因此:$O(n\sqrt n)$
$\;$
右端点
$\;$
其位置作为第二关键字。因此若左端点有若干个位于同一个块中,此时右端点应该是单调不降的。
因此对于同一个块的左端点,右端点至多移动$n$次,而总共有$\sqrt n$个块
因此:$O(n\sqrt n)$
否则,若左端点不在同一个块中,右端点的位置就无法确定了。这样一次右端点至多移动$n$次
但这种情况至多出现$\sqrt n$次
因此:$O(n\sqrt n)$
$\;$
综上所述,莫队算法的时间复杂度为$O(n\sqrt n)$

Code

#include <bits/stdc++.h>

const int N = 50010, M = 200010;
int n, m, a[N], b[N], ans[M], id[N], sq, nn, cnt[N];
struct node {
    int pos, l, r;
}ask[M];
bool cmp(node a, node b) {
    if(id[a.l] != id[b.l]) return id[a.l] < id[b.l]; // 左端点所属块 
    return a.r < b.r; // 右端点所属位置 
}
int main() {
    scanf("%d", &n);
    sq = (int)sqrt(n);
    for(int i=1;i<=n;i++) id[i] = (int)ceil(i / sq); // 预处理每个点所属块的编号 
    for(int i=1;i<=n;i++) scanf("%d", &a[i]), b[i] = a[i];
    std::sort(b + 1, b + n + 1);
    nn = std::unique(b + 1, b + n + 1) - b - 1;
    for(int i=1;i<=n;i++) a[i] = std::lower_bound(b + 1, b + nn + 1, a[i]) - b;
    //----------------- 上面是离散化部分,不多赘述 
    scanf("%d", &m);
    for(int i=1;i<=m;i++) scanf("%d%d", &ask[i].l, &ask[i].r), ask[i].pos = i;
    std::sort(ask + 1, ask + m + 1, cmp);
    int x = 0, y = 0, res = 0; //x,y维护的是一直在移动两个指针 
    for(int i=1;i<=m;i++) {
        int l = ask[i].l, r = ask[i].r; // l,r是当前询问的两个左右端点 
        while(x < l) { // 左端点向右移,区间缩小 
            cnt[a[x]] --; if(!cnt[a[x]]) -- res;
            x ++;
        }

        while(x > l) { // 左端点向左移,区间变大 
            cnt[a[x - 1]] ++; if(cnt[a[x - 1]] == 1) ++ res;
            x --;
        }

        while(y < r) { // 右端点向右移,区间变大 
            cnt[a[y + 1]] ++; if(cnt[a[y + 1]] == 1) ++ res;
            y ++;
        }

        while(y > r) { // 右端点向左移,区间缩小 
            cnt[a[y]] --; if(!cnt[a[y]]) -- res;
            y --;
        }

        ans[ask[i].pos] = res; // 注意:i是排序后区间的编号,但并不是输入时询问的编号 
    }
    for(int i=1;i<=m;i++) printf("%d\n", ans[i]);
    return 0;
}

带修莫队

$\;$
一般的莫队实质上是不支持修改操作的,但如果这个修改操作很简单,比较容易维护,我们还是可以实现的。
而带修莫队的分块方式与普通莫队不同。
现在我们把序列分为$n^{\frac{1}{3}}$个块,每个块的长度为$n^{\frac{2}{3}}$
对于操作来说,我们把修改和询问分开。
对于询问:左端点所在块为第一关键字,右端点所在块为第二关键字,时间(输入的时候排第几行)为第三关键字进行排序。
那么,与普通莫队类似。只需多维护一个修改的操作。
即:假设两个询问的时间分别为$t_1,t_2$,我们只需把$[t_1,t_2]$这段时间内的修改操作执行一遍(时光正流或倒流)
$\;$

时间复杂度

$\;$
时间指针
当左右端点所在块不变时。对于每种两个块组合的方案,因为时间是递增的,所以最多执行$O(n)$次,一共有$n^{\frac{2}{3}}$种方案,故为$O(n^{\frac{5}{3}})$
当左端点所在块不变,右端点递增时,也只会出现$n^{\frac{2}{3}}$次,每次$O(n)$,故为$O(n^{\frac{5}{3}})$
当左端点所在块变化时,只会出现$n^{\frac{1}{3}}$次,每次$O(n)$,故为$O(n^{\frac{4}{3}})$
综上:为$O(n^{\frac{5}{3}})$
$\;$
右端点
当左右端点所在块不变时。$n$次询问,每次最多移动$n^{\frac{2}{3}}$,故为$O(n^{\frac{5}{3}})$
当左端点所在块不变,右端点递增时,会出现$n^{\frac{1}{3}}$次,每次$O(n)$,故为$O(n^{\frac{4}{3}})$
当左端点所在块变化时,与上面类似,也为$O(n^{\frac{4}{3}})$
综上:为$O(n^{\frac{5}{3}})$
$\;$
左端点
当左端点所在块不变时,与上面的情况一样。为$O(n^{\frac{5}{3}})$
而最多会变$n^{\frac{1}{3}}$次,因为是按左端点所在块为第一关键字排序的。所以变化这一部分是$O(n)$的
综上:为$O(n^{\frac{5}{3}})$
$\;$

Code

$\;$
例题:P1903 数颜色
https://www.luogu.com.cn/problem/P1903

#include <bits/stdc++.h>

#define fi first
#define se second
const int N = 143333;
int n, m, k, a[N], cnt[N * 10], ans[N], id[N], sq, T, b[N], res, x, y;
std::pair<int,int> cur[N], fur[N];
struct node {
    int l, r, t, pos;
}ask[N];

bool cmp(node a, node b) {
    if(id[a.l] != id[b.l]) return id[a.l] < id[b.l];
    if(id[a.r] != id[b.r]) return id[a.r] < id[b.r];
    return a.t < b.t;
}

bool g(int d) {
    return (x <= d && d <= y);
}
void gg(int x, int y) {
    cnt[x] --; cnt[y] ++;
    if(!cnt[x]) -- res; if(cnt[y] == 1) ++ res;
}
int main() {
    scanf("%d%d", &n, &m);
    sq = pow(n, 3.0 / 4);
    for(int i=1;i<=n;i++) id[i] = (int)ceil(i / sq);
    for(int i=1;i<=n;i++) scanf("%d", &a[i]), b[i] = a[i];
    for(int i=1;i<=m;i++) {
        char op[5]; int l, r;
        scanf("%s", op);
        scanf("%d%d", &l, &r);
        if(op[0] == 'Q') {
            ++ k; ask[k].l = l; ask[k].r = r; ask[k].t = i; ask[k].pos = k;
        }
        else {
            cur[i].fi = l; cur[i].se = r;
            fur[i].fi = l; fur[i].se = b[l]; b[l] = r;
        }
    }
    std::sort(ask + 1, ask + k + 1, cmp);
    int ti = 0;
    for(int i=1;i<=k;i++) {
        int t = ask[i].t, l = ask[i].l, r = ask[i].r;
        while(ti < t) {
            if(!cur[ti + 1].fi) {
                ti ++; continue;
            }
            if(g(cur[ti + 1].fi)) gg(a[cur[ti + 1].fi], cur[ti + 1].se);
            a[cur[ti + 1].fi] = cur[ti + 1].se;
            ti ++;
        } 
        while(ti > t) {
            if(!fur[ti].fi) {
                ti --; continue;
            }
            if(g(fur[ti].fi)) gg(a[fur[ti].fi], fur[ti].se);
            a[fur[ti].fi] = fur[ti].se; 
            ti --; 
        }
        while(x < l) {
            cnt[a[x]] --; if(!cnt[a[x]]) -- res;
            x ++;
        }
        while(x > l) {
            cnt[a[x - 1]] ++; if(cnt[a[x - 1]] == 1) ++ res;
            x --;
        } 
        while(y < r) {
            cnt[a[y + 1]] ++; if(cnt[a[y + 1]] == 1) ++ res;
            y ++;
        }
        while(y > r) {
            cnt[a[y]] --; if(!cnt[a[y]]) -- res;
            y --;
        }
        ans[ask[i].pos] = res;
    }
    for(int i=1;i<=k;i++) printf("%d\n", ans[i]);
    return 0;
}

$\;$

树上莫队

$\;$

核心

$\;$
只不过把序列的问题搬到了树上,区间也就变成了一条链。
我们将树分块。
具体实现方法是:维护一个栈,代表目前待选的点的集合S。dfs到某个点u的时候,遍历它的所有子树并统计目前集合S的大小,在遍历的过程中,如果发现集合S的大小已超过规定的块大小,将这些点分为一块。
可以注意到,因为我们是按dfs的顺序进行编号的。所以相邻编号的块在树上也一定是相邻的,这样就会满足莫队的复杂度。
而因为不是在序列上,所以我们不能简单的对左右指针+1或-1
假如上一次询问的链是$(x,y)$,这次是$(u,v)$,那么只需对$(x,u)$和$(y,v)$这两条链上的点的标记进行取反操作。
最终$(u,v)$上的所有点会被标为1。这个可以通过画图理解。
不过在实现的时候,还要注意一些细节:比如说LCA可能要特殊处理,可以参考代码理解。
那么剩余的就和普通、带修莫队一样了。
$\;$

Code

$\;$
例题:P4074 糖果公园
https://www.luogu.com.cn/problem/P4074
$\;$

#include <bits/stdc++.h>

const int N = 100010;

int n, m, k, q, top, val[N], w[N], tim[N], stk[N], idx, dfn[N], dep[N], S, lst[N], id[N], scc, c[N], bc[N];
int upd[N], pre[N], d[N], x, y, vis[N], f[N][20];
long long ans, res[N];
std::vector<int> G[N];
int read() {
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    return f * x;
}
int dfs(int u, int fa) {
    int re = 0; 
    dfn[u] = ++idx; 
    f[u][0] = lst[u] = fa; 
    dep[u] = dep[fa] + 1;
    for(int i=1;i<=19;i++) f[u][i] = f[f[u][i - 1]][i - 1];
    for(int i=0;i<G[u].size();i++) {
        int v = G[u][i];
        if(v == fa) continue;
        re += dfs(v, u);
        if(re >= S) {
            scc ++;
            while(re) 
                id[stk[top --]] = scc, re --;
        }
    }
    stk[++top] = u;
    return re + 1;
}
struct node {
    int l, r, pos, t;
}ask[N];
bool cmp(node a, node b) {
    if(id[a.l] != id[b.l]) return id[a.l] < id[b.l];
    if(id[a.r] != id[b.r]) {
        if(id[a.l] & 1) return id[a.r] < id[b.r];
        return id[a.r] > id[b.r];
    }
    return a.pos < b.pos;
}
int lca(int x, int y) {
    if(x == y) return x;
    if(dep[x] < dep[y]) std::swap(x, y);
    int ch = dep[x] - dep[y], er = 0;
    while(ch) {
        if(ch & 1) x = f[x][er];
        ch >>= 1; er ++; 
    }
    if(x == y) return x;
    for(int i=19;~i;i--) {
        if(f[x][i] == f[y][i]) continue;
        x = f[x][i]; y = f[y][i];
    }
    return f[x][0];
}
void change(int d, int v) {
    if(vis[d]) {
        ans = ans - 1ll * w[tim[c[d]] --] * val[c[d]];
        ans = ans + 1ll * w[++ tim[v]] * val[v];
        c[d] = v;
    }
    else c[d] = v;
}
void modify(int x) {
    if(vis[x]) {
        vis[x] = 0;
        ans = ans - 1ll * val[c[x]] * w[tim[c[x]] --]; 
    }
    else {
        vis[x] = 1;
        ans = ans + 1ll * val[c[x]] * w[++tim[c[x]]];
    }
}
void make_tag(int u, int v) {
    while(u != v) {
        if(dep[u] > dep[v]) modify(u), u = f[u][0];
        else modify(v), v = f[v][0];
        //printf("%d %d\n", u, v);
    }
} 
int main() {
    n = read(); m = read(); q = read();
    S = pow(n, 0.666); 
    for(int i=1;i<=m;i++) val[i] = read();
    for(int i=1;i<=n;i++) w[i] = read();
    for(int i=1;i<n;i++) {
        int u, v;
        u = read(); v = read();
        G[u].push_back(v); G[v].push_back(u);
    }
    dfs(1, 0);
    scc ++;
    for(int i=1;i<=n;i++) if(!id[i]) id[i] = scc;
    for(int i=1;i<=n;i++) c[i] = read(), bc[i] = c[i];
    for(int i=1;i<=q;i++) { 
        int op, l, r;
        op = read(); l = read(); r = read();
        if(!op) {
            upd[i] = r; d[i] = l; pre[i] = bc[l]; bc[l] = r;
        }
        else {
            if(dfn[l] > dfn[r]) std::swap(l, r);
            ask[++k].l = l; ask[k].r = r; ask[k].t = i; ask[k].pos = k;
        }
    }
    std::sort(ask + 1, ask + k + 1, cmp);
    for(int i=1;i<ask[1].t;i++) {
        if(!upd[i]) continue;
        change(d[i], upd[i]); 
    }
    x = ask[1].l; y = ask[1].r; 
    make_tag(x, y); modify(lca(x, y));
    res[ask[1].pos] = ans;
    modify(lca(x, y));
    for(int i=2;i<=k;i++) {
        int l = ask[i].l, r = ask[i].r;
        // time
        int t = ask[i].t, p = ask[i - 1].t;
        while(p < t) {
            p ++;
            if(upd[p]) change(d[p], upd[p]); 
        }
        while(p > t) {
            if(upd[p]) change(d[p], pre[p]);
            p --;
        }
        make_tag(x, l);
        make_tag(y, r); 
        modify(lca(l, r));
        res[ask[i].pos] = ans;
        modify(lca(l, r));
        x = l; y = r;
    }
    for(int i=1;i<=k;i++) printf("%lld\n", res[i]);
    return 0;
}



ytczy666
1个月前

博客食用更佳~ https://www.cnblogs.com/czyty114/p/14432462.html

$\;$
莫队是一类离线区间询问问题,经常应用于需要维护的信息无法合并时(如线段树等)
其核心思想是:维护两个指针$l,r$。在已知$[l,r]$这段区间的信息的前提下,两个指针分别移动到$l’,r’$的过程中,实时地维护答案。从而算出区间$[l,r]的信息$
$\;$

引入

$\;$
因为题目没有强制在线,所以莫队算法是将所有的询问按一定顺序排好序,并且一次询问是以上一次询问为基础。
我们可以把一次询问$l,r$看作二维平面上的一个点$(l,r)$,那我们在两次询问间$l,r$指针一共移动的距离,实质上是$(l_1,r_1)$,$(l_2,r_2)$间的曼哈顿距离
但求最小哈密尔顿路径又是无法做到的。所以我们需要找到一个合适的顺序,使得两指针移动的距离尽可能的小。
$\;$

普通莫队

$\;$

核心

$\;$
假设现在给定你一个长为$n$的序列,$m$次询问,每次询问求$[l,r]$这段区间不同数的数量。
$n,m\leq 10^5$
对于这个问题来说,用线段树是很难去维护的。因为区间不同数的数量并不能很轻松地由左右子区间转移而来。
考虑将整个序列分块,每段长度为$\sqrt n$
这样每段询问区间的左右端点必定位于某个块中。
我们把区间左端点所属的块的编号作为第一关键字,右端点的位置作为第二关键字,将询问区间排序。
按照莫队的思想,我们按此顺序依次处理每一个区间,在两个指针的移动的过程中维护一个数组cnt,表示每一个数出现的次数。
若发现某个数cnt为由1减为0了,将答案减1,反之则加1
$\;$

时间复杂度

$\;$
我们发现算法中时间的瓶颈就在于,左右指针总共会移动多少次。我们分开来看:
(注意:这里我们假设m与n同阶)
$\;$
左端点
$\;$
因为第一关键字是按左端点所在块排序的,所以左端点所在块是单调不降的。
对于目前左端点与上一个左端点同属一个块的情况:最多出现$n$次,但每一次两个点之间移动的距离不超过$\sqrt n$
因此:$O(n\sqrt n)$
对于目前左端点与上一个左端点不同属一个块的情况:最多出现$\sqrt n$次,但每一次两个点之间移动的距离不超过$n$
因此:$O(n\sqrt n)$
$\;$
右端点
$\;$
其位置作为第二关键字。因此若左端点有若干个位于同一个块中,此时右端点应该是单调不降的。
因此对于同一个块的左端点,右端点至多移动$n$次,而总共有$\sqrt n$个块
因此:$O(n\sqrt n)$
否则,若左端点不在同一个块中,右端点的位置就无法确定了。这样一次右端点至多移动$n$次
但这种情况至多出现$\sqrt n$次
因此:$O(n\sqrt n)$
$\;$
综上所述,莫队算法的时间复杂度为$O(n\sqrt n)$

Code

#include <bits/stdc++.h>

const int N = 50010, M = 200010;
int n, m, a[N], b[N], ans[M], id[N], sq, nn, cnt[N];
struct node {
    int pos, l, r;
}ask[M];
bool cmp(node a, node b) {
    if(id[a.l] != id[b.l]) return id[a.l] < id[b.l]; // 左端点所属块 
    return a.r < b.r; // 右端点所属位置 
}
int main() {
    scanf("%d", &n);
    sq = (int)sqrt(n);
    for(int i=1;i<=n;i++) id[i] = (int)ceil(i / sq); // 预处理每个点所属块的编号 
    for(int i=1;i<=n;i++) scanf("%d", &a[i]), b[i] = a[i];
    std::sort(b + 1, b + n + 1);
    nn = std::unique(b + 1, b + n + 1) - b - 1;
    for(int i=1;i<=n;i++) a[i] = std::lower_bound(b + 1, b + nn + 1, a[i]) - b;
    //----------------- 上面是离散化部分,不多赘述 
    scanf("%d", &m);
    for(int i=1;i<=m;i++) scanf("%d%d", &ask[i].l, &ask[i].r), ask[i].pos = i;
    std::sort(ask + 1, ask + m + 1, cmp);
    int x = 0, y = 0, res = 0; //x,y维护的是一直在移动两个指针 
    for(int i=1;i<=m;i++) {
        int l = ask[i].l, r = ask[i].r; // l,r是当前询问的两个左右端点 
        while(x < l) { // 左端点向右移,区间缩小 
            cnt[a[x]] --; if(!cnt[a[x]]) -- res;
            x ++;
        }

        while(x > l) { // 左端点向左移,区间变大 
            cnt[a[x - 1]] ++; if(cnt[a[x - 1]] == 1) ++ res;
            x --;
        }

        while(y < r) { // 右端点向右移,区间变大 
            cnt[a[y + 1]] ++; if(cnt[a[y + 1]] == 1) ++ res;
            y ++;
        }

        while(y > r) { // 右端点向左移,区间缩小 
            cnt[a[y]] --; if(!cnt[a[y]]) -- res;
            y --;
        }

        ans[ask[i].pos] = res; // 注意:i是排序后区间的编号,但并不是输入时询问的编号 
    }
    for(int i=1;i<=m;i++) printf("%d\n", ans[i]);
    return 0;
}

带修莫队

$\;$
一般的莫队实质上是不支持修改操作的,但如果这个修改操作很简单,比较容易维护,我们还是可以实现的。
而带修莫队的分块方式与普通莫队不同。
现在我们把序列分为$n^{\frac{1}{3}}$个块,每个块的长度为$n^{\frac{2}{3}}$
对于操作来说,我们把修改和询问分开。
对于询问:左端点所在块为第一关键字,右端点所在块为第二关键字,时间(输入的时候排第几行)为第三关键字进行排序。
那么,与普通莫队类似。只需多维护一个修改的操作。
即:假设两个询问的时间分别为$t_1,t_2$,我们只需把$[t_1,t_2]$这段时间内的修改操作执行一遍(时光正流或倒流)
$\;$

时间复杂度

$\;$
时间指针
当左右端点所在块不变时。对于每种两个块组合的方案,因为时间是递增的,所以最多执行$O(n)$次,一共有$n^{\frac{2}{3}}$种方案,故为$O(n^{\frac{5}{3}})$
当左端点所在块不变,右端点递增时,也只会出现$n^{\frac{2}{3}}$次,每次$O(n)$,故为$O(n^{\frac{5}{3}})$
当左端点所在块变化时,只会出现$n^{\frac{1}{3}}$次,每次$O(n)$,故为$O(n^{\frac{4}{3}})$
综上:为$O(n^{\frac{5}{3}})$
$\;$
右端点
当左右端点所在块不变时。$n$次询问,每次最多移动$n^{\frac{2}{3}}$,故为$O(n^{\frac{5}{3}})$
当左端点所在块不变,右端点递增时,会出现$n^{\frac{1}{3}}$次,每次$O(n)$,故为$O(n^{\frac{4}{3}})$
当左端点所在块变化时,与上面类似,也为$O(n^{\frac{4}{3}})$
综上:为$O(n^{\frac{5}{3}})$
$\;$
左端点
当左端点所在块不变时,与上面的情况一样。为$O(n^{\frac{5}{3}})$
而最多会变$n^{\frac{1}{3}}$次,因为是按左端点所在块为第一关键字排序的。所以变化这一部分是$O(n)$的
综上:为$O(n^{\frac{5}{3}})$
$\;$

Code

$\;$
例题:P1903 数颜色
https://www.luogu.com.cn/problem/P1903

#include <bits/stdc++.h>

#define fi first
#define se second
const int N = 143333;
int n, m, k, a[N], cnt[N * 10], ans[N], id[N], sq, T, b[N], res, x, y;
std::pair<int,int> cur[N], fur[N];
struct node {
    int l, r, t, pos;
}ask[N];

bool cmp(node a, node b) {
    if(id[a.l] != id[b.l]) return id[a.l] < id[b.l];
    if(id[a.r] != id[b.r]) return id[a.r] < id[b.r];
    return a.t < b.t;
}

bool g(int d) {
    return (x <= d && d <= y);
}
void gg(int x, int y) {
    cnt[x] --; cnt[y] ++;
    if(!cnt[x]) -- res; if(cnt[y] == 1) ++ res;
}
int main() {
    scanf("%d%d", &n, &m);
    sq = pow(n, 3.0 / 4);
    for(int i=1;i<=n;i++) id[i] = (int)ceil(i / sq);
    for(int i=1;i<=n;i++) scanf("%d", &a[i]), b[i] = a[i];
    for(int i=1;i<=m;i++) {
        char op[5]; int l, r;
        scanf("%s", op);
        scanf("%d%d", &l, &r);
        if(op[0] == 'Q') {
            ++ k; ask[k].l = l; ask[k].r = r; ask[k].t = i; ask[k].pos = k;
        }
        else {
            cur[i].fi = l; cur[i].se = r;
            fur[i].fi = l; fur[i].se = b[l]; b[l] = r;
        }
    }
    std::sort(ask + 1, ask + k + 1, cmp);
    int ti = 0;
    for(int i=1;i<=k;i++) {
        int t = ask[i].t, l = ask[i].l, r = ask[i].r;
        while(ti < t) {
            if(!cur[ti + 1].fi) {
                ti ++; continue;
            }
            if(g(cur[ti + 1].fi)) gg(a[cur[ti + 1].fi], cur[ti + 1].se);
            a[cur[ti + 1].fi] = cur[ti + 1].se;
            ti ++;
        } 
        while(ti > t) {
            if(!fur[ti].fi) {
                ti --; continue;
            }
            if(g(fur[ti].fi)) gg(a[fur[ti].fi], fur[ti].se);
            a[fur[ti].fi] = fur[ti].se; 
            ti --; 
        }
        while(x < l) {
            cnt[a[x]] --; if(!cnt[a[x]]) -- res;
            x ++;
        }
        while(x > l) {
            cnt[a[x - 1]] ++; if(cnt[a[x - 1]] == 1) ++ res;
            x --;
        } 
        while(y < r) {
            cnt[a[y + 1]] ++; if(cnt[a[y + 1]] == 1) ++ res;
            y ++;
        }
        while(y > r) {
            cnt[a[y]] --; if(!cnt[a[y]]) -- res;
            y --;
        }
        ans[ask[i].pos] = res;
    }
    for(int i=1;i<=k;i++) printf("%d\n", ans[i]);
    return 0;
}

$\;$

树上莫队

$\;$

核心

$\;$
只不过把序列的问题搬到了树上,区间也就变成了一条链。
我们将树分块。
具体实现方法是:维护一个栈,代表目前待选的点的集合S。dfs到某个点u的时候,遍历它的所有子树并统计目前集合S的大小,在遍历的过程中,如果发现集合S的大小已超过规定的块大小,将这些点分为一块。
可以注意到,因为我们是按dfs的顺序进行编号的。所以相邻编号的块在树上也一定是相邻的,这样就会满足莫队的复杂度。
而因为不是在序列上,所以我们不能简单的对左右指针+1或-1
假如上一次询问的链是$(x,y)$,这次是$(u,v)$,那么只需对$(x,u)$和$(y,v)$这两条链上的点的标记进行取反操作。
最终$(u,v)$上的所有点会被标为1。这个可以通过画图理解。
不过在实现的时候,还要注意一些细节:比如说LCA可能要特殊处理,可以参考代码理解。
那么剩余的就和普通、带修莫队一样了。
$\;$

Code

$\;$
例题:P4074 糖果公园
https://www.luogu.com.cn/problem/P4074
$\;$

#include <bits/stdc++.h>

const int N = 100010;

int n, m, k, q, top, val[N], w[N], tim[N], stk[N], idx, dfn[N], dep[N], S, lst[N], id[N], scc, c[N], bc[N];
int upd[N], pre[N], d[N], x, y, vis[N], f[N][20];
long long ans, res[N];
std::vector<int> G[N];
int read() {
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    return f * x;
}
int dfs(int u, int fa) {
    int re = 0; 
    dfn[u] = ++idx; 
    f[u][0] = lst[u] = fa; 
    dep[u] = dep[fa] + 1;
    for(int i=1;i<=19;i++) f[u][i] = f[f[u][i - 1]][i - 1];
    for(int i=0;i<G[u].size();i++) {
        int v = G[u][i];
        if(v == fa) continue;
        re += dfs(v, u);
        if(re >= S) {
            scc ++;
            while(re) 
                id[stk[top --]] = scc, re --;
        }
    }
    stk[++top] = u;
    return re + 1;
}
struct node {
    int l, r, pos, t;
}ask[N];
bool cmp(node a, node b) {
    if(id[a.l] != id[b.l]) return id[a.l] < id[b.l];
    if(id[a.r] != id[b.r]) {
        if(id[a.l] & 1) return id[a.r] < id[b.r];
        return id[a.r] > id[b.r];
    }
    return a.pos < b.pos;
}
int lca(int x, int y) {
    if(x == y) return x;
    if(dep[x] < dep[y]) std::swap(x, y);
    int ch = dep[x] - dep[y], er = 0;
    while(ch) {
        if(ch & 1) x = f[x][er];
        ch >>= 1; er ++; 
    }
    if(x == y) return x;
    for(int i=19;~i;i--) {
        if(f[x][i] == f[y][i]) continue;
        x = f[x][i]; y = f[y][i];
    }
    return f[x][0];
}
void change(int d, int v) {
    if(vis[d]) {
        ans = ans - 1ll * w[tim[c[d]] --] * val[c[d]];
        ans = ans + 1ll * w[++ tim[v]] * val[v];
        c[d] = v;
    }
    else c[d] = v;
}
void modify(int x) {
    if(vis[x]) {
        vis[x] = 0;
        ans = ans - 1ll * val[c[x]] * w[tim[c[x]] --]; 
    }
    else {
        vis[x] = 1;
        ans = ans + 1ll * val[c[x]] * w[++tim[c[x]]];
    }
}
void make_tag(int u, int v) {
    while(u != v) {
        if(dep[u] > dep[v]) modify(u), u = f[u][0];
        else modify(v), v = f[v][0];
        //printf("%d %d\n", u, v);
    }
} 
int main() {
    n = read(); m = read(); q = read();
    S = pow(n, 0.666); 
    for(int i=1;i<=m;i++) val[i] = read();
    for(int i=1;i<=n;i++) w[i] = read();
    for(int i=1;i<n;i++) {
        int u, v;
        u = read(); v = read();
        G[u].push_back(v); G[v].push_back(u);
    }
    dfs(1, 0);
    scc ++;
    for(int i=1;i<=n;i++) if(!id[i]) id[i] = scc;
    for(int i=1;i<=n;i++) c[i] = read(), bc[i] = c[i];
    for(int i=1;i<=q;i++) { 
        int op, l, r;
        op = read(); l = read(); r = read();
        if(!op) {
            upd[i] = r; d[i] = l; pre[i] = bc[l]; bc[l] = r;
        }
        else {
            if(dfn[l] > dfn[r]) std::swap(l, r);
            ask[++k].l = l; ask[k].r = r; ask[k].t = i; ask[k].pos = k;
        }
    }
    std::sort(ask + 1, ask + k + 1, cmp);
    for(int i=1;i<ask[1].t;i++) {
        if(!upd[i]) continue;
        change(d[i], upd[i]); 
    }
    x = ask[1].l; y = ask[1].r; 
    make_tag(x, y); modify(lca(x, y));
    res[ask[1].pos] = ans;
    modify(lca(x, y));
    for(int i=2;i<=k;i++) {
        int l = ask[i].l, r = ask[i].r;
        // time
        int t = ask[i].t, p = ask[i - 1].t;
        while(p < t) {
            p ++;
            if(upd[p]) change(d[p], upd[p]); 
        }
        while(p > t) {
            if(upd[p]) change(d[p], pre[p]);
            p --;
        }
        make_tag(x, l);
        make_tag(y, r); 
        modify(lca(l, r));
        res[ask[i].pos] = ans;
        modify(lca(l, r));
        x = l; y = r;
    }
    for(int i=1;i<=k;i++) printf("%lld\n", res[i]);
    return 0;
}



ytczy666
1个月前

博客食用更佳 https://www.cnblogs.com/czyty114/p/14449737.html

引入

$\;$
假如现在我们得到了一棵$n$个节点的树,每条边都有长度。
现在我们要求这棵树中两个点之间距离小于$k$的点对个数。
$n\leq 4×10^4$

朴素做法

$\;$
先预处理好距离,再$O(n^2)$枚举点对。

重心

$\;$
我们找到这棵树的重心G,把这棵树分为若干个子树,那么发现满足条件的点对只有3种情况:
1.点对在某个子树中(直接递归求解)
2.两个点所构成的路径经过了重心G,但你会发现这两个点一定不能在同一个子树中。
所以我们处理出当前这棵树中每个点的d值,$d_i$表示点$i$到重心G的距离。
那么只需要用$d_i+d_j\leq k$这样$(i,j)$的数量减去$d_i+d_j\leq k$且满足$i,j$在同一个子树中的数量
而你会发现,后者可以在递归子树中处理。
3.这条路经的一个端点是G,那么实质上和2.是一种情况,再加入一个$d_G=0$即可
$\;$

时间复杂度

$\;$
选重心来分割整棵树的目的:
你会发现,这若干棵子树中不会有子树的大小超过原树的一半(否则就与重心的定义不符)
所以最多只会递归$log(n)$层,每一层也是$n$个点。但在递归中还要将处理好的d排序。
总复杂度$O(n log^2 n)$

Code

$\;$
一定要注意:如果在函数里单独开变量而是开全局变量,一定要注意随时清空,防止上一层的答案对下面有影响。

#include <bits/stdc++.h>

const int N = 40010;
int n, k, head[N], tot, f[N], mn, W, vis[N], d[N], ans, q[N], cnt, sz[N];
struct node {
    int to, nxt, val;
}E[N << 1];
void add(int u, int v, int w) {
    E[++tot].to = v; E[tot].nxt = head[u]; E[tot].val = w; head[u] = tot;
}
void dfs(int total, int u, int fa) {
    f[u] = 0; // 一定注意初始化 
    for(int i=head[u];i;i=E[i].nxt) {
        int v = E[i].to;
        if(v == fa || vis[v]) continue;
        dfs(total, v, u);
        f[u] = std::max(f[u], sz[v]);
    }
    f[u] = std::max(f[u], total - sz[u]);
    if(f[u] < mn) {
        mn = f[u]; W = u;
    }
}
void dfs0(int u, int fa) {
    sz[u] = 1; q[++cnt] = d[u]; // 这是在减去2那一部分的时候的d值 
    for(int i=head[u];i;i=E[i].nxt) {
        int v = E[i].to;
        if(v == fa || vis[v]) continue;
        dfs0(v, u); 
        sz[u] += sz[v];
    }
} 
void getG(int rt) {     
    cnt = 0; // 随时清空 
    dfs0(rt, 0); // 预处理好每个点的子树大小(因为随着划分重心,树的形态会变化) 
    mn = 1e9; // 注意初始化 
    dfs(sz[rt], rt, 0); // DP计算重心 
    vis[W] = 1; // 这个点作为重心,将其打上标记(相当于一个边界条件) 
}
void getd(int u, int fa) {
    q[++cnt] = d[u]; // 在求d值的过程中将其存入q数组中,这里是以这棵树为重心是的d值,与上面的d不一样 
    for(int i=head[u];i;i=E[i].nxt) {
        int v = E[i].to;
        if(vis[v] || v == fa) continue;
        d[v] = d[u] + E[i].val; 
        getd(v, u);
    }
}
void solve(int rt) {
    getG(rt);  // 得到重心 
    if(sz[rt] != n) { 
    // 对于2.情况,要减去在相同子树内(i,j)<=k的个数。这个过程是在递归到这个子树中时进行的 
    //但对于一开始整棵树的情况就没必要减了 
        std::sort(q + 1, q + cnt + 1); 
        // q里存储的是这棵子树内的d值
        // 因为树内点的编号不一定是连续的,所以需要开q这个数组存它 
        int e1 = 1, e2 = cnt;
        for(int e1=1;e1<=cnt;e1++) {
            while(e2 > e1 && q[e1] + q[e2] > k) e2 --; // 双指针枚举,复杂度是线性的 
            if(e2 <= e1) break;
            ans -= (e2 - e1);
        }
    }
    d[W] = 0; // 重心的d当然是0 
    cnt = 0; // 一定注意要随时清空 
    getd(W, 0);
    std::sort(q + 1, q + cnt + 1);
    int e1 = 1, e2 = cnt;
    for(int e1=1;e1<=cnt;e1++) {
        while(e2 > e1 && q[e1] + q[e2] > k) e2 --;
        if(e2 <= e1) break;
        ans += (e2 - e1);
    } 
    for(int i=head[W];i;i=E[i].nxt) {
        int v = E[i].to;
        if(!vis[v]) solve(v); // 如果这个点没被打上标记,一定要向下递归 
    }
}
int main() {
    scanf("%d", &n);
    for(int i=1;i<n;i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w); add(v, u, w);
    }
    scanf("%d", &k);
    solve(1);
    printf("%d", ans);
    return 0;
}


分享 点分治

ytczy666
1个月前

博客食用更佳 https://www.cnblogs.com/czyty114/p/14449737.html

引入

$\;$
假如现在我们得到了一棵$n$个节点的树,每条边都有长度。
现在我们要求这棵树中两个点之间距离小于$k$的点对个数。
$n\leq 4×10^4$

朴素做法

$\;$
先预处理好距离,再$O(n^2)$枚举点对。

重心

$\;$
我们找到这棵树的重心G,把这棵树分为若干个子树,那么发现满足条件的点对只有3种情况:
1.点对在某个子树中(直接递归求解)
2.两个点所构成的路径经过了重心G,但你会发现这两个点一定不能在同一个子树中。
所以我们处理出当前这棵树中每个点的d值,$d_i$表示点$i$到重心G的距离。
那么只需要用$d_i+d_j\leq k$这样$(i,j)$的数量减去$d_i+d_j\leq k$且满足$i,j$在同一个子树中的数量
而你会发现,后者可以在递归子树中处理。
3.这条路经的一个端点是G,那么实质上和2.是一种情况,再加入一个$d_G=0$即可
$\;$

时间复杂度

$\;$
选重心来分割整棵树的目的:
你会发现,这若干棵子树中不会有子树的大小超过原树的一半(否则就与重心的定义不符)
所以最多只会递归$log(n)$层,每一层也是$n$个点。但在递归中还要将处理好的d排序。
总复杂度$O(n log^2 n)$

Code

$\;$
一定要注意:如果在函数里单独开变量而是开全局变量,一定要注意随时清空,防止上一层的答案对下面有影响。

#include <bits/stdc++.h>

const int N = 40010;
int n, k, head[N], tot, f[N], mn, W, vis[N], d[N], ans, q[N], cnt, sz[N];
struct node {
    int to, nxt, val;
}E[N << 1];
void add(int u, int v, int w) {
    E[++tot].to = v; E[tot].nxt = head[u]; E[tot].val = w; head[u] = tot;
}
void dfs(int total, int u, int fa) {
    f[u] = 0; // 一定注意初始化 
    for(int i=head[u];i;i=E[i].nxt) {
        int v = E[i].to;
        if(v == fa || vis[v]) continue;
        dfs(total, v, u);
        f[u] = std::max(f[u], sz[v]);
    }
    f[u] = std::max(f[u], total - sz[u]);
    if(f[u] < mn) {
        mn = f[u]; W = u;
    }
}
void dfs0(int u, int fa) {
    sz[u] = 1; q[++cnt] = d[u]; // 这是在减去2那一部分的时候的d值 
    for(int i=head[u];i;i=E[i].nxt) {
        int v = E[i].to;
        if(v == fa || vis[v]) continue;
        dfs0(v, u); 
        sz[u] += sz[v];
    }
} 
void getG(int rt) {     
    cnt = 0; // 随时清空 
    dfs0(rt, 0); // 预处理好每个点的子树大小(因为随着划分重心,树的形态会变化) 
    mn = 1e9; // 注意初始化 
    dfs(sz[rt], rt, 0); // DP计算重心 
    vis[W] = 1; // 这个点作为重心,将其打上标记(相当于一个边界条件) 
}
void getd(int u, int fa) {
    q[++cnt] = d[u]; // 在求d值的过程中将其存入q数组中,这里是以这棵树为重心是的d值,与上面的d不一样 
    for(int i=head[u];i;i=E[i].nxt) {
        int v = E[i].to;
        if(vis[v] || v == fa) continue;
        d[v] = d[u] + E[i].val; 
        getd(v, u);
    }
}
void solve(int rt) {
    getG(rt);  // 得到重心 
    if(sz[rt] != n) { 
    // 对于2.情况,要减去在相同子树内(i,j)<=k的个数。这个过程是在递归到这个子树中时进行的 
    //但对于一开始整棵树的情况就没必要减了 
        std::sort(q + 1, q + cnt + 1); 
        // q里存储的是这棵子树内的d值
        // 因为树内点的编号不一定是连续的,所以需要开q这个数组存它 
        int e1 = 1, e2 = cnt;
        for(int e1=1;e1<=cnt;e1++) {
            while(e2 > e1 && q[e1] + q[e2] > k) e2 --; // 双指针枚举,复杂度是线性的 
            if(e2 <= e1) break;
            ans -= (e2 - e1);
        }
    }
    d[W] = 0; // 重心的d当然是0 
    cnt = 0; // 一定注意要随时清空 
    getd(W, 0);
    std::sort(q + 1, q + cnt + 1);
    int e1 = 1, e2 = cnt;
    for(int e1=1;e1<=cnt;e1++) {
        while(e2 > e1 && q[e1] + q[e2] > k) e2 --;
        if(e2 <= e1) break;
        ans += (e2 - e1);
    } 
    for(int i=head[W];i;i=E[i].nxt) {
        int v = E[i].to;
        if(!vis[v]) solve(v); // 如果这个点没被打上标记,一定要向下递归 
    }
}
int main() {
    scanf("%d", &n);
    for(int i=1;i<n;i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w); add(v, u, w);
    }
    scanf("%d", &k);
    solve(1);
    printf("%d", ans);
    return 0;
}



ytczy666
1个月前

博客食用更佳~ https://www.cnblogs.com/czyty114/p/14443656.html

引入

$\;$
假设现在我们得到了一个$n$次多项式$f(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n$,$n+1$个条件形如$(x_i,y_i)$,表示当$x=x_i$时,多项式的值为$y_i$
求:$a_0,a_1,\cdots,a_n$
对于这类问题,我们当然可以根据$(x_i,y_i)$写出$n+1$个$n+1$次方程组成的线性方程组,然后再$O(n^3)$的时间内用高斯消元求解
但对于$n\leq 2000$这样的范围,高斯消元就不适用了。
接下来介绍的拉格朗日插值法,时间复杂度是$O(n^2)$的
$\;$

拉格朗日插值

$\;$
我们考虑构造出$n+1$个多项式,满足第$i$个多项式只有当自变量取值为$x_i$时,其值为1,否则为0
那么对于第$i$个多项式,其形式即为:
$$fi(k)=\prod_{i\neq j} \frac{k-x_j}{x_i-x_j}$$
显然,上式是满足条件的。
那么对于原多项式,显然:
$$f(k)=\sum_{i=0}^n y_i fi(k)$$
如果题目只是要求这个多项式在给定$k$下的函数值,显然可以$O(n^2)$来解决。
但如果要求每一项系数,仍然是$O(n^3)$
$\;$

特殊情况

$\;$
若给定的$x_i$是连续的数,即:$x_i=i$,我们来看这个东西有什么更好的性质
$fi(k)$可以变为$\prod_{i\neq j} \frac{k-j}{i-j}$
我们把整个柿子抄一遍
$$f(k)=\sum_{i=0}^n y_i \prod_{i\neq j} \frac{k-j}{i-j}$$
设$h(i)=\prod_{j=0}^i (k-j),r(i)=\prod_{j=i}^n (k-j), fac(i)=i!$,那么:
$$f(k)=\sum_{i=0}^n y_i \frac{h(i-1)r(i+1)}{fac(i)fac(n-i)(-1)^{n-i}}$$
那么我们预处理好$h,r,fac$,$f(k)$就可以$O(n)$的算出来了
但是若要求表达式仍是O(n^3)的
$\;$

优化

$\;$
其实也不算是优化,是为了解决另一种更繁琐的情况,若有时候要减少一个或加入一个插值点,即:$(x_i,y_i)$
按原来的式子还必须重新算一遍,如何优化呢?
观察上面的式子:
$f(k)=\sum_{i=0}^n y_i \prod_{i\neq j} \frac{k-x_j}{x_i-x_j}$
我们发现$k-x_j$这里是与$i$无关的,提到前面。
设$g(k)=\prod_{i=0}^n (k-x_i)$
于是原式就变成了:
$f(k)=g(k) \sum_{i=0}^n \frac{y_i}{k-x_i} \prod_{i\neq j} \frac{1}{x_i-x_j}$
设$t(i)= \prod_{i\neq j} \frac{1}{x_i-x_j}$
$f(k)=g(k) \sum_{i=0}^n \frac{y_it_i}{k-x_i}$
我们发现,$t(1),t(2),\cdots,t(n)$是可以$O(n^2)$预处理的,其余用$O(n)$时间即可解决
那么如果我们要加入一个插值点$(x_{n+1},y_{n+1})$,显然只需要把所有的$t(i)$除以$x_i-x_{n+1}$
这样修改的复杂度是$O(n)$的,然后我们再用$O(n)$的时间求值即可

Code

$\;$
求$f(k)$的值。
代码用的是那个支持加入插值点方法(其实第一种也可以做)

#include <bits/stdc++.h>

const int N = 2010, mod = 998244353;
int n, k, g = 1, t[N], x[N], y[N];
int power(int a, int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1; 
    }
    return ans;
} 
int main() {
    scanf("%d%d", &n, &k); 
    for(int i=0;i<n;i++) scanf("%d%d", &x[i], &y[i]);
    for(int i=0;i<n;i++) g = 1ll * g * (k - x[i] + mod) % mod;
    for(int i=0;i<n;i++) {
        int now = 1;
        for(int j=0;j<n;j++) {
            if(j == i) continue;
            now = 1ll * now * (x[i] - x[j] + mod) % mod;
        }
        t[i] = power(now, mod - 2);
    }
    int ans = 0;
    for(int i=0;i<n;i++) {
        int tmp = 1ll * y[i] * t[i] % mod * power(k - x[i] + mod, mod - 2) % mod;
        ans = (ans + tmp) % mod;
    }
    printf("%d", 1ll * ans * g % mod);
    return 0;
}


分享 莫队算法

ytczy666
1个月前

博客食用更佳~ https://www.cnblogs.com/czyty114/p/14432462.html

$\;$
莫队是一类离线区间询问问题,经常应用于需要维护的信息无法合并时(如线段树等)
其核心思想是:维护两个指针$l,r$。在已知$[l,r]$这段区间的信息的前提下,两个指针分别移动到$l’,r’$的过程中,实时地维护答案。从而算出区间$[l,r]的信息$
$\;$

引入

$\;$
因为题目没有强制在线,所以莫队算法是将所有的询问按一定顺序排好序,并且一次询问是以上一次询问为基础。
我们可以把一次询问$l,r$看作二维平面上的一个点$(l,r)$,那我们在两次询问间$l,r$指针一共移动的距离,实质上是$(l_1,r_1)$,$(l_2,r_2)$间的曼哈顿距离
但求最小哈密尔顿路径又是无法做到的。所以我们需要找到一个合适的顺序,使得两指针移动的距离尽可能的小。
$\;$

核心

$\;$
假设现在给定你一个长为$n$的序列,$m$次询问,每次询问求$[l,r]$这段区间不同数的数量。
$n,m\leq 10^5$
对于这个问题来说,用线段树是很难去维护的。因为区间不同数的数量并不能很轻松地由左右子区间转移而来。
考虑将整个序列分块,每段长度为$\sqrt n$
这样每段询问区间的左右端点必定位于某个块中。
我们把区间左端点所属的块的编号作为第一关键字,右端点的位置作为第二关键字,将询问区间排序。
按照莫队的思想,我们按此顺序依次处理每一个区间,在两个指针的移动的过程中维护一个数组cnt,表示每一个数出现的次数。
若发现某个数cnt为由1减为0了,将答案减1,反之则加1
$\;$

时间复杂度

$\;$
我们发现算法中时间的瓶颈就在于,左右指针总共会移动多少次。我们分开来看:
(注意:这里我们假设m与n同阶)

左端点

$\;$
因为第一关键字是按左端点所在块排序的,所以左端点所在块是单调不降的。
对于目前左端点与上一个左端点同属一个块的情况:最多出现$n$次,但每一次两个点之间移动的距离不超过$\sqrt n$
因此:$O(n\sqrt n)$
对于目前左端点与上一个左端点不同属一个块的情况:最多出现$\sqrt n$次,但每一次两个点之间移动的距离不超过$n$
因此:$O(n\sqrt n)$
$\;$

右端点

$\;$
其位置作为第二关键字。因此若左端点有若干个位于同一个块中,此时右端点应该是单调不降的。
因此对于同一个块的左端点,右端点至多移动$n$次,而总共有$\sqrt n$个块
因此:$O(n\sqrt n)$
否则,若左端点不在同一个块中,右端点的位置就无法确定了。这样一次右端点至多移动$n$次
但这种情况至多出现$\sqrt n$次
因此:$O(n\sqrt n)$
$\;$
综上所述,莫队算法的时间复杂度为$O(n\sqrt n)$

Code

#include <bits/stdc++.h>

const int N = 50010, M = 200010;
int n, m, a[N], b[N], ans[M], id[N], sq, nn, cnt[N];
struct node {
    int pos, l, r;
}ask[M];
bool cmp(node a, node b) {
    if(id[a.l] != id[b.l]) return id[a.l] < id[b.l]; // 左端点所属块 
    return a.r < b.r; // 右端点所属位置 
}
int main() {
    scanf("%d", &n);
    sq = (int)sqrt(n);
    for(int i=1;i<=n;i++) id[i] = (int)ceil(i / sq); // 预处理每个点所属块的编号 
    for(int i=1;i<=n;i++) scanf("%d", &a[i]), b[i] = a[i];
    std::sort(b + 1, b + n + 1);
    nn = std::unique(b + 1, b + n + 1) - b - 1;
    for(int i=1;i<=n;i++) a[i] = std::lower_bound(b + 1, b + nn + 1, a[i]) - b;
    //----------------- 上面是离散化部分,不多赘述 
    scanf("%d", &m);
    for(int i=1;i<=m;i++) scanf("%d%d", &ask[i].l, &ask[i].r), ask[i].pos = i;
    std::sort(ask + 1, ask + m + 1, cmp);
    int x = 0, y = 0, res = 0; //x,y维护的是一直在移动两个指针 
    for(int i=1;i<=m;i++) {
        int l = ask[i].l, r = ask[i].r; // l,r是当前询问的两个左右端点 
        while(x < l) { // 左端点向右移,区间缩小 
            cnt[a[x]] --; if(!cnt[a[x]]) -- res;
            x ++;
        }

        while(x > l) { // 左端点向左移,区间变大 
            cnt[a[x - 1]] ++; if(cnt[a[x - 1]] == 1) ++ res;
            x --;
        }

        while(y < r) { // 右端点向右移,区间变大 
            cnt[a[y + 1]] ++; if(cnt[a[y + 1]] == 1) ++ res;
            y ++;
        }

        while(y > r) { // 右端点向左移,区间缩小 
            cnt[a[y]] --; if(!cnt[a[y]]) -- res;
            y --;
        }

        ans[ask[i].pos] = res; // 注意:i是排序后区间的编号,但并不是输入时询问的编号 
    }
    for(int i=1;i<=m;i++) printf("%d\n", ans[i]);
    return 0;
}


活动打卡代码 AcWing 499. 聪明的质监员

ytczy666
2个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 503. 借教室

ytczy666
2个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~