2022-11-10总结

GCD 和 LCM

Description

$T$ 个询问，每次询问给出三个整数 $n, m, a$，求：

$$\sum_{i=1}^{n} \sum_{j=1}^{m} \operatorname{lcm}(i,j) [\gcd(i,j) \le a]$$

Input

第一行读入 $T$。

接下来 $T$ 行，每行三个整数 $n, m, a$。

Output

$T$ 行，表示每个询问的答案。

Hint

$T \le 10^4, n,m,a \le 10^5$

Solution

套路莫比乌斯反演，下面设 $n \le m$。

$$\sum_{i=1}^{n} \sum_{j=1}^{m} \operatorname{lim}(i,j) [\gcd(i,j) \le a] \\ = \sum_{d=1}^{\min(n,a)} \frac{1}{d} \sum_{i=1}^{n} \sum _{i=1}^{m} ij [\gcd(i,j) = d] \\ = \sum_{d=1}^{\min(n,a)} d \sum_{i=1}^{ \lfloor \frac{n}{d} \rfloor } \sum_{j=1}^{ \lfloor \frac{m}{d} \rfloor } ij [\gcd(i,j)=1] \\ = \sum_{d=1}^{\min(n,a)} d \sum_{i=1}^{ \lfloor \frac{n}{d} \rfloor } \sum_{j=1}^{ \lfloor \frac{m}{d} \rfloor} ij \sum_{t|\gcd(i,j)} \mu(t) \\ = \sum_{d=1}^{min(n,a)} d \sum_{t=1}^{ \lfloor \frac{n}{d} \rfloor} \mu(t) t^2 \sum_{i=1}^{ \lfloor \frac{n}{dt} \rfloor } i \sum_{j=1}^{ \lfloor \frac{m}{dt} \rfloor } j$$

设 $S(x) = \sum_{i=1}^x i = \frac{x(x+1)}{2}$，继续化简：

$$\sum_{d=1}^{min(n,a)} d \sum_{t=1}^{ \lfloor \frac{n}{d} \rfloor} \mu(t) \sum_{i=1}^{ \lfloor \frac{n}{dt} \rfloor } i \sum_{j=1}^{ \lfloor \frac{m}{dt} \rfloor } j \\ = \sum_{d=1}^{\min(n,a)} d \sum_{t=1}^{ \lfloor \frac{n}{d} \rfloor } \mu(t) t^2 S(\lfloor \frac{n}{dt} \rfloor) S(\lfloor \frac{m}{dt} \rfloor)$$

如果两次整除分块的话询问一次是 $O(n^{\frac{3}{4}})$ 的，但是有多组询问，所以考虑 $T=dt$ 的换元，搞成一个整除分块：

$$\sum_{d=1}^{\min(n,a)} d \sum_{t=1}^{ \lfloor \frac{n}{d} \rfloor } \mu(t) S(\lfloor \frac{n}{dt} \rfloor) S(\lfloor \frac{m}{dt} \rfloor) \\ = \sum_{T=1}^{n} \sum_{d|T, d \le a} \frac{T^2}{d} \mu(\frac{T}{d}) S(\lfloor \frac{n}{T} \rfloor) S(\lfloor \frac{m}{T} \rfloor)$$

如果没有 $d \le a$ 的限制，可以 $O(n \ln n)$ 预处理出 $f(T) = \sum_{d|T} \frac{T^2}{d} \mu(\frac{T}{d})$，然后每次询问就是 $O(\sqrt n)$ 的了。

如果有 $d \le a$ 的限制，我们可以把询问按 $a$ 从小到大排序，然后动态维护 $f(T)$ 的前缀和，这个可以用树状数组解决，一共 $O(n \ln n)$ 次单点加，$O(T \sqrt n)$ 次询问，所以时间复杂度是 $O(n \ln n \log n + T \sqrt n \log n)$。

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

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

