WizCode
文章
50
标签
79
评论
0

单点修改，求区间最大值

#include <iostream>
#include <cstring>
#define code() cin.tie(0),ios::sync_with_stdio(false)
using namespace std;
const int N = 200010;

int n, m, w[N];
struct Node
{
    int l, r, v;
}tr[N << 2];

void pushup(int u)
{
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, w[r]};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int x, int v)
{
    if (tr[u].l == x && tr[u].r == x)   tr[u].v = v;
    else 
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid)   modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if (l <= tr[u].l && tr[u].r <= r)   return tr[u].v;
    int mid = tr[u].l + tr[u].r >> 1;
    int v = 0;
    if (l <= mid)   v = query(u << 1, l, r);
    if (r > mid)    v = max(v, query(u << 1 | 1, l, r));
    return v;
}

int main()
{
    code();
    while (cin >> n >> m)
    {
        memset(tr, 0, sizeof tr);
        memset(w, 0, sizeof w);
        for (int i = 1; i <= n; i++)    cin >> w[i];
        
        build(1, 1, n);
        
        while (m--)
        {
            string op;  int a, b;
            cin >> op >> a >> b;
            if (op == "U")  modify(1, a, b);
            else cout << query(1, a, b) << endl;
        }
    }
}

单点修改，求区间和

#include <bits/stdc++.h>
using namespace std;
 
const int N = 100010;
 
int n, m;
int w[N]; //记录一下权重
 
struct Node
{
    int l, r;  //左右区间
    int sum;  //总和
}tr[N * 4];  //记得开 4 倍空间
 
void pushup(int u)  //利用它的两个儿子来算一下它的当前节点信息
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;  //左儿子 u<<1 ,右儿子 u<<1|1
}
 
void build(int u, int l, int r)  /*第一个参数，当前节点编号，第二个参数，左边界，第三个参数，右边界*/
{
    if (l == r) tr[u] = {l, r, w[r]}; //如果当前已经是叶节点了，那我们就直接赋值就可以了
    else  //否则的话，说明当前区间长度至少是 2，那么我们需要把当前区间分为左右两个区间，那先要找边界点
    {
        tr[u] = {l, r};  //这里记得赋值一下左右边界的初值
        int mid = l + r >> 1;  //边界的话直接去计算一下 l + r 的下取整
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);  //先递归一下左儿子,然后递归一下右儿子
        pushup(u);  //做完两个儿子之后的话呢 push_up一遍u，更新一下当前节点信息
    }
}
 
int query(int u, int l, int r)  //查询的过程是从根结点开始往下找对应的一个区间
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;    //如果当前区间已经完全被包含了，那么我们直接返回它的值就可以了
    //否则的话我们需要去递归来算
    int mid = tr[u].l + tr[u].r >> 1;  //计算一下我们 当前 区间的中点是多少  
    int sum = 0;
    if (l <= mid) sum = query(u << 1, l, r);  //看一下我们当前区间的中点和左边有没有交集
    if (r > mid) sum += query(u << 1 | 1, l, r);  //看一下我们当前区间的中点和右边有没有交集
    return sum;
}
 
void modify(int u, int x, int v) //第一个参数也就是当前节点的编号,第二个参数是要修改的位置，第三个参数是要修改的值
{
    if (tr[u].l == tr[u].r) tr[u].sum += v;  //如果当前已经是叶节点了，那我们就直接让他的总和加上 v 就可以了
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;  //看一下 x 是在左半边还是在右半边
        if (x <= mid) modify(u << 1, x, v);  //如果是在左半边，那就找左儿子
        else modify(u << 1 | 1, x, v);  //如果在右半边，那就找右儿子
        pushup(u);  //push_up一遍u，更新一下当前节点信息
    }
}
 
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    build(1, 1, n);  /*第一个参数是根节点的下标，根节点是一号点，然后初始区间是 1 到 n */
 
    int k, a, b;
    while (m -- )
    {
        scanf("%d%d%d", &k, &a, &b);
        if (k == 0) printf("%d\n", query(1, a, b));   //也是传三个参数，第一个的话是根节点的编号 ，第二个的话是我们查询的区间 
        else modify(1, a, b);  //第一个参数是根节点的下标,第二个参数是要修改的位置，第三个参数是要修改的值
    }
 
    return 0;
}

单点修改，求区间最大连续和

#include <bits/stdc++.h>
#define code() cin.tie(0),ios::sync_with_stdio(false)
using namespace std;
const int N = 500010;

int n, m, w[N];
struct Node
{
	int l, r, sum, lmax, rmax, tmax; 	
}tr[N << 2];

void pushup(Node &u, Node &l, Node &r)
{
	u.sum = l.sum + r.sum;
	u.lmax = max(l.lmax, l.sum + r.lmax);
	u.rmax = max(r.rmax, r.sum + l.rmax);
	u.tmax = max({l.tmax, r.tmax, l.rmax + r.lmax});
}

void pushup(int u)
{
	pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);	
}

void build(int u, int l, int r)
{
	if (l == r)	tr[u] = {l, r, w[r], w[r], w[r], w[r]};
	else 
	{
		tr[u] = {l, r};
		int mid = l + r >> 1;
		build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
		pushup(u);
	}
}

