Home

# owo

# 题目描述

有两组玩家进行游戏，第一组有 nn 个人，第二组有 mm 个人，两组之间玩家两两进行比赛，共 n×mn \times m 场。
第一组玩家的能力值为 a1,a2,…,ana_1, a_2, \dots, a_n，第二组玩家的能力值为 b1,b2,…,bmb_1, b_2, \dots, b_m。其中能力值为 1∼21 \sim 2 之间的浮点数。两个能力值为 aa 和 bb 的玩家进行比赛时，能力值为 aa 的玩家获胜的概率是 aa+b\frac{a}{a+b}。
请求出所有比赛结束后，第一组每个・玩家获胜场次的期望。(n,m≤106n,m \le 10^6)
输出共 nn 行，每行一个实数，第 ii 行的实数表示第一组第 ii 个人获胜的期望场次，要求绝对误差在 10−310^{-3} 以内。

# 解题思路

# 方法一

这是个发扬人类智慧的时刻，由于精度的要求在 10−310^{-3} 以内，我们就能把 1∼21 \sim 2 的实数值域转化成 104∼2∗10410^4 \sim 2*10^4 的整数值域，开个桶存一下每个数的出现次数，然后对着值域搞就可以了。

# 方法二

当方法一被更高的精度要求卡住后，就轮到正解出场了。

首先我们要知道 泰勒展开

函数 f(x)f(x) 在 x=x0x = x_0 泰勒展开的公式为：
f(x)=∑i=0∞f(i)(x0)i!(x−x0)if(x) = \sum\limits_{i = 0}^{\infty}\frac{f^{(i)}(x_0)}{i!}(x-x_0)^i

我们转化一下问题，用所有场次减去期望输的场次，问题变成了 m−∑i=1mbia+bim- \sum\limits_{i=1}^m{\frac{b_i}{a+b_i}}

求得 h(x,k)=bkx+bkh(x, k) = \frac{b_k}{x+b_k} 的 nn 阶导数为 n!×bk(a+bk)(n+1)\frac{n! \times b_k}{(a+b_k)^(n+1)} (可以用归纳法求得)

定义 f(x)=∑j=1mh(x,j)f(x) = \sum\limits_{j = 1}^{m}h(x,j)。

将 h(x,j)h(x,j) 的泰勒展开式带入得
∑j=0m∑i=0∞bjf(i)(x0)(a+bj)(i+1)(x−x0)i\sum\limits_{j=0}^{m} \sum\limits_{i=0}^{\infty}{\frac{b_jf^{(i)}(x_0)}{(a+b_j)^{(i+1)}}(x-x_0)^{i}}

由于x∈[1,2]x \in [1, 2]，我们取 x0=1.5x_0 = 1.5 使 (x−x0)∈[−0.5,0.5](x-x_0) \in [-0.5, 0.5]，则 lim⁡x→∞(x−x0)i=0\lim\limits_{x \to \infty}(x-x_0)^i = 0，在 i=30i = 30 时上述式子的取值已经小于 10−910^{-9} 所有在这个题的精度下泰勒展开的前 3030 项已经满足精度需要了。

最后就是 f(x)=∑i=030(∑j=0mbjf(i)(x0)(a+bj)(i+1))(x−x0)if(x) = \sum\limits_{i = 0}^{30}\left(\sum\limits_{j = 0}^{m}\frac{b_jf^{(i)}(x_0)}{(a+b_j)^{(i+1)}}\right)(x-x_0)^i
我们将 x=1.5x = 1.5 带入，求得每一个 ii 的 ∑j=0mbjf(i)(x0)(a+bj)(i+1)\sum\limits_{j = 0}^{m}\frac{b_jf^{(i)}(x_0)}{(a+b_j)^{(i+1)}} 储存起来，对于每一个询问就可以 O(m)O(m) 处理了（带一个 3030 的小常数）。

# Code

\Large

