145 条题解

  • -2
    @ 2023-4-8 20:33:53

    很简单,线段树模板题。

    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    int x, y, a[100005];
    struct node {
    	int l, r, w, tag;
    } tr[400005];
    inline bool inrange(int l1, int r1, int l2, int r2) {
    	return (l1 >= l2) && (r1 <= r2);
    }
    inline bool outofrange(int l1, int r1, int l2, int r2) {
    	return (l1 > r2) || (l2 > r1);
    }
    inline void pushup(int u) {
    	tr[u].w = tr[u * 2].w + tr[u * 2 + 1].w;
    }
    inline void build(int u, int l, int r) {
    	if (l == r) {
    		tr[u].w = a[l];
    		return;
    	}
    	int mid = l + r >> 1;
    	build(u * 2, l, mid); build(u * 2 + 1, mid + 1, r);
    	pushup(u);
    }
    inline int query1(int u, int l, int r, int p) {
    	if (l == r) {
    		return tr[u].w;
    	} else {
    		int mid = l + r >> 1;
    		if (p <= mid) return query1(u * 2, l, mid, p);
    		else return query1(u * 2 + 1, mid + 1, r, p);
    	}
    }
    inline void update1(int u, int l, int r, int p, int x) {
    	if (l == r) {
    		tr[u].w += x;
    	} else {
    		int mid = l + r >> 1;
    		if (mid >= p) update1(u * 2, l, mid, p, x);
    		else update1(u * 2 + 1, mid + 1, r, p, x);
    	}
    }
    inline void maketag(int u, int len, int x) {
    	tr[u].tag += x;
    	tr[u].w += len * x;
    }
    inline void pushdown(int u, int l, int r) {
    	int mid = l + r >> 1;
    	maketag(u * 2, mid - l + 1, tr[u].tag);
    	maketag(u * 2 + 1, r - mid, tr[u].tag);
    	tr[u].tag = 0;
    }
    inline int query(int u, int l1, int r1, int l2, int r2) {
    	if (inrange(l1, r1, l2, r2)) {
    		return tr[u].w;
    	} else if (!outofrange(l1, r1, l2, r2)) {
    		int mid = l1 + r1 >> 1;
    		pushdown(u, l1, r1);
    		return query(u * 2, l1, mid, l2, r2) + query(u * 2 + 1, mid + 1, r1, l2, r2);
    	}
    }
    inline void update(int u, int l1, int r1, int l2, int r2, int x) {
    	if (inrange(l1, r1, l2, r2)) {
    		maketag(u, r1 - l1 + 1, x);
    	} else if (!outofrange(l1, r1, l2, r2)) {
    		int mid = l1 + r1 >> 1;
    		pushdown(u, l1, r1);
    		update(u * 2, l1, mid, l2, r2, x);
    		update(u * 2 + 1, mid + 1, r1, l2, r2, x);
    		pushup(u);
    	}
    }
    signed main() {
        cin >> x >> y;
        build(1, 1, 1);
        update1(1, 1, 1, 1, x);
        update1(1, 1, 1, 1, y);
        cout << query1(1, 1, 1, 1);
        return 0;
    }
    

信息

ID
56
时间
1000ms
内存
1024MiB
难度
1
标签
递交数
9073
已通过
4043
上传者