c/c++语言开发共享P2184 贪婪大陆

题目

p2184 贪婪大陆

解析

线段树，差分？
在所修改的区间的开头位置+1，表示从这个位置开始往后开始埋一种地雷，在结尾位置+1，表示在这个位置有一种地雷被埋完
查询的时候我们就只需要查询

• ([1,r])中开头的位置，表示(1)到r中共埋了多少种类型的地雷
• ([1,l-1])中结尾的个数，表示(1)到(l-1)中有多少种类型的地雷被埋完，因为在(l)之前就埋完了，所以不会影响([l,r])内的答案

所以查询时输出前者减后者的差就可以了。
线段树维护单点修改+区间查询

代码

#include <bits/stdc++.h> using namespace std; const int n = 1e6 + 10; int n, m; int d[n]; class tree {   public:     int len, sta, end; } t[n];  #define lson rt << 1 #define rson rt << 1 | 1  template<class t>inline void read(t &x) {     x = 0; int f = 0; char ch = getchar();     while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();     while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();     x = f ? -x : x;     return; }  void build(int l, int r, int rt) {     t[rt].len = r - l + 1;     if (l == r) return;     int m = (l + r) >> 1;     build(l, m, lson), build(m + 1, r, rson); }  void update_sta(int l, int c, int l = 1, int r = n, int rt = 1) {     if (l == r) {         t[rt].sta += c;         return ;     }     int m = (l + r) >> 1;     if (l <= m) update_sta(l, c, l, m, lson);     else update_sta(l, c, m + 1, r, rson);     t[rt].sta = t[lson].sta + t[rson].sta; }  void update_end(int l, int c, int l = 1, int r = n, int rt = 1) {     if (l == r) {         t[rt].end += c;         return ;     }     int m = (l + r) >> 1;     if (l <= m) update_end(l, c, l, m, lson);     else update_end(l, c, m + 1, r, rson);     t[rt].end = t[lson].end + t[rson].end; }  int query_sta(int l, int r, int l = 1, int r = n, int rt = 1) {     if (l <= l && r <= r) return t[rt].sta;     int m = (l + r) >> 1, ans = 0;     if (l <= m) ans += query_sta(l, r, l, m, lson);     if (r > m) ans += query_sta(l, r, m + 1, r, rson);     return ans; }  int query_end(int l, int r, int l = 1, int r = n, int rt = 1) {     if (l <= l && r <= r) return t[rt].end;     int m = (l + r) >> 1, ans = 0;     if (l <= m) ans += query_end(l, r, l, m, lson);     if (r > m) ans += query_end(l, r, m + 1, r, rson);     return ans; }  int main() {     read(n), read(m);     build(1, n, 1);     for (int i = 1, x, y, opt; i <= m; ++i) {         read(opt) , read(x), read(y);         if (opt == 1) update_sta(x, 1), update_end(y, 1);         else printf("%dn", query_sta(1, y) - query_end(1, x - 1));     } }