Day 10

nt赛

T1

dij随便改了几行，dis数组同时能代表目前的时间，即可判断当前路径真实通过时间

时间复杂度 \(O(m \log n)\)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define gt getchar
using namespace std;
inline ll read(){
	ll x=0,f=1;char ch=gt();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
	return x*f;}
const int N = 100005, M = 250005;
int n, k, m;
ll T = 0;
struct edge
{
	int t, dis, nxt;
}e[M];int ecnt, head[N];
inline void add(int u, int v, int dis)
{
	e[++ ecnt] = (edge){v, dis, head[u]};head[u] = ecnt;
	//e[++ ecnt] = (edge){u, dis, head[v]};head[v] = ecnt;
}
int dis[M];
int vis[M], f[M];
struct pr
{
	int t, dis;
	bool operator < (const pr & b)const
	{
		return dis > b.dis;
	}
};
/*
u, v;
u --> v dis;
ed[i].dis;
dis[u]
 - dis[u] % 2k = a;
 - a > k , e[i].dis += 2k - a;
 - a <= k , e[i].dis

*/
priority_queue<pr> Q;
inline void Dij(int S)
{
	Q.push((pr){S, 0});
	memset(dis, 0x3f, sizeof dis);
	dis[S] = 0;
	int tcnt = 0;;
	while(!Q.empty())
	{
		int u = Q.top().t, d = Q.top().dis;
		Q.pop();
		if(vis[u])continue;
		vis[u] = 1;
		for(int i = head[u]; i; i = e[i].nxt)
		{
			if(vis[e[i].t])continue;
			int a = dis[u] % (2 * k), dist = dis[u];
			if(a >= k) dist += (2 * k) - a + e[i].dis;
			else dist += e[i].dis;
			//cout << "Error: " << u << ' ' << e[i].t << ' ' << dis[u] << ' ' << e[i].dis <<' ' << dis[e[i].t] << '\n'; 
			//cout << a << ' ' << dist << '\n';  
			if(dis[e[i].t] > dist)
			{
				dis[e[i].t] = dist;
				//cout << dis[e[i].t] << '\n';
				if(!vis[e[i].t])Q.push((pr){e[i].t, dis[e[i].t]});
			}
		}
	}
}
void init()
{
	ecnt = 1;
	memset(head, 0, sizeof head);
}
int main()
{
	init();
	n = read(), k = read(), m = read();
	for(int i = 1; i <= m; ++ i)
	{
		int u = read(), v = read(), d = read();
		add(u, v, d);
		add(v, u, d);
	}
	Dij(1);
	//for(int i = 1; i <= n; ++ i)cout << dis[i] << ' ';
	//cout << '\n';
	cout << dis[n];
	return 0;
}

T2

首先不难想到直接最短路计算, 记 \(f(i,j)\) 表示跳到 \((i,j)\) 最少使用的体力。 那么转移就是枚举上一个位置然后加上曼哈顿距离求最小值。

考虑优化，我们注意到如果转移都在左上的话坐标正负的贡献是固定的, 所以可以使用数据结构维护。先按照一维扫描线，另一维可以使用线段树或者树状数组维护前缀/后缀最小值。

对于四个象限分别计算一次即可。

时间复杂度 \(O(n^2 \log n)\)

