CodeForces 915E Physical Education Lessons 线段树动态开点
题目链接：https://codeforces.com/problemset/problem/915/E
题意：q次操作，每次将一段区间置0或者置1，然后输出1~n中0的个数
思路：由于n太大，所以我们考虑线段树动态开点，可以大大减少点的数量便于维护，这也是一道动态开点的模板题
#include<bits/stdc++.h>using namespace std;typedef long long ll;#define fi first#define se second#define ls rt << 1#define rs rt << 1|1#define po pop_back#define pb push_back#define mk make_pair#define lson l, mid, ls#define rson mid + 1, r, rs#define pll pair<ll, ll>#define pii pair<int, int>#define ull unsigned long long#define pdd pair<double, double>const int mod = 1e9 + 7;const int maxn = 3e5 + 10;const int inf = 0x3f3f3f3f;const ll linf = 0x3f3f3f3f3f3f3f3f;struct seg{int lc, rc, val, lazy;}tree[maxn * 50];int root = 0, tot = 0; //根结点和结点编号，多样例初始化int build(){++tot;tree[tot].lc = tree[tot].rc = tree[tot].val = 0;tree[tot].lazy = -1; //return tot;}void push_up(int rt){tree[rt].val = tree[tree[rt].lc].val + tree[tree[rt].rc].val;}void push_down(int l, int r, int rt){if(tree[rt].lazy != -1 && l != r){int mid = (l + r) >> 1;if(!tree[rt].lc) tree[rt].lc = build();if(!tree[rt].rc) tree[rt].rc = build();tree[tree[rt].lc].val = tree[rt].lazy * (mid - l + 1);tree[tree[rt].lc].lazy = tree[rt].lazy;tree[tree[rt].rc].val = tree[rt].lazy * (r - mid);tree[tree[rt].rc].lazy = tree[rt].lazy;tree[rt].lazy = -1;}}void update(int ql, int qr, int val, int l, int r, int &rt) //区间修改 传递引用{if(!rt) rt = build();if(ql <= l && r <= qr){tree[rt].val = val * (r - l + 1);tree[rt].lazy = val;return;}int mid = (l + r) >> 1;push_down(l, r, rt);if(ql <= mid) update(ql, qr, val, l, mid, tree[rt].lc);if(qr > mid) update(ql, qr, val, mid + 1, r, tree[rt].rc);push_up(rt);}int query(int ql, int qr, int l, int r, int rt){if(!rt) return 0;if(ql <= l && qr <= r)return tree[rt].val;int mid = (l + r) >> 1, res = 0;if(ql <= mid)res += query(ql, qr, l, mid, tree[rt].lc);if(qr > mid)res += query(ql, qr, mid + 1, r, tree[rt].rc);return res;}int main(){int n, q;scanf("%d%d", &n, &q);while(q--){int l, r, k;scanf("%d%d%d", &l, &r, &k);update(l, r, k % 2, 1, n, root);printf("%d\n", n - query(1, n, 1, n, root));}return 0;}
布满荆棘的人生
我就是我
爱被打了一巴掌
╰+攻爆jí腚メ
还没有评论，来说两句吧...