#define Aniciry Meteorshower_Y
#include<iostream>
#include<cstdio>
using namespace std;
using namespace Octane;
const int A = 1e4+0;
const int B = 2e4+0;
const int N = 1e6+10;
const int M = 2e4+10;
struct Meteorshower_Y{
    Meteorshower_Y(){
    freopen("owo.in", "r", stdin);
    freopen("owo.out", "w", stdout);    
}};Meteorshower_Y Aniciry;
int n, m, ta[M], tb[M];
double a[N], b[N], f[M];
int main()
{
    read(n, m);
    for(int i = 1; i <= n; i += 1)
        read(a[i]), ta[(int)(a[i]*A)] += 1;
    for(int i = 1; i <= m; i += 1)
        read(b[i]), tb[(int)(b[i]*A)] += 1;
    for(int i = A; i <= B; i += 1)
    {
        if(!ta[i]) continue;
        for(int j = A; j <= B; j += 1)
        {
            if(!tb[j]) continue;
            f[i] += tb[j]*((double)i/(i+j));
        }
    }
    setpcs(4);
    for(int i = 1; i <= n; i += 1)
        print(f[(int)(a[i]*A)], '\n');
    return 0;
}

# tvt

# 题目描述

nn 个城市形成了树形结构，每条边都有长度，经过长度为 ww 的边需要的时间为 ww。对于一组询问，dqrdqr 会在 t1t_1 时刻出发，从 u1u_1 走向 v1v_1，cyrcyr 会在 t2t_2 时刻出发，从 u2u_2 走向 v2v_2。请问两人是否会有超过 00 的时间在同一条边上 (顶点并不被包括在边内)。(n,q≤105)(n,q\le 10^5)

# 解题思路

第一步我们需要判断两条路径是不是有交，无交或者交仅为一个节点就直接输出 NoNo。
判断有无交的方法：树上路径求交
然后我们需要判断他们在链（路径交的链）上的方向。

  1. 如果是同向，那么路径上存在一条边的长度大于两人到路径起点的时间差，那么就会有在同一条边上的情况出现，否则则无。
  2. 如果是相向，需要找出他们在路径上相遇的位置，可以树剖然后重链上二分，或者直接倍增向上跳。

# Code

