Hexo
0%

Posted on In , ,
Symbols count in article: 1.2k Reading time ≈ 1 mins.

归并排序

  • 将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。
  • 将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表。
  • O(nlogn)
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
#include<iostream>
#include<cstdlib>
#define ElemType_I int

using namespace std;

void Merge(ElemType_I A[], ElemType_I left, ElemType_I mid, ElemType_I right)             //合并
{
	ElemType_I *B = new ElemType_I[right - left + 1];                                     //申请辅助数组
	ElemType_I i = left;
	ElemType_I j = mid + 1;
	ElemType_I k = 0;

	while (i <= mid && j <= right)
		if (A[i] <= A[j])
			B[k++] = A[i++];
		else
			B[k++] = A[j++];

	while (i <= mid)
		B[k++] = A[i++];

	while (j <= right)
		B[k++] = A[j++];

	for (i = left, k = 0; i <= right; i++)
		A[i] = B[k++];

	delete[] B;
}

void MergeSort(ElemType_I A[], ElemType_I left, ElemType_I right)                             //递归形式的归并排序
{
	if (left < right)
	{
		ElemType_I mid;
		mid = (left + right) / 2;
		MergeSort(A, left, mid);
		MergeSort(A, mid + 1, right);
		Merge(A, left, mid, right);
	}
}

int main()
{
	ElemType_I n;
	cin >> n;
	ElemType_I *A = new ElemType_I[n];
	for (int i = 0; i < n; i++)
		cin >> A[i];

	MergeSort(A, 0, n - 1);                                          //调用归并排序              

	for (int i = 0; i < n; i++)
		cout << A[i] << " ";

	cout << endl;
	//system("pause");                                                        //输出暂停，头文件<cstdlib>

	return 0;
}

Read more »

Posted on In ,
Symbols count in article: 1.2k Reading time ≈ 1 mins.

st表

询问特定区间的最大/最小值

先进行初始化，每次询问的复杂度为O(1)

询问区间的极差(最大值-最小值)

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
/*
 * @Description: 
 * @Author: CrayonXiaoxin
 * @Date: 2024-01-26 10:46:31
 * @LastEditTime: 2024-05-22 20:53:39
 * @LastEditors:  
 */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
const int maxn = 1e6 + 10;
int n, m;
ll max_xy[maxn][22], min_xy[maxn][22];

ll st(int l,int r)
{
    int s = log2(r - l + 1), x, y;
    x = max(max_xy[l][s], max_xy[r - (1 << s) + 1][s]);//区间最大
    y = min(min_xy[l][s], min_xy[r - (1 << s) + 1][s]);//区间最小
    return x - y;
}
void solve(){
    cin >> n >> m;
    for (int i = 1; i <= n;++i)
    {
        cin >> max_xy[i][0];
        min_xy[i][0] = max_xy[i][0];
    }

    for (int i = 1; i <= 21;++i)//这个循环的上界决定于数据的大小，即2的21次方大于数据
    {
        for (int k = 1; k + (1 << i) <= n + 1;++k)
        {
            max_xy[k][i] = max(max_xy[k][i - 1], max_xy[k + (1 << (i - 1))][i - 1]);
            min_xy[k][i] = min(min_xy[k][i - 1], min_xy[k + (1 << (i - 1))][i - 1]);
        }
    }

    while(m--)
    {
        int l, r;
        cin >> l >> r;
        cout << st(l, r) << endl;
    }
}

int main(){
//std::ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
int t=1;
//cin>>t;
while(t--){
    solve();
}
return 0;
}
Read more »

Posted on In ,
Symbols count in article: 1.6k Reading time ≈ 1 mins.

主席树

静态区间第k小

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
80
81
82
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1e5; // 数据范围
int tot, n, m;
int sum[(maxn << 5) + 10], rt[maxn + 10], ls[(maxn << 5) + 10],
    rs[(maxn << 5) + 10];
int a[maxn + 10], ind[maxn + 10], len;

int getid(const int &val)
{ // 离散化
    return lower_bound(ind + 1, ind + len + 1, val) - ind;
}

int build(int l, int r)
{ // 建树
    int root = ++tot;
    if (l == r)
        return root;
    int mid = l + r >> 1;
    ls[root] = build(l, mid);
    rs[root] = build(mid + 1, r);
    return root; // 返回该子树的根节点
}