代码寄了，先挂着

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int M = 505;
int n, a[M][M], k;
int dist[M][M];
vector<pair<int,int> > pos[M * M];
void Ckmin(int &x, int y){if (y < x) x = y;}
struct T
{
    int val[M * 4];
    void _init(){
        for(int i  = 0; i < 4 * M; ++ i)val[i] = 1e9;
    }
    void modify(int p, int l, int r, int pos, int Val){
        if(l == r)
        {
            Ckmin(val[p], Val);
            return;
        }
        int mid = (l + r) >> 1;
        if(pos <= mid)
        {
            modify(p << 1, l, mid, pos, Val);
            val[p] = min(val[p], val[p << 1]);
        }
        else{
            modify(p << 1, mid + 1 , r, pos, Val);
            val[p] = min(val[p], val[(p << 1) + 1]);
        }
    }
    int query(int p, int l, int r, int lo, int hi)
    {
        if(lo <= l && r <= hi)
            return val[p];
        int mid = (l + r) >> 1;
        int ans = 1e9;
        if(lo <= mid)
            ans = min(ans, query(p << 1, l, mid, lo, hi));
        if(hi > mid)
            ans = min(ans, query((p << 1) + 1, mid + 1, r, lo, hi));
        return ans;
    }
    void Modify(int pos, int Val)
    {
        modify(1, 1, n, pos, Val);
    }
    int Query(int lo,int hi)
    {
        return query(1, 1, n, lo, hi);
    }
}T1, T2;
bool cmp1(pair<int, pair<int, int> > A, pair<int, pair<int, int> > B)
{
    if (A.se.fi != B.se.fi)
        return A.se.fi < B.se.fi;
    if (A.fi != B.fi)
        return A.fi < B.fi;
    return A.se.se < B.se.se;
}
bool cmp2(pair<int,pair<int,int> > A, pair<int,pair<int,int> > B)
{
    if (A.se.fi != B.se.fi)
        return A.se.fi > B.se.fi;
    if (A.fi != B.fi)
        return A.fi < B.fi;
    return A.se.se < B.se.se;
}
void Solve(vector <pair <int, pair<int, int> > > E)
{
    sort(E.begin(), E.end(), cmp1);
    T1._init();
    T2._init();
    for(int i = 0;i < E.size(); ++ i)
    {
        if(E[i].first == 0){
            int di = dist[E[i].se.fi][E[i].se.se];
            T1.Modify(E[i].se.se, di - E[i].se.fi - E[i].se.se);
            T2.Modify(E[i].se.se, di - E[i].se.fi + E[i].se.se);
        }
        else{
            int &di = dist[E[i].se.fi][E[i].se.se];
            di = min(di, T1.Query(1, E[i].se.se) + E[i].se.fi + E[i].se.se);
            di = min(di, T2.Query(E[i].se.se, n) + E[i].se.fi - E[i].se.se);
        }
    }
    sort(E.begin(), E.end(), cmp2);
    T1._init();
    T2._init();
    for(int i = 0; i < E.size(); ++ i)
    {
        if(E[i].first == 0)
        {
            int di = dist[E[i].se.fi][E[i].se.se];
            T1.Modify(E[i].se.se, di + E[i].se.fi - E[i].se.se);
            T2.Modify(E[i].se.se, di + E[i].se.fi + E[i].se.se);
        }
        else{
            int &di = dist[E[i].se.fi][E[i].se.se];
            di = min(di, T1.Query(1, E[i].se.se) - E[i].se.fi + E[i].se.se);
            di = min(di, T2.Query(E[i].se.se, n) - E[i].se.fi - E[i].se.se);
        }
    }
}

void work(){
    for(int i = 0; i < M * M; ++ i)
        pos[i].clear();
    n = read(); k = read();
    for(int i = 1; i <= n; ++ i)
    {
        for(int j = 1; j <= n; ++ j)
        {
            a[i][j] = read();
            pos[a[i][j]].pb(mp(i, j));
            dist[i][j] = 1e9;
        }
    }
    for(int i = 1; i <= k; ++ i)
        if (!pos[i].size())
        {
            cout << -1 << '\n';
            return;
        }
    for(auto v : pos[1])
        dist[v.fi][v.se] = 0;
    for(int i = 2;i <= k; ++ i)
    {
        vector<pair<int, pair<int, int> > > E;
        for (auto v : pos[i - 1]) E.pb(mp(0, v));
        for (auto v : pos[i]) E.pb(mp(1, v));
        Solve(E);
    }
    int res = 1e9;
    for(auto v : pos[k])
        res = min(res, dist[v.fi][v.se]);
    cout << -res << '\n';
}
int t;
int main()
{
    t = read();
    while (t --)
        work();
}