#define Aniciry Meteorshower_Y
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 1e5+10;
#define int long long
struct Meteorshower_Y{
    Meteorshower_Y(){
    freopen("tvt.in", "r", stdin);
    freopen("tvt.out", "w", stdout);
}};Meteorshower_Y Aniciry;
struct node{int s, t, T;};
namespace HLDT
{
    struct edge{
        int from, to;
        int dis, next;
    }a[N<<1];
    int head[N], cnt, tim;
    int f[N], w[N], siz[N], son[N];
    int id[N], aid[N], dep[N], top[N], dis[N];
    inline auto LCA(int x, int y) -> int;
    inline auto dist(int x, int y) -> int;
    inline auto dfs1(int x, int fa) -> void;
    inline auto dfs2(int x, int tp) -> void;
    inline auto solve(node a, node b) -> int;
    inline auto querydis(int x, int y) -> int;
    inline auto add_edge(int from, int to, int dis) -> void;
}
namespace Stree
{
    struct tree{
        int l, r, mx;
    }tr[N<<2];    
    inline auto build(int l, int r, int i) -> void;
    inline auto query_max(int l, int r, int i) -> int;
}using namespace Stree;
namespace binary_lifting
{
    const int M = 1<<17;
    int to[18][M*2], d[18][M*2];
    inline auto init() -> void;
    inline auto up(int x, int dis) -> int;
}
int n, q, u, v, w;
inline auto _abs(int x) -> int;
auto main() -> signed 
{
    scanf("%lld%lld", &n, &q);
    for(int i = 1; i < n; i += 1)
    {
        scanf("%lld%lld%lld", &u, &v, &w);
        HLDT::add_edge(u, v, w);
        HLDT::add_edge(v, u, w);
    }
    HLDT::dfs1(1, 0);
    HLDT::dfs2(1, 1);
    Stree::build(1, n, 1);
    binary_lifting::init();
    node x, y;
    for(int i = 1; i <= q; i += 1)
    {
        scanf("%lld%lld%lld", &x.s, &x.t, &x.T);
        scanf("%lld%lld%lld", &y.s, &y.t, &y.T);
        printf(HLDT::solve(x, y)?"YES\n":"NO\n");
    }
    return 0;
}
inline auto _abs(int x) -> int {return x >= 0 ? x : -x;}
namespace HLDT
{
    inline auto solve(node a, node b) -> int
    {
        static int lca[4];
        lca[0] = LCA(a.s, b.s);
        lca[1] = LCA(a.t, b.t);
        lca[2] = LCA(a.s, b.t);
        lca[3] = LCA(a.t, b.s);
        sort(lca, lca+4, [](int a, int b){return dep[a] > dep[b];});
        if(lca[0] == lca[1]) return false;
        int u = lca[0], v = lca[1];
        static int dir_1, dir_2;
        static int dis1_u, dis1_v;
        static int dis2_u, dis2_v;
        dis1_u = dist(a.s, u)+a.T;
        dis1_v = dist(a.s, v)+a.T;
        dis2_u = dist(b.s, u)+b.T;
        dis2_v = dist(b.s, v)+b.T;
        dir_1 = (dis1_u < dis1_v) ? (0) : (1);
        dir_2 = (dis2_u < dis2_v) ? (0) : (1);
        if(dir_1 == dir_2)
        {
            static int deltaT;
            deltaT = _abs((dir_1)?(dis1_v-dis2_v):(dis1_u-dis2_u));
            if(querydis(u, v) > deltaT) return true;
            else return false;
        }
        else if(!dir_1 and dir_2)
        {
            if(dis1_v < dis2_v) return false;
            if(dis2_u < dis1_u) return false;
            static int p, t1, t2;
            static int deltaT, walking;
            t1 = dis1_u, t2 = dis2_v;
            deltaT = t1-t2;
            walking = dist(u, v)-_abs(deltaT);
            if(walking&1) return true; walking /= 2;
            p = LCA(u, v);
            if(t1 <= t2)
            {
                if(walking <= dist(v, p))
                {
                    if(binary_lifting::up(v, walking)) return true;
                    else return false;
                }
                else
                {
                    if(binary_lifting::up(u, walking+_abs(deltaT))) return true;
                    else return false;
                }
            }
            else
            {
                if(walking <= dist(u, p))
                {
                    if(binary_lifting::up(u, walking)) return true;
                    else return false;
                }
                else
                {
                    if(binary_lifting::up(v, walking+_abs(deltaT))) return true;
                    else return false;
                }
            }
        }
        else
        {
            if(dis1_u <= dis2_u) return false;
            if(dis1_v >= dis2_v) return false;
            static int p, t1, t2;
            static int deltaT, walking;
            t1 = dis1_v, t2 = dis2_u;
            deltaT = t1-t2;
            walking = dist(u, v)-_abs(deltaT);
            if(walking&1) return true; walking /= 2;
            p = LCA(u, v);
            if(t1 <= t2)
            {
                if(walking <= dist(u, p))
                {
                    if(binary_lifting::up(u, walking)) return true;
                    else return false;
                }
                else 
                {
                    if(binary_lifting::up(v, walking+_abs(deltaT))) return true;
                    else return false;
                }
            }
            else
            {
                if(walking <= dist(v, p))
                {
                    if(binary_lifting::up(v, walking)) return true;
                    else return false;
                }
                else
                {
                    if(binary_lifting::up(u, walking+_abs(deltaT))) return true;
                    else return false;
                }
            }
        }
    }
    inline auto dist(int x, int y) -> int
    {
        return dis[x]+dis[y]-2*dis[LCA(x, y)];
    }
    inline auto LCA(int x, int y) -> int
    {
        while(top[x] != top[y])
        {
            if(dep[top[x]] > dep[top[y]]) x = f[top[x]];
            else y = f[top[y]];
        }
        return dep[x] < dep[y] ? x : y;
    }
    inline auto querydis(int x, int y) -> int
    {
        int ans = 0;
        while(top[x] != top[y])
        {
            if(dep[top[x]] < dep[top[y]]) swap(x, y);
            ans = max(ans, query_max(id[top[x]], id[x], 1));
            x = f[top[x]];
        }
        if(id[x] == id[y]) return ans;
        if(id[x] > id[y]) swap(x, y);
        return max(ans, query_max(id[x]+1, id[y], 1));
    }
    inline auto dfs1(int x, int fa) -> void
    {
        dep[x] = dep[fa]+1;
        f[x] = fa; siz[x] = 1;
        for(int i = head[x], y; i; i = a[i].next)
        {
            if(y = a[i].to, y == fa) continue;
            w[y] = a[i].dis; dis[y] = dis[x]+a[i].dis;
            dfs1(y, x); siz[x] += siz[y];
            if(siz[y] > siz[son[x]]) son[x] = y;
        }
    }
    inline auto dfs2(int x, int tp) -> void
    {
        top[x] = tp; id[x] = ++tim; aid[tim] = x;
        if(son[x]) dfs2(son[x], tp);
        for(int i = head[x], y; i; i = a[i].next)
        {
            if(y = a[i].to, y == f[x] or y == son[x]) continue;
            dfs2(y, y);
        }
    }
    inline auto add_edge(int from, int to, int dis) -> void
    {
        cnt += 1;
        a[cnt].from = from;
        a[cnt].to = to;
        a[cnt].dis = dis;
        a[cnt].next = head[from];
        head[from] = cnt;
    }
}
namespace Stree
{
    #define ls(i) (i<<1)
    #define rs(i) (i<<1|1)
    inline auto build(int l, int r, int i) -> void
    {
        tr[i].l = l;
        tr[i].r = r;
        if(l == r) return (void)(tr[i].mx = HLDT::w[HLDT::aid[l]]);
        int mid = (l+r)>>1;
        build(l, mid, ls(i));
        build(mid+1, r, rs(i));
        tr[i].mx = max(tr[ls(i)].mx, tr[rs(i)].mx);
    }
    inline auto query_max(int l, int r, int i) -> int
    {
        if(tr[i].l > r or tr[i].r < l) return 0;
        if(tr[i].l >= l and tr[i].r <= r) return tr[i].mx;
        return max(query_max(l, r, ls(i)), query_max(l, r, rs(i)));
    }
}
namespace binary_lifting
{
    inline auto init() -> void
    {
        memset(d, 0x3f, sizeof(d));
        for(int i = 2; i <= n; i += 1)
            to[0][i] = HLDT::f[i];
        for(int i = 1; i <= n; i += 1)
            d[0][i] = HLDT::w[i];
        for(int k = 1; k <= 17; k += 1)
            for(int i = 1; i <= n; i += 1)
            {
                to[k][i] = to[k-1][to[k-1][i]];
                d[k][i] = min(d[k][i], d[k-1][i]+d[k-1][to[k-1][i]]);
            }
    }
    inline auto up(int x, int dis) -> int
    {
        for(int i = 17; i >= 0; i -= 1)
            if(d[i][x] <= dis) dis -= d[i][x], x = to[i][x];
        return dis;
    }
}

