算法模板

总览

  • [[#基础算法]]

    • [[#前缀和与差分]]
    • [[#二分]]

  • [[#数据结构]]

    • [[#并查集]]
      • [[#普通并查集]]
      • [[#带权并查集]]
      • [[#拓展域并查集]]
    • [[#树状数组]]

  • [[#图论]]

    • [[#最小生成树]]
      • [[#Kruskal算法]]
    • [[#全源最短路]]
      • [[#Djkstra堆优化(正权稀疏图)]]
      • [[#Djkstra(正权稠密图)]]
      • [[#Bellman_Ford]]
      • [[#Spfa]]
      • [[#Floyd]]
    • [[#拓扑排序]]
    • [[#LCA最近公共祖先]]

  • [[#数论]]

    • [[#快速幂]]
    • [[#组合数]]
    • [[#欧几里得算法]]
    • [[#质数]]
      • [[#试除法]]
      • [[#线性筛]]

  • [[#杂项]]

    • [[#莫队]]
      • [[#带修莫队]]

基础算法

前缀和与差分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int a[],p[],d[]
//前缀和
p[i] = p[i-1] + a[i] //构造
sum(l,r) = p[r] - p[l - 1] //查询

p[x][y] = p[x-1][y] + p[x][y-1] - p[x-1][y-1] + a[x][y] //构造
sum(point(1),point(2)) = p[x2][y2] + p[x1-1][y1-1] - p[x1-1][y2] - p[x2][y1-1] //查询

//差分
diff(l,r,c)
{
	d[l] += c
	d[r + 1] -= c
}

diff(point(1),point(2),c)
{
	d[x1][y1]+=c
	d[x2+1][y1]-=c
	d[x1][y2+1]-=c
	d[x2+1][y2+1]+=c
}

二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

lower_bound(begin,end,num,rule) 第一个大于等于(小于等于)
upper_bound(begin,end,num,rule) 第一个大于(小于)

数据结构

并查集

普通并查集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct DSU
{
    std::vector<int> p, siz;
    DSU() {}
    DSU(int n) { init(n); }
    void init(int n)
    {
        p.resize(n);
        std::iota(p.begin(), p.end(), 0);
        siz.assign(n, 1);
    }
    int find(int x)
    {
        while (x != p[x])
            x = p[x] = p[p[x]];
        return x;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    bool merge(int x, int y)
    {
        int px = find(x);
        int py = find(y);
        if (px == py) return false;
        siz[px] += siz[py];
        p[py] = px;
        return true;
    }
    int size(int x) { return siz[find(x)]; }
};
带权并查集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
struct DSUV
{
    std::vector<int> p, siz, d;
    DSUV() {}
    DSUV(int n) { init(n); }
    void init(int n)
    {
        p.resize(n);
        std::iota(p.begin(), p.end(), 0);
        siz.assign(n, 1);
        d.assign(n, 0);
    }
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]]; // 按情况修改
            p[x] = u;
        }
        return p[x];
    }
    bool same(int x, int y) { return find(x) == find(y); }
    bool merge(int x, int y, int s)
    {
        int px = find(x);
        int py = find(y);
        if (px == py) return false;
        siz[px] += siz[py];
        p[py] = px;
        d[py] = (d[x] - d[y] + s); // s为偏移量，按情况修改
        return true;
    }
    int size(int x) { return siz[find(x)]; }
};
拓展域并查集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
//利用p[x + k *n] 来对应不同的情况
//例题
struct DSU
{
	std::vector<int> p, siz;
	DSU() {}
	DSU(int n) { init(n); }
	void init(int n)
	{
		p.resize(n);
		std::iota(p.begin(), p.end(), 0);
		siz.assign(n, 1);
	}
	int find(int x)
	{
		while (x != p[x])
		{
			x = p[x] = p[p[x]];
		}
		return x;
	}
	bool same(int x, int y) { return find(x) == find(y); }
	bool merge(int x, int y)
	{
		int px = find(x);
		int py = find(y);
		if (px == py)
		{
			return false;
		}
		siz[px] += siz[py];
		p[py] = px;
		return true;
	}
	int size(int x) { return siz[find(x)]; }
};
int main()
{
	int n, k, res = 0;
	cin >> n >> k;
	DSU dsu(3 * (n + 1));
	for (int i = 0, d, x, y; i < k; ++i)
	{
		cin >> d >> x >> y;
		if (x > n || y > n)
		{
			res++;
			continue;
		}
		if (d & 1)
		{
			if (dsu.same(x + n, y) || dsu.same(x + n + n, y))
			{
				res++;
			}
			else
			{
				dsu.merge(x, y);
				dsu.merge(x + n, y + n);
				dsu.merge(x + n + n, y + n + n);
			}
		}
		else
		{
			if (dsu.same(x + n + n, y) || dsu.same(x, y))
			{
				res++;
			}
			else
			{
				dsu.merge(x + n, y);
				dsu.merge(x + n + n, y + n);
				dsu.merge(x, y + n + n);
			}
		}
	}
	cout << res << endl;
	return 0;
}

树状数组

基础封装 $Onlogn$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
struct BIT
{
    int n;
    vector<int> w;
    BIT(int n)
    {
        this->n = n; // 这里必须写 n ，否则会RE
        w.resize(n + 1);
    }
    void add(int x, int k)
    {
        for (; x <= n; x += x & -x)
        {
            w[x] += k;
        }
    }

    void add(int x, int y, int k)
    { // 区间修改
        add(x, k), add(y, -k);
    }
    int ask(int x)
    {
        int ans = 0;
        for (; x; x -= x & -x)
        {
            ans += w[x];
        }
        return ans;
    }
    int ask(int x, int y)
    { // 区间查询
        return ask(y) - ask(x - 1);
    }
    int kth(int k)
    { // ex: 查找第k大的值
        int ans = 0;
        for (int i = __lg(n); i >= 0; i--)
        {
            int val = ans + (1 << i);
            if (val < n && w[val] < k)
            {
                k -= w[val];
                ans = val;
            }
        }
        return ans + 1;
    }
};

图论

最小生成树

Kruskal算法

$O(mlogm)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
struct DSU
{
	std::vector<int> p, siz;
	DSU() {}
	DSU(int n) { init(n); }
	void init(int n)
	{
		p.resize(n);
		std::iota(p.begin(), p.end(), 0);
		siz.assign(n, 1);
	}
	int find(int x)
	{
		while (x != p[x])
		{
			x = p[x] = p[p[x]];
		}
		return x;
	}
	bool same(int x, int y) { return find(x) == find(y); }
	bool merge(int x, int y)
	{
		int px = find(x);
		int py = find(y);
		if (px == py)
		{
			return false;
		}
		siz[px] += siz[py];
		p[py] = px;
		return true;
	}
	int size(int x) { return siz[find(x)]; }
};
struct MST
{
	using TII = tuple<int,int,int>;
	int n;
	priority_queue<TII,vector<TII>,greater<TII>> eg;
	MST(int n) : n(n){}
	void add(int x,int y,int w)
	{
		eg.emplace(w,x,y);
	}
	int kruskal()
	{
		DSU dsu(n + 1);
		int ans = 0,cnt = 0,w,x,y;
		while(eg.size())
		{
			tie(w,x,y) = eg.top();
			eg.pop();
			if(dsu.same(x,y)) continue;
			dsu.merge(x,y);
			ans += w;
			cnt ++ ;
		}
		if(cnt < n - 1) return INF;
		return ans;
	}
};

全源最短路

Djkstra堆优化(正权稀疏图)

$O(MlogN)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vector<int> dis(n + 1,0x3f3f3f3f);
auto dijkstra = [&](int s = 1) ->void
{
	int y,w;
	using PII = pair<int,int>;
	priority_queue<PII,vector<PII>,greater<PII> > q;
	q.emplace(0,s);
	dis[s] = 0;
	vector<int> st(n + 1);
	while(q.size())
	{
		int x = q.top().second;
		q.pop();
		if(st[x]) continue;
		st[x] = 1;
		for(auto el : h[x])
		{
			tie(y,w) = el;
			if(dis[y] > dis[x] + w)
			{
				dis[y] = dis[x] + w;
				q.emplace(dis[y],y);
			}
		}
	}
};
Djkstra(正权稠密图)

$O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const int N = 3010;
int n,m,g[N][N];
int d[N],st[N];
void dji(int s = 1){
	memset(d,0x3f,sizeof d); d[s] = 0;
	for(int i=1;i<=n;++i)
	{
		int x = 0;
		for(int j=1;j<=n;++j)
		{
			if(st[j]) continue;
			if(x == 0|| d[j] < d[x]) x = j;
		}
		st[x] = 1;
		for(int j=1;j<=n;++j) d[j] = min(d[j],d[x] + g[x][j]);
	}
}
int main()
{
	cin >> n >> m;
	memset(g,0x3f,sizeof g);
	for(int i=1;i<=m;++i)
	{
		int x,y,w;cin >> x >> y >> w;
		g[x][y] = min(g[x][y],w);//考虑重边
		g[y][x] = min(g[y][x],w);//无向图
	}
	dji();
	if(d[n] == INF) cout << -1 << endl;
	else cout << d[n] << endl;
	return 0;
}
Bellman_Ford

使用结构体存边（该算法无需存图），以 $O(NM)$的复杂度计算,当所求点的路径上存在负环时，所求点的答案无法得到，但是会比 INF 小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//求解从 1 到 n 号节点的、最多经过 k 条边的最短距离。
const int N = 510,M = 10010;
int dis[N],backup[N];
vector<tuple<int,int,int> > eg;
void bellman_ford(int s = 1)
{
    int u,v,w;
    memset(dis,0x3f,sizeof dis);
    dis[s] = 0;
    for(int i=0;i<k;++i)
    {
        memcpy(backup,dis,sizeof dis);
        for(int j=0;j<m; ++ j)
        {
            tie(u,v,w) = eg[j];
            dis[v] = min(dis[v],backup[u] + w);
        }
    }
}
int main()
{
    cin >> n >> m >> k;
    for(int i=0,a,b,w;i<m;++i)
    {
        cin >> a >> b >> w;
        eg.emplace_back(a,b,w);
    }
    bellman_ford();
    if(dis[n] > INF / 2) puts("impossible");
    else cout << dis[n] << endl;
    return 0;
}
Spfa

以 $O(KM)$的复杂度计算，其中 $K$ 虽然为常数，但是可以通过特殊的构造退化成接近 $N$ ，需要注意被卡,注意判断负环，dis数组里面值必须一致。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
vector<int> dis(n + 1, 0x3f3f3f3f);
auto spfa = [&](int s = 1) -> bool {
    int y, w;
    using PII = pair<int, int>;
    vector<int> st(n + 1), cnt(n + 1);
    queue<int> q;
    q.emplace(s);//
    dis[s] = 0;//
    st[s] = 1;//
    // for(int i=1;i<=n;++i) q.emplace(i),st[i] = 1;//判断负环，一般要全部点加入
    while (q.size()) {
        auto x = q.front();
        q.pop();
        st[x] = 0;
        for (auto el : h[x]) {
            // tie(y,w) = el; // tie开销更大可能会超时
            y = el.first, w = el.second;
            if (dis[y] > dis[x] + w) {
                dis[y] = dis[x] + w;
                cnt[y] = cnt[x] + 1;
                if (cnt[y] >= n)
                    return true;
                if (!st[y])
                    q.emplace(y), st[y] = 1;
            }
        }
    }
    return false;
};

Floyd
1
2
3
4
5
6
7
8
9
10
11
12
13
//初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;
// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

拓扑排序

时间复杂度 $O(V+E)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> h[N];
vector<int> d(n + 1, 0);
vector<int> ans;
auto topsort = [&]() -> void
{
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (!d[i])
            q.push(i);
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        ans.push_back(t);
        for (auto el : h[t])
        {
            if( -- d[el] == 0)
            q.push(el);
        }
    }
};

LCA最近公共祖先

预处理时间复杂度 $O(NlogN)$ ；单次查询 $O(logN)$

基础封装，无权图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
struct LCA {
    int n;
    vector<vector<int> > h,f;//存图，从i开始向上走2^j步到的点
    vector<int> dep,lg;
    LCA(int n) {
        this->n = n;
        h.resize(n + 1);
        f.resize(n + 1, vector<int>(30));
        dep.resize(n + 1);
        lg.resize(n + 1);
        for(int i=1;i<=n;++i)
            lg[i] = lg[i-1] + (1 << lg[i-1] == i);
    }
    void add(int x, int y) { // 建立双向边
        h[x].push_back(y);
        h[y].push_back(x);
    }
    void dfs(int x, int fa) {
        f[x][0] = fa; // 储存 x 的父节点
        dep[x] = dep[fa] + 1;
        for (int i = 1; i <= lg[dep[x]]; i++) {
            f[x][i] = f[f[x][i - 1]][i - 1];
        }
        for (auto y : h[x]) {
            if (y == fa) continue;
            dfs(y, x);
        }
    }
    int lca(int x, int y) {
        if (dep[x] < dep[y]) swap(x, y);//保证x更深
        while (dep[x] > dep[y]) {
            x = f[x][lg[dep[x] - dep[y]] - 1];
        }
        if (x == y) return x;
        for (int k = lg[dep[x]] - 1; k >= 0; k--) {
            if (f[x][k] == f[y][k]) continue;
            x = f[x][k];
            y = f[y][k];
        }
        return f[x][0];
    }
    int clac(int x, int y) { // 倍增查询两点间距离
        return dep[x] + dep[y] - 2 * dep[lca(x, y)];
    }
    void work(int root = 1) { // 在此初始化
        dfs(root, 0);
    }
};

数论

快速幂

求 m^k mod p，时间复杂度 O(logk)

1
2
3
4
5
6
7
8
9
10
11
int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

组合数

1
2
3
4
5
6
7
int C(int a,int b)
{
    LL res = 1;
    for(int i=a,j=1;j<=b;i--,j++)
        res = res * i/j;
    return res;
}

欧几里得算法

gcd
1
2
3
4
int gcd(int a,int b)
{
	return b ? gcd(b,a % b) : a;
}
lcm
1
2
3
4
int lcm(int a,int b)
{
	return a / gcd(a,b) *b;
}
拓展欧几里得算法
1
2
3
4
5
6
7
8
9
10
11
int exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x = 1,y = 0;
        return a;
    }
    int d = exgcd(b,a%b,y,x);
    y -= a / b * x;//公式
    return d;
}

质数

试除法

时间复杂度$O(\sqrt n)$ 

1
2
3
4
5
6
7
bool Is_prime(int n)
{
    if(n<2) return false;
    for(int i=2;i<=n/i;++i)
        if(n%i==0) return false;
    return true;
}
线性筛

时间复杂度$O(n)$ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int primes[N],cnt;//存所有质数
bool st[N];//记录i有没有被筛过

void get_primes(int n)//筛选2~n的素数
{
	for(int i=2;i<=n;++i)
	{
		if(!st[i]) primes[cnt++] = i;//如果没有被筛过,证明是素数
		for(int j = 0;primes[j] * i <=n;j++)
		{
		/*p[j]一定小于等于i的质因子*/
			st[primes[j] * i] = true;//用最小质因子筛掉合数
			if(i%primes[j] == 0) break;
		}
	}
}

存最小质因子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int primes[N],cnt;//存所有质数
bool st[N];//记录i有没有被筛过
//****
int minp[N];//每个数的最小质因子
//****
void get_primes(int n)//筛选2~n的素数
{
	for(int i=2;i<=n;++i)
	{
		if(!st[i]) minp[i]=i,primes[cnt++] = i;//如果没有被筛过,证明是素数
		for(int j = 0;primes[j] * i <=n;j++)
		{
		/*p[j]一定小于等于i的质因子*/
			st[primes[j] * i] = true;//用最小质因子筛掉合数
			minp[primes[j] * i] = primes[j];
			if(i%primes[j] == 0) break;
		}
	}
}

存储约数个数及其i的最小素因子个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const int N = 2e7+3;
int primes[N],cnt;//存所有质数
bool st[N];//记录i有没有被筛过
//****
int minp[N];//每个数的最小质因子
int d[N];//表示i的约数的个数
int num[N];//表示i的最小素因子的个数
//****
void get_primes(int n)//筛选2~n的素数
{
    d[1] = 1;
	for(int i=2;i<=n;++i)
	{
		if(!st[i]) minp[i]=i,primes[cnt++] = i,num[i] = 1,d[i] = 2;//如果没有被筛过,证明是素数
		for(int j = 0;primes[j] * i <=n;j++)
		{
		/*p[j]一定小于等于i的质因子*/
			st[primes[j] * i] = true;//用最小质因子筛掉合数
			minp[primes[j] * i] = primes[j];
			if(i%primes[j] == 0)
            {
                num[primes[j] * i] = num[i] + 1;
                d[primes[j] * i] = d[i] / num[primes[j] * i] * (num[primes[j]*i] + 1);
                break;
            }
            num[primes[j] * i] = 1;
            d[primes[j] * i] = d[i] * 2;
		}
	}
}

杂项

莫队
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int main()
{
    int n, m;
    cin >> n >> m;
    i64 kn = n / min<int>(n, sqrt(m));
    vector<int> v(n + 1), K(n + 1);
    vector<i64> ans(m + 1);
    vector<array<int, 3>> query(m + 1);
    for (int i = 1; i <= n; ++i)
        cin >> v[i], K[i] = (i - 1) / kn + 1;
    for (int i = 1; i <= m; ++i)
    {
        int l, r;
        cin >> l >> r;
        query[i] = {l, r, i};
    }
    sort(query.begin() + 1, query.end(), [&](auto x, auto y)
        {
            if(K[x[0]] != K[y[0]]) return x[0] < y[0];
            if(K[x[0]] & 1) return x[1] < y[1];
            return x[1] > y[1];
        });
    int l = 1, r = 0, val = 0;
    for (int i = 1; i <= m; ++i)
    {
        auto &e = query[i];
        int ql = e[0], qr = e[1], id = e[2];
        auto add = [&](int x) -> void {
  
		};
        auto sub = [&](int x) -> void {
  
        };
        while (l > ql) add(v[--l]);
        while (r < qr) add(v[++r]);
        while (l < ql) sub(v[l++]);
        while (r > qr) sub(v[r--]);
        ans[id] = val;
    }
    for (int i = 1; i <= m; ++i) cout << ans[i] << endl;
    return 0;
}
带修莫队

单点修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int main()
{
    int n,m;
    cin >> n >> m;
    int kn = pow(n,0.6666);
    vector<int> v(n + 1),K(n + 1);
    vector<array<int,4>> query = {{}};//l,r,time,id
    vector<array<int,2>> modify = {{}};//下标，值
    for(int i=1;i<=n;++i) cin >> v[i],K[i] = (i-1)/kn + 1;
    for(int i=1;i<=m;++i)
    {
        string s;int x,y;cin >> s >> x >> y;
        if(s == "Q") query.emplace_back(x,y,(int)modify.size() - 1,(int)query.size());
        else modify.emplace_back(x,y);
    }
    sort(query.begin() + 1,query.end(),[&](auto x,auto y){
        if(K[x[0]] != K[y[0]]) return x[0] < y[0];
        if(K[x[1]] != K[y[1]]) return x[1] < y[1];
        return x[3] < y[3];
    });
    int l = 1,r = 0,val = 0,t = 0;//t为累计修改次数
    for(int i=1;i<query.size(); ++ i)
    {
        auto &e = query[i];
        int ql = e[0],qr = e[1],qt = e[2],id = e[3];
        auto add = [&](int x) -> void {

        };
        auto sub = [&](int x) -> void {

        };
        auto time = [&](int x,int l,int r) -> void {
            int &w = modify[x][1], id = modify[x][0];//记得引用
            if(l <= id && id <= r)
            {
                sub(v[id]);
                add(w);
            }
            swap(v[id],w);
        };
        while (l > ql) add(w[--l]);
        while (r < qr) add(w[++r]);
        while (l < ql) sub(w[l++]);
        while (r > qr) sub(w[r--]);
        while (t < qt) time(++t, ql, qr);
        while (t > qt) time(t--, ql, qr);
        ans[id] = val;
    }
    for(int i=1;i<=ans.size();++i) cout << ans[i] << endl;
    return 0;
}

算法模板
#算法
算法模板
http://pikachuxpf.github.io/posts/2cc2fa98/
作者
Pikachu_fpx
发布于
2024年3月15日
许可协议