namespace sieve {
    bool vis[N];
    int prime[N], pcnt;
    ll mu[N];
    void main()
    {
        mu[1] = 1;
        for(int i = 2; i <= A; i++)
        {
            if(!vis[i]) prime[++pcnt] = i, mu[i] = -1;
            for(int j = 1; j <= pcnt and i*prime[j] <= A; j++)
            {
                vis[i*prime[j]] = true;
                if(i%prime[j] == 0) break;
                else mu[i*prime[j]] = -mu[i];
            }
        }
    }
}
namespace bit {
    ll a[N];
    #define lowbit(i) (i&-i)
    void add(int x, ll v) { for(; x <= A; x += lowbit(x)) (a[x] += v) %= P; }
    ll get(int x) { ll ans = 0; for(; x >= 1; x -= lowbit(x)) (ans += a[x]) %= P; return ans; }
    ll get(int l, int r) { return (get(r)-get(l-1)+P)%P;}
}

using namespace bit;
using namespace sieve;

int tot; ll ans[N];
struct query { int n, m, a, id; } q[N];

ll solve(int n, int m);
ll S(ll x) { return x*(x+1)/2%P; }

int main()
{
    sieve::main();
    
    read(tot);
    for(int i = 1; i <= tot; i++)
        read(q[i].n, q[i].m, q[i].a), q[i].id = i;
    sort(q+1, q+tot+1, [&](query a, query b){
        return a.a < b.a;
    });
    
    int d = 0;
    for(int i = 1; i <= tot; i++)
    {
        while(d < q[i].a)
        {
            d++;
            for(ll T = d; T <= A; T += d)
                bit::add(T, T*T/d%P * (mu[T/d]+P)%P);
        }
        ans[q[i].id] = solve(q[i].n, q[i].m);
    }
    
    for(int i = 1; i <= tot; i++)
        print(ans[i], '\n');
}

ll solve(int n, int m)
{
    if(n > m) swap(n, m);
    ll sum = 0;
    for(int l = 1, r; l <= n; l = r+1)
    {
        r = min(n/(n/l), m/(m/l));
        sum += bit::get(l, r) * S(n/l)%P * S(m/l)%P;
        sum %= P;
    }
    return sum;
}

平面图

Description

给定一个联通的平面图，接下来有 $q$ 次操作：

• 操作 “-”: 删除边 $(x, y)$，并询问删完后有几个联通块。
• 操作 “?”: 询问 $x, y$ 是否在同一个联通块内，如果是输出 $1$，否则输出 $0$。

Input

第一行 $n, q$。

接下来 $n$ 行，每行先读入 $k$，表示点的度数，再读入 $k$ 个数，表示该点顺时针依次与哪些点相连。

接下来 $q$ 行读入 $opt, x, y$, 表示一组询问。

询问强制在线， $x, y$ 需要异或上一次的答案 $lastans$, $lastans$ 初始为 $0$。

Output

$q$ 行，对于每个询问输出答案。

Hint

$n \le 10^5, m \le 2 \times 10^5$。

Solution

首先删边维护连通性不好做(如果写一般图的动态联通性也不拦着你)，考虑怎么转化成加边操作，看到平面图想到转对偶图，在网络流问题中有平面图最小割等于对偶图最短路，在这个模型中，我们将对偶图的一条路径看作原图的一个割，这题中我们可以把对偶图连一条边看成原图的删一条边。

如果对偶图连出来一个环，那么在原图上就会割出来一个新的连通块(对偶图连出来环代表这一部分被删完边之后的空白区域围起来了，就与其他部分不连通了)，直接用并查集判断连一条边是否会出现环即可，第一个询问就做完了。

考虑第二个询问，原图的两点是否联通好像与对偶图没有太大关系，我们直接在原图上做，我们由第一问可以知道删一条边的时候是否会把一个部分割成两个联通块，我们可以在原图上做相应的删边，如果删去 $(x,y)$ 后连通块数量会增加，那么删完 $(x,y)$ 后 $x$ 和 $y$ 必定属于不同的连通块，所以我们可以从 $x,y$ 出发进行一个 bfs 的做，选择一个小的连通块，给这个连通块标上新的标号，这样就与其他连通块区分开来了，其实就是启发式分裂。但是为了保证复杂度，我们可以每次尝试只拓展一个点，当其中一个连通块不能拓展后就退出，这样的话拓展次数就等于小的连通块的大小，可以保证时间复杂度不会假。