# 环

# 题目描述

对于一个长度为 nn 的 01 串，下标从 00 到 n−1n-1。
定义两种类型的操作:

  1. 选择一个 xx，将这个 01 序列循环右移 xx 位，原序列的第 ii 位移动到 (i+x)mod  n(i+x) \mod n 位。
  2. 选择一个 xx，满足序列第 xx 个位置为 1 ，且 第(x+1)mod  n(x+1) \mod n 个位置为 0 ，然后交换这两个位置。

给定 nn，kk，ll (2≤n，l≤100，0≤k≤n)(2 \le n，l \le 100， 0 \le k \le n)，请尝试构造 ll 个长度为 nn 的 01 序列 SiS_i (下标从 00 开始算)，该序列中恰好有 kk 个 1 。而且要满足 ∀i∈[0,l−1]\forall i \in [0,l -1]，SiS_i 既可以通过一次操作一变成 Si+1S_{i+1}，也可以通过一次操作二变成 Si+1S_{i+1}。若无解则输出 NO ，有解则第一行输出 YES ，并在接下来 ll 行输出你的方案 (如果解法不唯一，输出任意一种即可)。

# 解题思路

对于每个 SiS_i，记录其 1 所处下标和为 WiW_i，对于每一次操作一，相当于将 WiW_i 加上 kxkx；对于每一次操作二，相当于将 WiW_i 加上 11。
于是我们得出了以下式子：

Wi+kx≡Wi+1(modn)Wi+1≡Wi+1(modn)\begin{aligned} W_i + kx &\equiv W_{i+1} \pmod {n} \\ W_i + 1 &\equiv W_{i+1} \pmod {n} \end{aligned}

所以得到：

kx≡1(modn)\begin{aligned} kx \equiv 1 \pmod {n} \end{aligned}