void modify(int u, int x, int v)
{
	if (tr[u].l == x && tr[u].r == x)	tr[u] = {x, x, v, v, v, v};
	else 
	{
		int mid = tr[u].l + tr[u].r >> 1;
		if (x <= mid)	modify(u << 1, x, v);
		else modify(u << 1 | 1, x, v);
		pushup(u);
	}
}

Node query(int u, int l, int r)
{
	if (l <= tr[u].l && tr[u].r <= r)	return tr[u];
	else
	{
		int mid = tr[u].l + tr[u].r >> 1;
		if (r <= mid)	return query(u << 1, l, r);
		else if (l > mid)	return query(u << 1 | 1, l, r);
		else 
		{
			auto left = query(u << 1, l, r);
			auto right = query(u << 1 | 1, l, r);
			Node res;
			pushup(res, left, right);
			return res;
		}
	}	
}

int main()
{
    code();
    
	cin >> n >> m;
	for (int i = 1; i <= n; i++)	cin >> w[i];
	
	build(1, 1, n);
	
	while (m--)
	{
		int op, a, b;	cin >> op >> a >> b;
		if (op == 1)
		{
			if (a > b)	swap(a, b);
			cout << query(1, a, b).tmax << endl;
		}
		else modify(1, a, b);
	}
	
	return 0;
}

区间增加，区间查询连续和

#include <bits/stdc++.h>
#define int long long
#define code() cin.tie(0),ios::sync_with_stdio(false)
using namespace std;
const int N = 100010;

int n, m, w[N];
struct Node
{
	int l, r, sum, lazy;
}tr[N << 2];

void pushup(int u)
{
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u)
{
	auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
	if (root.lazy)
	{
		left.lazy += root.lazy, left.sum += (left.r - left.l + 1) * root.lazy;
		right.lazy += root.lazy, right.sum += (right.r - right.l + 1) * root.lazy;
		root.lazy = 0;
	}	
}

void build(int u, int l, int r)
{
	if (l == r)	tr[u] = {l, r, w[r], 0};
	else 
	{
		tr[u] = {l, r};
		int mid = l + r >> 1;
		build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
		pushup(u);
	}		
}

void modify(int u, int l, int r, int d)
{
	if (l <= tr[u].l && tr[u].r <= r)	
	{
		tr[u].sum += (tr[u].r - tr[u].l + 1) * d;
		tr[u].lazy += d;
	}
	else 
	{
		pushdown(u);
		int mid = tr[u].l + tr[u].r >> 1;
		if (l <= mid)	modify(u << 1, l, r, d);
		if (r > mid)	modify(u << 1 | 1, l, r, d);
		pushup(u);
	}
}

int query(int u, int l, int r)
{
	if (l <= tr[u].l && tr[u].r <= r)	return tr[u].sum;
	else
	{
		pushdown(u);
		int mid = tr[u].l + tr[u].r >> 1;
		int sum = 0;
		if (l <= mid)	sum = query(u << 1, l, r);
		if (r > mid) sum += query(u << 1 | 1, l, r);
		return sum;	
	}	
}

signed main()
{
    code();
	cin >> n >> m;
	for (int i = 1; i <= n; i++)	cin >> w[i];
	build(1, 1, n);
	
	while (m--)
	{
		string op; int l, r, d;
		cin >> op >> l >> r;
		
		if (op == "C")	
		{
			cin >> d;
			modify(1, l, r, d);
		}
		else 
		{
			cout << query(1, l, r) << endl;
		}
	}
	return 0;
}

区间修改，区间查询连续和

// 区间修改，区间查询
#include <iostream>
#include <cstring>
#define code() cin.tie(0),ios::sync_with_stdio(false)
#define int long long
using namespace std;
const int N = 100010;

int n, m, cnt, w[N];
struct Node
{
    int l, r, sum, lazy;
}tr[N << 2];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.lazy)
    {
        left.lazy = root.lazy, left.sum = (left.r - left.l + 1) * root.lazy;
        right.lazy = root.lazy, right.sum = (right.r - right.l + 1) * root.lazy;
        root.lazy = 0;
    }   
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, w[r], 0};
    else 
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }       
}

void modify(int u, int l, int r, int d)
{
    if (l <= tr[u].l && tr[u].r <= r)   
    {
        tr[u].sum = (tr[u].r - tr[u].l + 1) * d;
        tr[u].lazy = d;
    }
    else 
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid)   modify(u << 1, l, r, d);
        if (r > mid)    modify(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if (l <= tr[u].l && tr[u].r <= r)   return tr[u].sum;
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        int sum = 0;
        if (l <= mid)   sum = query(u << 1, l, r);
        if (r > mid) sum += query(u << 1 | 1, l, r);
        return sum; 
    }   
}


void solve()
{
    memset(tr, 0, sizeof tr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)    w[i] = 1;
    build(1, 1, n);

    while (m--)
    {
        int l, r, v;    cin >> l >> r >> v;
        modify(1, l, r, v);
    }
    printf("Case %ld: The total value of the hook is %ld.\n", cnt, query(1, 1, n));
}

signed main()
{
    code();
    int t;  cin >> t;
    while (t--) cnt++, solve();
    return 0;
}
文章作者: WizCode
文章连结: /archives/xian-duan-shu-he-ji
版权声明: 本部落格所有文章除特别声明外，均採用 CC BY-NC-SA 4.0 许可协议。转载请註明来自 WizCode！
线段树
上一篇 下一篇