P2184 贪婪大陆

题目描述

小 FF 最后一道防线是一条长度为 $n$ 的战壕，小 FF 拥有无数多种地雷，而 SCV 每次可以在 $[L,R]$ 区间埋放同一种不同于之前已经埋放的地雷。由于情况已经十万火急，小 FF 在某些时候可能会询问你在 $[L^{\prime },R^{\prime }]$ 区间内有多少种不同的地雷，他希望你能尽快的给予答复。

输入格式

第一行为两个整数 $n$ 和 $m$，$n$ 表示防线长度，$m$ 表示 SCV 布雷次数及小 FF 询问的次数总和。

接下来有 $m$ 行，每行三个整数 $q,l,r$：

• 若 $q=1$，则表示 SCV 在 $[l,r]$ 这段区间布上一种地雷；
• 若 $q=2$，则表示小 FF 询问当前 $[l,r]$ 区间总共有多少种地雷。

$0\le n$，$m\le {10}^5$。

输出格式

对于小 FF 的每次询问，输出一个答案（单独一行），表示当前区间地雷总数。

Solution

线段树/树状数组/差分思想

本题就是属于线段树不太好做，树状数组有优势的题目

实际上是单点修改/区间查询的题目

C41 线段树+差分 P2184 贪婪大陆_哔哩哔哩_bilibili

求区间 $[l,r]$ 中地雷种类个数即求 $[1,r]$ 内起点的个数 $-$ $[1,l-1]$ 内终点的个数 (即为 $[1,r]$ 内个数减去前面的完整的线段个数)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define ls u<<1
#define rs u<<1|1
const int N = 100005;
int n, m;
struct tree {
    int l, r, sum[2];
}tr[N * 4];
//sum[0]:区间起点数, sum[1]:区间终点数

void pushup(int u, int k) { //上传
    tr[u].sum[k] = tr[ls].sum[k] + tr[rs].sum[k];
}
void build(int u, int l, int r) { //建树
    tr[u] = {l,r,0,0};
    if (l == r)return;
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
}
void change(int u, int x, int k) { //点修
    if (tr[u].l == tr[u].r) {
        tr[u].sum[k]++; return;
    }
    if (x <= tr[ls].r) change(ls, x, k);
    else change(rs, x, k);
    pushup(u, k);
}
int query(int u, int x, int y, int k) { //区查
    if (x > tr[u].r || y < tr[u].l)return 0;
    if (x <= tr[u].l && tr[u].r <= y)return tr[u].sum[k];
    return query(ls, x, y, k) + query(rs, x, y, k);
}
int main() {
    cin >> n >> m;
    build(1, 1, n);
    for (int i = 1;i <= m;i++) {
        int q, l, r; cin >> q >> l >> r;
        if (q == 1) change(1, l, 0), change(1, r, 1);
        else cout << query(1, 1, r, 0) - query(1, 1, l - 1, 1) << '\n';
    }
}