显然有解的前提是 kk 和 nn 互质，下面我们就开始构造这个序列。
另 Si={ik,i+1k…,i+k−1k}S_i = \{ \frac{i}{k}, \frac{i+1}{k} \dots , \frac{i+k-1}{k} \}
这样每次右移 1k\frac{1}{k} 位之后就能和下一位对上，操作一的要求这样就满足了。
对于操作二，对于 SiS_i 来说将 ik\frac{i}{k} 和 ik+1\frac{i}{k}+1 交换位置，ik\frac{i}{k} 位置上的 1 就到了 i+kk\frac{i+k}{k} 的位置上，SiS_i 也就变成了 Si+1S_{i+1} 操作二也满足，构造正确。

# Code

#define Aniciry Meteorshower_Y
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
int T, n, k, l, x, S[110];
auto work() -> void;
auto Ex_Gcd(int a, int b, int &x, int &y) -> void;
int main()
{
    scanf("%d", &T);
    while(T--) work();
}
auto work() -> void
{
    scanf("%d%d%d", &n, &k, &l);
    static int d, x, y;
    if((d = __gcd(n, k)) != 1) return (void)(printf("NO\n"));
    printf("YES\n"); 
    Ex_Gcd(k, n, x, y);
    x -= ((x-(n-1))/n)*n;
    for(int i = 0; i < l; i += 1)
    {
        for(int j = 0; j < k; j += 1) S[(j+i)*x%n] = 1;
        for(int j = 0; j < n; j += 1) printf("%d", S[j]);
        printf("\n"); memset(S, 0, n*4);
    }
}
auto Ex_Gcd(int a, int b, int &x, int &y) -> void
{
    if(!b) return (void)(x = 1, y = 0);
    Ex_Gcd(b, a%b, y, x);
    y -= (a/b)*x;
}

# 探寻

# 题目描述

给定一棵 nn 个点， n−1n-1 条边的树，边带权，节点编号为 0∼n−10 \sim n-1 ，其中根的编号为 00，一开始你在根上，第一次走一条边需要花与边权相同数目的钱，走过一次这条边后再走这条边就不需要花钱，如果钱不够则不能走，第一次走到一个点 xx 可以获得 valxval_x 的钱，之后再到达 xx 就不会获得钱，标记其中一个叶子为目标节点，求出到达目标节点所需的最少的初始钱数。

# 解题思路

考虑贪心做法，每次走花费小的，收益大的，但 显然 是错的，因为没有考虑走完这一步之后的情况，所以在贪心时需要考虑上子树内的情况。
这启发我们从叶子开始向上合并信息，对于每个点记录最低的启动资金 needxneed_x 和最大收益 gainxgain_x 在保证收益为正的情况下使启动资金尽可能的少，然后每个点维护一个堆 (可并堆)，当然不可并的话启发式合并也是可以的，维护子树内收益非负的联通块，向上合并到根，根的最小启动资金就是答案。

# Code

#define Aniciry Meteorshower_Y
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const ll inf = 1e18;
const int N = 2e5+10;
struct node{ ll need, gain;
    friend bool operator<(node a, node b){
        return a.need < b.need;
    }
    friend bool operator>(node a, node b){
        return a.need > b.need;
    }
};
int n, cnt, head[N]; 
int to[N], nxt[N];
ll val[N], cost[N];
__gnu_pbds::priority_queue<node,greater<node> > q[N];
inline auto dfs(int x) -> void;
inline auto add_edge(int from, int to) -> void;
int main()
{
    read(n); cost[1] = inf;
    for(int i = 2, fa, v; i <= n; i += 1)
    {
        read(fa, val[i], cost[i]);
        add_edge(fa+1, i);
        if(val[i] == -1) val[i] = inf<<1;
    }
    dfs(1); print(q[1].top().need-inf);
    return 0;
}
inline auto dfs(int x) -> void
{
    for(int i = head[x]; i; i = nxt[i])
        dfs(to[i]), q[x].join(q[to[i]]);
    ll need = cost[x], gain = val[x]-cost[x]; node now;
    while(!q[x].empty() and (gain < 0 or need >= q[x].top().need))
    {
        now = q[x].top(); q[x].pop();
        if(need+gain < now.need)
            need += now.need-(need+gain);
        gain += now.gain;
    }
    if(gain > 0) q[x].push({need, gain});
}
inline auto add_edge(int from, int to) -> void
{
    cnt += 1;
    ::to[cnt] = to;
    nxt[cnt] = head[from];
    head[from] = cnt;
}