T3

首先每个数只有质因子有用，所以我们只需要保留每个数质因子的乘积即可。

那么通过简单的容斥或莫比乌斯反演我们可以将我们要求的 \(\sum_{i,j}[gcd(v_i,v_j)=1]\) 转化为 \(\sum_{g}\mu(g) \sum_{i,j} [g|v_i,g|v_j]\)

那么考虑假设我们要在路径中加入一个点或者删除一个点, 我们最多只需要枚举8个不同的\(g\) 并计算当前路径中有多少数是 \(g\) 的倍数，也就是说插入和删除的维护和更新可以在 \(O(1)\) 完成。

假设树的形态是一条链且我们可以快速的进行插入和删除，那么我们直接使用序列莫队的技巧即可。

对于一般的情况我们可以使用树上莫队的技巧，首先对树跑一边dfs, 在进入每个点(开始位置)和走出每个点(结束位置)的时刻同时记录, 这样就得到了一个长度为 \(2n\) 的序列，序列上的相邻元素在树上也相邻。注意到如果要统计树上的一条路径 \((u,v)\) 那么我们只需要将 \(u\) 的结束位置到 \(v\) 的开始位置对应序列的区间取出, 忽略出现两次的元素, 剩余的出现正好一次的元素再加上lca就是路径上的点集。 注意如果 \(u\) 是 \(v\) 的祖先需要特判。

于是就将树上莫队转化成了序列莫队问题求解。

最终时间复杂度 \(O(m\sqrt n)\)

T4

首先我们注意到任意两个秘密据点的路径中点是重要的，为了让这个中点不出现在边上一个常见的技巧就是在每条边上新建一个点。

然后我们先考虑在扩建了树之后每个 \(M\) 值的改变，原先树上的点 \(M\) 值会变成两倍。 考虑原图中的边 \((u,v)\) 中间新建的点 \(x\) 那么首先必须有 \(|M_u-M_v|\le 2\) 如果 \(|M_u-M_v|=2\) 那么 \(M_x=(M_u+M_v)/2\). 如果 \(M_u=M_v\) 这时候这条边中点 \(x\) 一定是某两个秘密据点的中点，也就是说这种边最多只有3个。这些 \(M_x=M_u \pm 1\), 可以直接暴力枚举。

接着我们考虑 \(u_1,u_2,u_3\) 的位置关系，它们三个点一定有一个中心 \(u\), 不妨记 \(D_i=d(u,u_i)\), 并且假设 \(D_1\le D_2\le D_3\).

我们按照 \(M\) 值从大到小给边定向, 如果一个点没有出度则称为汇点。 通过观察: 当 \(D_1<D_2\le D_3\) 的时候有且只有两个汇点。 当 \(D_1=D_2\le D_3\) 的时候有且只有一个汇点。计算出汇点的个数分类讨论。

一个汇点的情况: 此时汇点一定是三个点的中心, 设汇点为 \(r\), 且 \(D_1=D_2=M_r,D_3>M_r\) 我们只需要通过简单的背包的\(dp\) 计数即可。

两个汇点的情况: 设两个汇点为 \(r_1,r_2\). 我们会发现 \(u_1,u_2,u_3\) 的点到 \(r_1,r_2\) 的距离已经全部确定了，只要分别独立的满足这些距离, 将方案数相乘即可，两次 dfs 即可。

最终时间复杂度 \(O(n)\)

图论+数据结构选讲

CF 1654E

给定序列 \(a_1, a_2, · · · , a_n\)，最少改变其中的多少个元素使得其变成
一个等差数列。

\(n ≤ 10^5, 1 ≤ a_i ≤ 10^5\)

对于 \(d \le \sqrt{n}\) 暴力对 \(a_i − id\) 使用桶统计取最大值

对于 \(d \ge \sqrt{n}\) 注意到这种情况下等差数列一定只在一个很小的
范围内，我们直接暴力对相邻元素建图找最长路即可。

CF 1555F