int update(int k, int l, int r, int root)
{ // 插入操作
    int dir = ++tot;
    ls[dir] = ls[root], rs[dir] = rs[root], sum[dir] = sum[root] + 1;
    if (l == r)
        return dir;
    int mid = l + r >> 1;
    if (k <= mid)
        ls[dir] = update(k, l, mid, ls[dir]);
    else
        rs[dir] = update(k, mid + 1, r, rs[dir]);
    return dir;
}

int query(int u, int v, int l, int r, int k)
{ // 查询操作
    int mid = l + r >> 1,
        x = sum[ls[v]] - sum[ls[u]]; // 通过区间减法得到左儿子中所存储的数值个数
    if (l == r)
        return l;
    if (k <= x) // 若 k 小于等于 x ，则说明第 k 小的数字存储在在左儿子中
        return query(ls[u], ls[v], l, mid, k);
    else // 否则说明在右儿子中
        return query(rs[u], rs[v], mid + 1, r, k - x);
}

void init()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", a + i);
    memcpy(ind, a, sizeof ind);
    sort(ind + 1, ind + n + 1);
    len = unique(ind + 1, ind + n + 1) - ind - 1;
    rt[0] = build(1, len);
    for (int i = 1; i <= n; ++i)
        rt[i] = update(getid(a[i]), 1, len, rt[i - 1]);
}

int l, r, k;

void work()
{
    while (m--)
    {
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", ind[query(rt[l - 1], rt[r], 1, len, k)]); // 回答询问
    }
}

int main()
{
    init();
    work();
    return 0;
}
Read more »

Posted on In ,
Symbols count in article: 6.7k Reading time ≈ 6 mins.

线段树

模板1

将某区间每个数加上k

求出某区间每一个数的和

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int maxn = 1e5 + 10;
ll n, m, a[maxn], t[maxn << 2], tag[maxn << 2]; // t为节点数组，tag为懒标记数组

ll ls(ll x)
{
    return x << 1;
}
ll rs(ll x)
{
    return x << 1 | 1;
}

void push_up(ll p) // 更新当前节点
{
    t[p] = t[ls(p)] + t[rs(p)];
    return;
}

void f(ll p, ll l, ll r, ll k) // 修改
{
    tag[p] = tag[p] + k;
    t[p] = t[p] + k * (r - l + 1);
}

void push_down(ll p, ll l, ll r) // 向下一层更新
{
    ll mid = (l + r) >> 1;
    f(ls(p), l, mid, tag[p]);
    f(rs(p), mid + 1, r, tag[p]);
    tag[p] = 0; // 懒标记清零
}

void build_tree(ll l, ll r, ll p) // 建树
{
    tag[p] = 0;
    if (l == r)
    {
        t[p] = a[l];
        return;
    }
    ll mid = (l + r) >> 1; // 中间分割点
    build_tree(l, mid, p << 1);
    build_tree(mid + 1, r, (p << 1) | 1);
    push_up(p);
}

/*
nl,nr为要修改的区间
l,r为固定的区间
p为节点编号
k为修改的值
*/
void update(ll nl, ll nr, ll l, ll r, ll p, ll k)
{
    if (nl <= l && r <= nr)
    {
        t[p] += k * (r - l + 1);
        tag[p] += k;
        return;
    }
    push_down(p, l, r);
    ll mid = (l + r) >> 1;
    if (nl <= mid)
        update(nl, nr, l, mid, ls(p), k);
    if (nr > mid)
        update(nl, nr, mid + 1, r, rs(p), k);
    push_up(p);
}

/*
ql,qr为询问区间
l,r为固定区间
p为节点编号
*/
ll query(ll ql, ll qr, ll l, ll r, ll p)
{
    ll res = 0;
    if (ql <= l && r <= qr)
        return t[p];
    ll mid = (l + r) >> 1;
    push_down(p, l, r); // 更新下面一层的节点
    if (ql <= mid)
        res += query(ql, qr, l, mid, ls(p));
    if (qr > mid)
        res += query(ql, qr, mid + 1, r, rs(p));
    return res;
}

void solve()
{
    cin >> n >> m;
    for (ll i = 1; i <= n; ++i)
        cin >> a[i];
    build_tree(1, n, 1);
    while (m--)
    {
        ll ope;
        cin >> ope;
        if (ope == 1) // 修改[l,r]的每个值加上k
        {
            ll l, r, k;
            cin >> l >> r >> k;
            update(l, r, 1, n, 1, k);
        }
        else
        {
            ll l, r;
            cin >> l >> r;
            cout << query(l, r, 1, n, 1) << endl;
        }
    }
}

