python

6.8 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##Physical Education Lessons

题意：

Alex高中毕业了，他现在是大学新生。虽然他学习编程，但他还是要上体育课，这对他来说完全是一个意外。快要期末了，但是不幸的Alex的体育学分还是零蛋！

Alex可不希望被开除，他想知道到期末还有多少天的工作日，这样他就能在这些日子里修体育学分。但是在这里计算工作日可不是件容易的事情：

从现在到学期结束还有 n 天(从 1 到 n 编号)，他们一开始都是工作日。接下来学校的工作人员会依次发出 q 个指令，每个指令可以用三个参数 l,r,k 描述：

如果 k=1，那么从 l 到 r （包含端点）的所有日子都变成非工作日。
如果 k=2，那么从 l 到 r （包含端点）的所有日子都变成工作日。

帮助Alex统计每个指令下发后，剩余的工作日天数。

输入格式：

第一行一个整数 n，第二行一个整数 q (1\le n\le 10^9,\;1\le q\le 3\cdot 10^5)，分别是剩余的天数和指令的个数。

接下来 q 行，第 i 行有 3 个整数 l_i,r_i,k_i，描述第 i 个指令 (1\le l_i,r_i\le n,\;1\le k\le 2)。

输出格式：

输出 q 行，第 i 行表示第 i 个指令被下发后剩余的工作日天数。

样例输入 #1

样例输出 #1

二、动态开点线段树解法

#include <bits/stdc++.h>

using namespace std;
#define N 15000010 // 1.5e7=3e5*25*2,log 3e5=25
int n, q;

// 动态开点线段树
#define ls tr[u].l
#define rs tr[u].r
struct Node {
    int l, r;
    int sum, tag;
} tr[N];

int idx;

// 汇总统计信息
void pushup(int u) {
    tr[u].sum = tr[ls].sum + tr[rs].sum;
}

void pushdown(int &u, int l, int r) {
    if (tr[u].tag == -1) return;
    // 如果存在懒标记
    // 准备左右儿子
    if (ls == 0) ls = ++idx; // 没有左儿子，创建,因为传递的是地址符&,所以会回写tr[u].l
    if (rs == 0) rs = ++idx; // 没有右儿子，创建,因为传递的是地址符&,所以会回写tr[u].r
    // 懒标记下传
    int mid = (l + r) >> 1;
    tr[ls].sum = tr[u].tag * (mid - l + 1); // 区间和增加=懒标记 乘以 区间长度
    tr[ls].tag = tr[u].tag;                 // 加法的懒标记可以叠加
    tr[rs].sum = tr[u].tag * (r - mid);     // 区间和增加=懒标记 乘以 区间长度
    tr[rs].tag = tr[u].tag;                 // 加法的懒标记可以叠加
    // 清除懒标记
    tr[u].tag = -1;
}

// 区间修改
void modify(int &u, int l, int r, int L, int R, int v) {
    if (u == 0) u = ++idx, tr[u].tag = -1; // 动态开点，同时，将懒标记修改为-1，初始化
    if (L <= l && r <= R) {                // 完整覆盖
        tr[u].tag = v;                     // 懒标记赋值
        tr[u].sum = v * (r - l + 1);       // 记录sum
        return;                            // 返回节点号
    }

    pushdown(u, l, r);                         // 下放懒标记
    int mid = (l + r) >> 1;                    // 分裂
    if (L <= mid) modify(ls, l, mid, L, R, v); // 与左儿子区间有交集，递归修改左儿子
    if (mid < R) modify(rs, mid + 1, r, L, R, v);
    pushup(u);
}
int root;
int main() {
#ifndef ONLINE_JUDGE
    freopen("CF915E.in", "r", stdin);
#endif
    scanf("%d%d", &n, &q);
    modify(root, 1, n, 1, n, 1);
    int l, r, op;
    for (int i = 1; i <= q; i++) {
        scanf("%d%d%d", &l, &r, &op);
        if (op == 1) {
            modify(root, 1, n, l, r, 0); // 更新对应区间
            printf("%d\n", tr[1].sum);   // 1号节点表示区间(1,n)
        } else {
            modify(root, 1, n, l, r, 1);
            printf("%d\n", tr[1].sum);
        }
    }
    return 0;
}

三、柯朵莉树解法

这题就是一道ODT的板子，操作是推平，查询是求和

Q：这题不保证数据随机为什么还能用ODT?

A：hackODT的方法是没有推平操作，但这题修改操作全是推平操作。

于是暴力很好写，但CF的毒瘤们不会让你过的，故考虑优化。

每次查询区间是一定的，所以就维护一个变量 sum 表示 1→n 的和，再推平时统计，推平区间里有多少个元素值会变化，再根据变成什么修改 sum

#include <bits/stdc++.h>
using namespace std;

#define int long long
int sum;

// 柯朵莉树模板
struct Node {
    int l, r;      // l和r表示这一段的起点和终点
    mutable int v; // v表示这一段上所有元素相同的值是多少,注意关键字 mutable,使得set中结构体属性可修改
    bool operator<(const Node &b) const {
        return l < b.l; // 规定按照每段的左端点排序
    }
};
set<Node> s; // 柯朵莉树的区间集合

// 分裂:[l,x-1],[x,r]
set<Node>::iterator split(int x) {
    auto it = s.lower_bound({x});
    if (it != s.end() && it->l == x) return it; // 一击命中
    it--;                                       // 没有找到就减1个继续找
    if (it->r < x) return s.end();              // 真的没找到,返回s.end()

    int l = it->l, r = it->r, v = it->v; // 没有被返回，说明找到了,记录下来，防止后面删除时被破坏
    s.erase(it);                         // 删除整个区间
    s.insert({l, x - 1, v});             //[l,x-1]拆分
    // insert函数返回pair，其中的first是新插入结点的迭代器
    return s.insert({x, r, v}).first; //[x,r]拆分
}

// 区间加
void add(int l, int r, int v) {
    // 必须先计算itr,后计算itl
    auto R = split(r + 1), L = split(l);
    for (auto it = L; it != R; it++) it->v += v;
}
// 区间赋值
void assign(int l, int r, int v) {
    auto R = split(r + 1), L = split(l);

    // 趁着没删除掉，赶快计算
    int res = 0;
    for (auto it = L; it != R; it++)
        if (it->v != v) res += it->r - it->l + 1; // 一共有多少值会变

    s.erase(L, R);       // 按迭代器开始删除中部的所有块
    s.insert({l, r, v}); // 插入新构建的整个的块

    sum += ((v == 0) ? -res : res); // 是加还是减
}
int n, q;

signed main() {
#ifndef ONLINE_JUDGE
    freopen("CF915E.in", "r", stdin);
#endif
    cin >> n >> q;
    // 柯朵莉树插入最初始的块，值为1
    s.insert({1, n, 1});

    sum = n;
    while (q--) {
        int l, r;
        cin >> l >> r;
        int op;
        cin >> op;
        if (op == 1) {
            assign(l, r, 0);
            printf("%lld\n", sum);
        } else {
            assign(l, r, 1);
            printf("%lld\n", sum);
        }
    }
    return 0;
}

6.8 KiB Raw Permalink Blame History Unescape Escape

题意：