# GCD 和 LCM

# 题目描述

现在有 TT 询问，每个询问给三个整数 nn，mm，aa，求对于所有 1≤i≤n,1≤j≤m,1≤gcd⁡(i,j)≤a1 \le i \le n, 1 \le j \le m, 1 \le \gcd(i,j) \le a 的 ii，jj，∑i=1n∑j=1mlcm⁡(i,j)\sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{m}{\operatorname{lcm}(i,j)}} 的值。
结果对 109+710^9+7 取模。
1≤T≤104,1≤n,m,a≤1051 \le T \le 10^4,1 \le n,m,a \le 10^5

# 解题思路

其实就是推式子
先把 aa 的限制放到一边，然后就是莫反的经典套路
记 A=min⁡(n,m)A = \min(n, m), T=dkT = dk, S(n)=n×(n+1)2S(n) = \frac{n \times (n+1)}{2},

∑i=1n∑j=1mlcm⁡(i,j)[gcd⁡(i,j)≤a]=∑i=1n∑j=1mi⋅jgcd⁡(i,j)[gcd⁡(i,j)≤a]=∑d=1A∑i=1n∑j=1mi⋅jd[gcd⁡(i,j)=d][d≤a]=∑d=1A∑i=1⌊nd⌋∑j=1⌊md⌋ijd[gcd⁡(i,j)=1][d≤a]=∑d=1A∑i=1⌊nd⌋∑j=1⌊md⌋ijd∑k∣gcd⁡(i,j)μ(k)[d≤a]=∑d=1Ad∑k=1⌊Ad⌋k2μ(k)∑i=1⌊ndk⌋i∑j=1⌊mdk⌋j[d≤a]=∑d=1Ad∑k=1⌊Ad⌋k2μ(k)S⁡(⌊ndk⌋)S⁡(⌊mdk⌋)[d≤a]=∑T=1AS⁡(⌊nT⌋)S⁡(⌊mT⌋)∑d∣TT2dμ(Td)[d≤a]\begin{aligned} &\sum_{i = 1}^{n} \sum_{j = 1}^{m} \operatorname{lcm}(i,j) [\gcd(i, j) \le a] \\ = &\sum_{i = 1}^{n} \sum_{j = 1}^{m} \frac{i \cdot j}{\gcd(i, j)} [\gcd(i, j) \le a] \\ = &\sum_{d = 1}^{A} \sum_{i = 1}^{n} \sum_{j = 1}^{m} \frac{i \cdot j}{d} [\gcd(i, j) = d] [d \le a] \\ = &\sum_{d = 1}^{A} \sum_{i = 1}^{\lfloor\frac{n}{d}\rfloor} \sum_{j = 1}^{\lfloor\frac{m}{d}\rfloor} ijd [\gcd(i, j) = 1] [d \le a] \\ = &\sum_{d = 1}^{A} \sum_{i = 1}^{\lfloor\frac{n}{d}\rfloor} \sum_{j = 1}^{\lfloor\frac{m}{d}\rfloor} ijd \sum_{k | \gcd(i, j)} \mu(k) [d \le a] \\ = &\sum_{d = 1}^{A} d \sum_{k = 1}^{\lfloor\frac{A}{d}\rfloor} k^2 \mu(k) \sum_{i = 1}^{\lfloor\frac{n}{dk}\rfloor} i \sum_{j = 1}^{\lfloor\frac{m}{dk}\rfloor} j [d \le a] \\ = &\sum_{d = 1}^{A} d \sum_{k = 1}^{\lfloor\frac{A}{d}\rfloor} k^2 \mu(k) \operatorname{S}(\lfloor\frac{n}{dk}\rfloor) \operatorname{S}(\lfloor\frac{m}{dk}\rfloor) [d \le a] \\ = &\sum_{T = 1}^{A} \operatorname{S}(\lfloor\frac{n}{T}\rfloor) \operatorname{S}(\lfloor\frac{m}{T}\rfloor) \sum_{d | T} \frac{T^2}{d}\mu(\frac{T}{d}) [d \le a] \end{aligned}