还有一个重要操作是建出对偶图，我们可以从把原图的一条 $(x,y)$ 的边拆成两条有向边 $x \rightarrow y, y \rightarrow x$，然后枚举每条有向边 $x \rightarrow y$，从 $y$ 点出发，找到 $y$ 的出边中，在 $y \rightarrow x$ 这条边的顺时针方向上的第一条边 $y \rightarrow z$，经过这条边到达 $z$，然后重复上述步骤，直到走回 $y$，所走过的边一定是一个环，我们将这个环的边赋上一个编号，代表它们围起来的空白区域的编号。

可以发现通过上面的操作，每个有向边都会获得一个编号，这个编号就是这条有向边左边的空白区域的编号，对于原图的一条边 $(x, y)$，$id(x \rightarrow y)$ 和 $id(y \rightarrow x)$ 即为 $(x,y)$ 两边的空白区域的编号。

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

typedef pair<int,int> pir;
const int N = 1e5+10;

int n, q, cnt; // cnt是面的数量
int belong[N], num; // 原图上每个点所属的连通块
int cur[N]; bool vis[N];
map<pir, int> mp; // (x,y) 在 ver[x] 中的编号 (ver[x]按顺时针排序)
map<pir, int> id; // 每条边所属的面
vector<int> ver[N];

namespace dsu {
    int f[N*10];
    void init(int n) { for(int i = 1; i <= n; i++) f[i] = i; }
    int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
    inline void merge(int x, int y) { f[find(y)] = find(x); }
    inline bool check(int x, int y) { return find(x) == find(y); }
}

void toggle(int x, int pre, int st);
bool extend(vector<int> &v, int &st);

int main()
{
    read(n, q);
    for(int x = 1; x <= n; x++)
    {
        int k; read(k);
        for(int i = 1; i <= k; i++)
        {
            int y; read(y);
            ver[x].push_back(y);
            mp[{x,y}] = i-1;
        }
    }
    for(int x = 1; x <= n; x++)
    {
        for(auto y : ver[x])
        {
            if(id.count({x,y})) continue;
            id[{x,y}] = ++cnt;
            toggle(y, x, x);
        }
    }
    
    for(int x = 1; x <= n; x++)
        sort(ver[x].begin(), ver[x].end());
    
    dsu::init(cnt);
    char opt; int x, y;
    int tot = 1, lastans = 0;
    for(int i = 1; i <= q; i++)
    {
        read(opt, x, y);
        x ^= lastans;
        y ^= lastans;
        if(opt == '-')
        {
            int a = id[{x,y}], b = id[{y,x}];
            
            ver[x].erase(lower_bound(ver[x].begin(), ver[x].end(), y));
            ver[y].erase(lower_bound(ver[y].begin(), ver[y].end(), x));
            
            if(dsu::check(a, b))
            {
                tot++;
                
                vector<int> v1, v2;
                int p1 = 0, p2 = 0;
                v1.push_back(x);
                v2.push_back(y);
                
                while(true)
                {
                    if(!extend(v1, p1)) { num++; for(auto i : v1) belong[i] = num; break; }
                    if(!extend(v2, p2)) { num++; for(auto i : v2) belong[i] = num; break; }
                }
                for(auto i : v1) cur[i] = vis[i] = 0;
                for(auto i : v2) cur[i] = vis[i] = 0;
            }
            else dsu::merge(a, b);
            
            print(lastans = tot, '\n');
        }
        else
            print(lastans = (belong[x]==belong[y]), '\n');
    }
    
}

void toggle(int x, int pre, int st)
{
    if(x == st) return void();
    int p = mp[{x,pre}];
    p = (p+1)%ver[x].size(); // 顺时针的下一条边
    int y = ver[x][p];
    id[{x,y}] = cnt;
    toggle(y, x, st);
}


bool extend(vector<int> &v, int &st)
{
    for(; st < v.size(); st++)
    {
        int x = v[st];
        for(int i = cur[x]; i < ver[x].size(); cur[x] = ++i)
        {
            int y = ver[x][i];
            if(!vis[y])
            {
                vis[y] = true;
                v.push_back(y);
                return true;
            }
        }
    }
    return false;
}

/*
4 3
3 2 3 4
2 1 4
1 1
2 1 2
- 1 2
- 0 2
? 3 1

1
2
0
*/