你需要维护一个 \(n\) 个点的无向带权图，初始为空。称一个图是好
的当且仅当它的所有简单环的边权异或和为 \(1\).
支持 \(Q\) 次询问，每次给出一条新的边 \((u, v, w)\), 如果这条边加入
之后图仍然是好的就加入，否则不加入。你需要快速回答是否加
入。

\(n, Q ≤ 10^5\)

通过观察我们能够发现一个性质:

一个好的图中任意两个简单环的公共部分最多只有一个顶点。

换句话说这张图是一个边仙人掌。

接着我们考虑怎么维护这个仙人掌

首先我们先求出所有生成森林里的边，这些边是不会受到环边的影响的。

也就是说目前所有的树结构已经固定了。

考虑加入一条环边 (u, v), 首先需要 check 树上路径异或和环边权值的异或是否为 1, 这个只需要预处理到根的异或值即可。

然后我们需要查询是否路径上的边是否有被使用过。

两种不同的做法：

1. 直接 HLD 用线段树维护
2. 我们注意到路
   径也是可以减的所以直接维护到根的路径就行了, 同时由于每条
   边最多被使用一次可以暴力一条一条修改。

KD-Tree

\(KD-Tree\) 是线段树在高维空间的一个扩展，能够在低于线性的复杂度内支持高维的区间修改/区间查询。

类似的，\(KD-Tree\) 也是一个二叉树结构，以二维为例每个点维护一个矩形 \([lx_v, rx_v] × [ly_v, ry_v]\)，一般来说这个矩形会对应一个点集, 所以一般会选择包含整个点集的最小矩形。

如果矩形内包含了不止一个点那么这个点的两个儿子会按照 \(x\) 轴或者 \(y\) 轴将空间平均划分成两个矩形，如此迭代。

区间修改和查询的方式与线段树相同，在复杂度分析上一般使用 \(n^{\frac{k - 1}{k}}\) 进行估计

NOI 2019 弹跳

跳蚤国有 \(n\) 座城市，分别编号为 \(1 - n\)，\(1\) 号城市为首都。所有城市分布在一个\(w \times h\) 范围的网格上。每座城市都有一个整数坐标 \((x, y) (1 \leq x \leq w, 1 \leq y \leq h)\)，不同城市的坐标不相同。

在跳蚤国中共有 \(m\) 个弹跳装置，分别编号为 \(1 - m\)，其中 \(i\) 号弹跳装置位于 \(p_i\) 号城市，并具有参数 \(t_i, L_i, R_i, D_i, U_i\)。利用该弹跳装置，跳蚤可花费 \(t_i (t_i > 0)\) 个单位时间，从 \(p_i\) 号城市跳至坐标满足 \(L_i \leq x \leq R_i, D_i \leq y \leq U_i (1 \leq L_i \leq R_i \leq w, 1 \leq D_i \leq U_i \leq h)\) 的任意一座城市。需要注意的是，一座城市中可能存在多个弹跳装置，也可能没有弹跳装置。

由于城市间距离较远，跳蚤们必须依靠弹跳装置出行。具体来说，一次出行将经过
若干座城市，依次经过的城市的编号可用序列 \(a_0, a_1, \cdots , a_k\) 表示；在此次出行中，依次利用的弹跳装置的编号可用序列 \(b_1, b_2, \cdots , b_k\) 表示。其中每座城市可在序列 \(\{a_j\}\) 中出现任意次，每个弹跳装置也可在序列 \(\{b_j\}\) 中出现任意次，且满足，对于每个 \(j (1 \leq j \leq k)\)，编号为 \(b_j\) 的弹跳装置位于城市 \(a_{j-1}\)，且跳蚤能通过该弹跳装置跳至城市 \(a_j\)。我们称这是一次从城市 \(a_0\) 到城市 \(a_k\) 的出行，其进行了 \(k\) 次弹跳，共花费 \(\sum^k_{i=1} t_{b_{i}}\) 个单位时间。

