线段树

2020-03-07

字数统计: 443字 | 阅读时长≈ 2分钟

线段树的总结

HYSBZ - 1012 最大数maxnumber (线段树)

#include <bits/stdc++.h>
#define ll long long
#define maxn 200005
using namespace std;
struct node
{
    ll left, right;
    ll maxx;
};
node tree[maxn << 2];
ll a[maxn] = {0};
ll n;
ll p = 0, q;
void build(int m, int l, int r)
{
    tree[m].left = l;
    tree[m].right = r;
    if (l == r){
        tree[m].maxx = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(m << 1, l, mid);
    build(m << 1 | 1, mid + 1, r);
    tree[m].maxx = max(tree[m << 1].maxx, tree[m << 1 | 1].maxx);
}
void update(int m, int a, int val)
{
    if (tree[m].left == a && tree[m].right == a){
        tree[m].maxx += val;
        return;
    }
    int mid = (tree[m].left + tree[m].right) >> 1;
    if (a <= mid){
        update(m << 1, a, val);
    }
    else{
        update(m << 1 | 1, a, val);
    }
    tree[m].maxx = max(tree[m << 1].maxx, tree[m << 1 | 1].maxx);
}
ll queryMax(int m, int l, int r)
{
    if (l == tree[m].left && r == tree[m].right){
        return tree[m].maxx;
    }
    int mid = (tree[m].left + tree[m].right) >> 1;
    if (r <= mid){
        return queryMax(m << 1, l, r);
    }
    else if (l > mid){
        return queryMax(m << 1 | 1, l, r);
    }
    return max(queryMax(m << 1, l, mid), queryMax(m << 1 | 1, mid + 1, r));
}
int main()
{
    ll t = 0,i,j, k, MOD, l;
    char cmd;
    scanf("%lld %lld", &n, &MOD);
    build(1, 1, n);
    for(k = 1; k <= n; k++)
    {
        getchar();
        scanf("%c %lld", &cmd, &l);
        if(cmd == 'Q')
        {
            //cout << p - l + 1 << " " << p << endl;
            t = queryMax(1, p - l + 1,p);
            printf("%lld\n", t);
        }
        else
        {
            update(1, p + 1, (l + t) % MOD);
            p++;
        }
    }
    return 0;
}

1	#include <bits/stdc++.h>
2	#define ll long long
3	#define maxn 200005
4	using namespace std;
5	struct node
6	{
7	ll left, right;
8	ll maxx;
9	};
10	node tree[maxn << 2];
11	ll a[maxn] = {0};
12	ll n;
13	ll p = 0, q;
14	void build(int m, int l, int r)
15	{
16	tree[m].left = l;
17	tree[m].right = r;
18	if (l == r){
19	tree[m].maxx = a[l];
20	return;
21	}
22	int mid = (l + r) >> 1;
23	build(m << 1, l, mid);
24	build(m << 1 \| 1, mid + 1, r);
25	tree[m].maxx = max(tree[m << 1].maxx, tree[m << 1 \| 1].maxx);
26	}
27	void update(int m, int a, int val)
28	{
29	if (tree[m].left == a && tree[m].right == a){
30	tree[m].maxx += val;
31	return;
32	}
33	int mid = (tree[m].left + tree[m].right) >> 1;
34	if (a <= mid){
35	update(m << 1, a, val);
36	}
37	else{
38	update(m << 1 \| 1, a, val);
39	}
40	tree[m].maxx = max(tree[m << 1].maxx, tree[m << 1 \| 1].maxx);
41	}
42	ll queryMax(int m, int l, int r)
43	{
44	if (l == tree[m].left && r == tree[m].right){
45	return tree[m].maxx;
46	}
47	int mid = (tree[m].left + tree[m].right) >> 1;
48	if (r <= mid){
49	return queryMax(m << 1, l, r);
50	}
51	else if (l > mid){
52	return queryMax(m << 1 \| 1, l, r);
53	}
54	return max(queryMax(m << 1, l, mid), queryMax(m << 1 \| 1, mid + 1, r));
55	}
56	int main()
57	{
58	ll t = 0,i,j, k, MOD, l;
59	char cmd;
60	scanf("%lld %lld", &n, &MOD);
61	build(1, 1, n);
62	for(k = 1; k <= n; k++)
63	{
64	getchar();
65	scanf("%c %lld", &cmd, &l);
66	if(cmd == 'Q')
67	{
68	//cout << p - l + 1 << " " << p << endl;
69	t = queryMax(1, p - l + 1,p);
70	printf("%lld\n", t);
71	}
72	else
73	{
74	update(1, p + 1, (l + t) % MOD);
75	p++;
76	}
77	}
78	return 0;
79	}