int main()
{
    // std::ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    int t = 1;
    // cin>>t;
    while (t--)
    {
        solve();
    }
    return 0;
}

模板2

将某区间每一个数乘上x

将某区间每一个数加上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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int maxn = 1e5 + 10;
const int mod = 1e9;
ll n, q, m, a[maxn];
struct nopde
{
    ll v, mul, add; // mul,add都是标记
} t[maxn << 2];

ll ls(ll x)
{
    return x << 1;
}

ll rs(ll x)
{
    return x << 1 | 1;
}

void push_up(ll p)
{
    t[p].v = (t[ls(p)].v + t[rs(p)].v) % mod;
    return;
}

void build_tree(ll l, ll r, ll p)
{
    t[p].mul = 1;
    t[p].add = 0;
    if (l == r)
    {
        t[p].v = a[l] % mod;
        return;
    }
    ll mid = (l + r) >> 1;
    build_tree(l, mid, ls(p));
    build_tree(mid + 1, r, rs(p));
    push_up(p);
    return;
}
/*
维护lazytag
*/
void push_down(ll l, ll r, ll p)
{
    ll mid = (l + r) >> 1;
    // 儿子的值=此刻儿子的值*爸爸的乘法lazytag+儿子的区间长度*爸爸的加法lazytag
    t[ls(p)].v = (t[ls(p)].v * t[p].mul + t[p].add * (mid - l + 1)) % mod;
    t[rs(p)].v = (t[rs(p)].v * t[p].mul + t[p].add * (r - mid)) % mod;
    // 维护lazytag
    t[ls(p)].mul = (t[ls(p)].mul * t[p].mul) % mod;
    t[rs(p)].mul = (t[rs(p)].mul * t[p].mul) % mod;
    t[ls(p)].add = (t[ls(p)].add * t[p].mul + t[p].add) % mod;
    t[rs(p)].add = (t[rs(p)].add * t[p].mul + t[p].add) % mod;
    // 初始化父节点
    t[p].mul = 1;
    t[p].add = 0;
    return;
}

//乘上k
void mul(ll ml, ll mr, ll l, ll r, ll p, ll k)
{
    if (mr < l || r < ml)
        return;
    if (ml <= l && r <= mr)
    {
        t[p].v = (t[p].v * k) % mod;
        t[p].mul = (t[p].mul * k) % mod;
        t[p].add = (t[p].add * k) % mod;
        return;
    }
    // 先传递lazytag
    push_down(l, r, p);
    ll mid = (l + r) >> 1;
    mul(ml, mr, l, mid, ls(p), k);
    mul(ml, mr, mid + 1, r, rs(p), k);
    push_up(p);
    return;
}

//加上k
void add(ll al, ll ar, ll l, ll r, ll p, ll k)
{
    if (ar < l || r < al)
        return;
    if (al <= l && r <= ar)
    {
        t[p].v = (t[p].v + k * (r - l + 1)) % mod;
        t[p].add = (t[p].add + k) % mod;
        return;
    }
    // 先传递lazytag
    push_down(l, r, p);
    ll mid = (l + r) >> 1;
    add(al, ar, l, mid, ls(p), k);
    add(al, ar, mid + 1, r, rs(p), k);
    push_up(p);
    return;
}

ll query(ll ql, ll qr, ll l, ll r, ll p)
{
    if (qr < l || r < ql)
        return 0;
    if (ql <= l && r <= qr)
        return t[p].v;
    push_down(l, r, p);
    ll mid = (l + r) >> 1;
    return (query(ql, qr, l, mid, ls(p)) + query(ql, qr, mid + 1, r, rs(p))) % mod;
}
void solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    build_tree(1, n, 1);
    while (q--)
    {
        int ope;
        cin >> ope;
        if (ope == 1) // 在[l,r]区间每个数都乘k
        {
            int l, r, k;
            cin >> l >> r >> k;
            mul(l, r, 1, n, 1, k);
        }
        else if (ope == 2) // 在[l,r]区间每个数都加k
        {
            int l, r, k;
            cin >> l >> r >> k;
            add(l, r, 1, n, 1, k);
        }
        else // 询问区间和
        {
            int l, r;
            cin >> l >> r;
            cout << query(l, r, 1, n, 1) << endl;
        }
    }
}

int main()
{
    // std::ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    int t = 1;
    // cin>>t;
    while (t--)
    {
        solve();
    }
    return 0;
}

模板3

将区间的所有值修改为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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int maxn = 1e5 + 10;
ll n, m, a[maxn], t[maxn << 2], tag[maxn << 2];