现在跳蚤国王想知道，对于跳蚤国除首都（\(1\) 号城市）外的每座城市，从首都出发，到达该城市最少需要花费的单位时间。跳蚤国王保证，对每座城市，均存在从首都到它的出行方案。

\(1 \leq n \leq 70000 , 1 \leq m \leq 150000 , 1 \leq w, h \leq n , 1 \leq t_i \leq 10000\)。

首先直接暴力建图是不行的，那么不难想到直接使用 \(KDT\) 进行
优化建图. \(KDT\) 帮助我们将一个任意的矩形拆成了 \(O(\sqrt{n})\) 个节点。

如果直接建图空间复杂度是 \(O(m \sqrt{n})\) 无法接受. 但是我们可以
考虑不显式建图跑 dijkstra, 具体流程如下：

• 设置两类节点, 一类普通的点 \(1 − n\), 另一类表示一个矩形内的点. 维护堆 \(Q\).

• 在 dijkstra 的过程中我们用 \(KDT\) 维护当前还没有被弹出的
  点的集合。

• 每次弹出点的时候，如果这个点是一个普通点那么我们直接
  根据它的转移更新若干矩形点并插入堆。

• 如果弹出的点是矩形点那我们就直接通过 \(KDT\) 遍历这个矩
  形里尚未被弹出的普通点进行普通点的弹出和更新。

CF 938G

给定无向连通带权图, 定义一条路径的长度为路径上边权的异或,
如果在一条路径上经过了多次那么在异或的时候也会被计算多
次。
你需要支持一下三种操作:

• 加入一条连接 x 和 y 的长度为 d 的边，保证加入这条边之前 x 和 y 之间没有边。
• 删除链接 x 和 y 的边，保证删除之前这条边存在且删除边
  之后图仍然连通。
• 计算 x 到 y 的最短路径，路径可以不是简单路径。

\(n, m, q ≤ 200000\)

考虑对询问建一个线段树，每条边存在一个加入时间 \(l_i\) 和一个删除时间 \(r_i\), 那么它会对所有 \([li, ri]\) 区间上的边产生贡献，把这条边打在线段树的懒标记上。

那么每个三号询问本质上对应了一个线段树的叶子，它对应图的边就是叶子到根的懒标记的并。

考虑对线段树做一个 DFS, 进入一个节点的时候加上这个点的贡
献，走出一个节点的时候 rollback 贡献即可。

思考这些信息需要什么数据结构来维护。不难发现一条最短路径
是由任意路径加上若干环构成的，所以我们只需要维护一个生成
森林的信息加上环权值构成的线性基就行了。

首先我们需要一个
并查集维护连通性以及路径异或和，注意到由于需要支持回退所
以我们不能路径压缩。线性基直接使用长度为 30 的数组维护即
可，由于数据量小可以暴力回退。

\(O(n \log n)\)

CF 878C

\(n\) 个运动员, \(m\) 个项目, 第 \(i\) 个运动员第 \(j\) 个项目的能力是 \(s_{i_j}\)
现在对于 \(n\) 次询问 \(k = 1, 2, ..., n\), 让前 \(k\) 个运动员 \(1, ..., k\) 进行
淘汰赛，淘汰赛共 \(k − 1\) 轮每轮可以选择任意两个没有被淘汰的
运动员比赛任意一个项目。问最后可能夺冠的有多少人。

建图, 将每个运动员看成点，如果一个运动员可以战胜另外一个
运动员就连一条有向边。注意到一个运动员可能夺冠当且仅当存
在一个以它为根的有根树。

进一步观察, 如果将这个图强连通缩点那么可能夺冠的运动员只
能是第一个强连通块内的，

同时如果我们用每个块每个项目内最
弱到最强的能力值将每个连通块抽象成一个高维长方体，那么这
些长方体一定是严格偏序的，

也就是说缩完点的 DAG 一定是满的

接下来考虑插入，由于我们已经有了强连通图的顺序结构，所以
可以直接二分新的点会把哪些块粘在一起。