如果没有 aa 的限制，这道题就做完了，但是他有 。
将询问离线下来，按照 aa 的从小到大排序，然后不断放宽 aa 的限制，aa 每增大 11，就会多一个可以被统计到答案里的 dd，所以就可以枚举 dd 的倍数，将它的贡献统计上，因为整除分块要计算前缀和，可以用树状数组维护一下（常数小），修改一次是 O(log⁡n)O(\log n) 的，枚举倍数是 O(nln⁡n)O(n \ln n)，整除分块算上查询是 O(nlogn)O(\sqrt{n}log n)，共 TT 组询问，总时间复杂度是 O(Tnlog⁡n+nln⁡nlog⁡n)O(T\sqrt{n}\log n + n \ln n \log n)。

# Code

#define Aniciry Meteorshower_Y
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N = 1e5+01;
const int mod = 1e9+7;
namespace BIT{
    long long tr[N];
    inline auto add(int x, int k) -> void;
    inline auto query(int x) -> long long;
    inline auto query(int l, int r) -> long long;
}
int T, cnt, ans[N];
int p[N], mu[N], edge[N];
struct node{int n, m, a, id;}q[N];
inline auto add_h(int d) -> void;
inline auto prework(int n) -> void;
inline auto S(long long x) -> long long;
inline auto work(int n, int m) -> long long;
int main()
{
    scanf("%d", &T); prework(1e5);
    for(int i = 1; i <= T; i += 1)
    {
        scanf("%d%d%d", &q[i].n, &q[i].m, &q[i].a);
        q[i].id = i;
    }
    sort(q+1, q+T+1, [](node a, node b){
        return a.a <= b.a;
    });
    for(int x = 1, i = 1; x <= 1e5; x += 1)
    {
        add_h(x); while(i <= T and q[i].a == x) 
            ans[q[i].id] = work(q[i].n, q[i].m), i += 1;
    }
    for(int i = 1; i <= T; i += 1)
        printf("%d\n", ans[i]);
    return 0;
}
inline auto prework(int n) -> void
{
    mu[1] = 1;
    for(int i = 2; i <= n; i += 1)
    {
        if(!edge[i]) p[++cnt] = i, mu[i] = -1;
        for(int j = 1; j <= cnt and i*p[j] <= n; j += 1)
        {
            edge[i*p[j]] = 1;
            if(i%p[j] == 0){mu[i*p[j]] = 0; break;}
            mu[i*p[j]] = -mu[i];
        }
    }
}
inline auto work(int n, int m) -> long long
{
    int A = min(n, m);
    long long ans = 0; 
    for(int l = 1, r; l <= A; l = r+1)
    {
        r = min(n/(n/l), m/(m/l));
        ans += S(n/l) * S(m/l)%mod * BIT::query(l, r)%mod;
    }
    return (ans%mod+mod)%mod;
}
inline auto add_h(int d) -> void
{
    for(ll T = d; T <= 1e5; T += d)
        BIT::add(T, (ll)T*(T/d)%mod*mu[T/d]);
}
inline auto S(long long x) -> long long{return (x*(x+1)>>1)%mod;}
namespace BIT
{
    #define lowbit(x) (x&-x)
    inline auto add(int x, int k) -> void
    {
        for(; x <= 1e5; x += lowbit(x))
            tr[x] += k;
    }
    inline auto query(int x) -> long long
    {
        long long ans = 0;
        for(; x; x -= lowbit(x))
            ans += tr[x];
        return ans%mod;
    }
    inline auto query(int l, int r) -> long long
    {
        return (query(r)-query(l-1))%mod;
    }
}

# 平面图

# 题目描述

给一个 nn 个点 组成的联通的 平面图，接下来有 qq 次操作：

  1. 操作 - ，删去边 x <-> y ，并询问删完之后有几个联通块。
  2. 操作 ? ，询问 x 和 y 是否在一个联通块内。

输入第一行 n,qn, q，(n≤105,m≤2×105n \le 10^5, m \le 2 \times 10^5)。
接下来 nn 行，每行先读入 kk，表示点的度数，再读入 kk 个数，表示该点顺时针依次与哪些点相连。
接下来 qq 行读入 opt,x,yopt, x, y, 表示一组询问。
询问强制在线， x,yx, y 需要异或上一次的答案 lastanslastans, lastanslastans 初始为 00。