ll ls(ll x)
{
    return x << 1;
}
ll rs(ll x)
{
    return x << 1 | 1;
}

void push_up(ll p)
{
    t[p] = t[ls(p)] + t[rs(p)];
}

void push_down(int l, int r, int p)
{
    if (tag[p])
    {
        int mid = (l + r) >> 1;
        t[ls(p)] = tag[p] * (mid - l + 1);
        t[rs(p)] = tag[p] * (r - mid);
        tag[ls(p)] = tag[p];
        tag[(rs(p))] = tag[p];
        tag[p] = 0;
    }
}

void build_tree(int l, int r, int p)
{
    if (l == r)
    {
        t[p] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build_tree(l, mid, ls(p));
    build_tree(mid + 1, r, rs(p));
    push_up(p);
}

void update(int l, int r, int ul, int ur, int p, int k)
{
    if (ul <= l && r <= ur)
    {
        t[p] = k * (r - l + 1);
        tag[p] = k;
        return;
    }
    if (tag[p])
        push_down(l, r, p);
    ll mid = (l + r) >> 1;
    if (ul <= mid)
        update(l, mid, ul, ur, ls(p), k);
    if (ur > mid)
        update(mid + 1, r, ul, ur, rs(p), k);
    push_up(p);
}

ll query(int l, int r, int ql, int qr, int p)
{
    if (ql <= l && r <= qr)
        return t[p];
    if (tag[p])
        push_down(l, r, p);
    int mid = (l + r) >> 1;
    ll sum = 0;
    if (ql <= mid)
        sum += query(l, mid, ql, qr, ls(p));
    if (qr > mid)
        sum += query(mid + 1, r, ql, qr, rs(p));
    return sum;
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    build_tree(1, n, 1);
    while(m--)
    {
        int ope;
        cin >> ope;
        if(ope==1)//将区间[l,r]的每个值修改为k
        {
            int l, r, k;
            cin >> l >> r >> k;
            update(1, n, l, r, 1, k);
        }
        else//询问[l,r]的区间和
        {
            int l, r;
            cin >> l >> r;
            cout << query(1, n, l, r, 1) << endl;
        }
    }
}

int main()
{
    // std::ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    int t = 1;
    // cin>>t;
    while (t--)
    {
        solve();
    }
    return 0;
}
Read more »

Posted on In ,
Symbols count in article: 3.3k Reading time ≈ 3 mins.

树状数组基础

树状数组是线段树的简化版，可以做到：1.单点修改，单点查询，2.区间修改，单点查询，3.区间查询，区间修改

树状数组的构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int n;
int a[1005],t[1005]; //对应原数组和树状数组

int lowbit(int x){//计算一个非负整数n在二进制下的最低为1及其后面的0构成的数
    return x&(-x);
}

void add_dandian(int x,int k)//用于更新每一个节点的状态
{
	for(int i=x;i<=n;i+=lowbit(i))
	t[i]+=k;
}


  • 单点修改，区间查询

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int add_dandian(int x,int k)//用于更新每一个节点的状态
    {
    	for(int i=x;i<=n;i+=lowbit(i))
    	t[i]+=k;
    }

    int ask(x){//查询前x项区间
    	int sum = 0;
    	for(int i=x;i;i-=lowbit(i)){
    		sum+=t[i];
    	}
    	return sum;
    }


​ 通过图中不难看出，sum[7]=t[7]+t[6]+t[4] ,我们进一步发现,6=7-lowbit(7),4=6-lowbit(6)，所以我们可以通过不断的- lowbit操作来实现求和

  • 求特定l到r区间(利用前缀和计算)
1
2
3
4
5
6
7
8
9
10
int search(int L,int R)
{
	int ans = 0;
	for(int i=L;i;i-=lowbit(i))
	ans+=c[i];
	for(int i=R-1;i;i-=lowbit(i))
	ans-=c[i];
	return 0;
}

  • 区间修改，单点查询

    我们需要构造出原数组的差分数组b，然后用树状数组维护b数组即可

    对于区间修改的话，我们只需要对差分数组进行操作即可，例如对区间[L,R]+k,那么我们只需要更新差分数组add(L,k),add(R+1,-k)，这是差分数组的性质.

1
2
3
4
5
6
7
8
9
int update(int pos,int k)//pos表示修改点的位置,K表示修改的值也即+K操作
{
	for(int i=pos;i<=n;i+=lowbit(i))
	c[i]+=k;
	return 0;
}
update(L,k);
update(R+1,-k);

Read more »