# 解题思路

考虑第一个问题，对于一个图的删边并不好维护，由于给的是平面图，我们可以将平面图的删边操作转化为对偶图的加边操作。考虑将对偶图的点建出，先不连边，每次删一条边，将这条边在对偶图中相邻的两个点（原图中的平面）连起来，若围成了一个环，这说明他们之间包住的那个平面图中的点周围的边都被切断，这时候联通块个数加一。并查集维护一下就好。

对于第二个问题，对同一个联通块染色。每次删边之后若将原联通块分割成了两个，我们就按照类似于启发式合并的思想，启发式分裂，每次将较小的联通块重新染色，这样就可以保证时间复杂度了。

# Code

#define Aniciry Meteorshower_Y
#include<unordered_map>
#include<algorithm>
#include<iostream>
#include<utility>
#include<cstdio>
#include<vector>
#include<map>
#define Pair pair<int,int>
using namespace std;
// 此处省略快读快写
const int N = 4e5+10;
int n, q, cnt, col, cnt_edge, lstans;
int belong[N], fa[N*3], vis[N], cur[N];
vector<int> to[N];
map<Pair, int> id;
map<Pair, int> edgebelong;
inline auto _find(int x) -> int;
inline auto extend(vector<int> &v, int &p) -> int;
int main()
{
    read(n, q);
    for(int i = 1, k; i <= n; i += 1) 
    {
        read(k); int x;
        for(int j = 1; j <= k; j += 1)
        {
            read(x);
            to[i].push_back(x);
            id[Pair(i,x)] = ++cnt_edge;
            fa[cnt_edge] = cnt_edge;
        }
    }
    for(int i = 1; i <= n; i += 1)
    {
        int k = to[i].size();
        for(int j = 1; j < k; j += 1)
            fa[_find(id[Pair(i,to[i][j-1])])] = fa[_find(id[Pair(to[i][j],i)])];
        fa[_find(id[Pair(i,to[i][k-1])])] = fa[_find(id[Pair(to[i][0],i)])];
    }
    for(int i = 1; i <= n; i += 1)
    {
        int k = to[i].size();
        for(int j = 0; j < k; j += 1)
            edgebelong[Pair(i,to[i][j])] = _find(id[Pair(i,to[i][j])]);
    }
    for(int i = 1; i <= n; i += 1)
        sort(to[i].begin(), to[i].end());
    for(int i = 1; i <= cnt_edge; i += 1) fa[i] = i; 
    char op; int x, y, idx, idy; cnt = 1;
    for(int i = 1; i <= q; i += 1)
    {
        read(op, x, y), x ^= lstans, y ^= lstans;
        if(op == '-')
        {
            idx = _find(edgebelong[Pair(x,y)]);
            idy = _find(edgebelong[Pair(y,x)]);
            to[x].erase(lower_bound(to[x].begin(), to[x].end(), y));
            to[y].erase(lower_bound(to[y].begin(), to[y].end(), x));
            if(idx == idy)
            {
                int p1 = 0, p2 = 0; cnt += 1;
                vector<int> v1; v1.push_back(x);
                vector<int> v2; v2.push_back(y);
                while(20051014)
                {
                    if(!extend(v1, p1)) {col += 1; 
                        for(auto y: v1) belong[y] = col; break;}
                    if(!extend(v2, p2)) {col += 1; 
                        for(auto y: v2) belong[y] = col; break;}
                }
                for(auto y: v1) vis[y] = cur[y] = 0;
                for(auto y: v2) vis[y] = cur[y] = 0;
            }
            else fa[idx] = idy; lstans = cnt;
        }
        else lstans = (belong[x] == belong[y]);
        printf("%d\n", lstans);
    }
    return 0;
}
inline auto _find(int x) -> int
{
    while(x != fa[x]) x = fa[x] = fa[fa[x]];
    return x;
}
inline auto extend(vector<int> &v, int &p) -> int
{
    for(; p < v.size(); p += 1)
    {
        int x = v[p];
        for(int i = cur[x]; i < to[x].size(); cur[x] = ++i)
        {
            int y = to[x][i];
            if(vis[y]) continue;
            vis[y] = true; v.push_back(y);
            return true;
        }
    }
    return false;
}