『树状数组』贪婪大陆

题目描述

人类被蚂蚁们逼到了 Greed Island 上的一个海湾。现在，小 FF 的后方是一望无际的大海， 前方是变异了的超 级蚂蚁。 小 FF 还有大好前程，他可不想命丧于此， 于是他派遣手下最后一批改造 SCV 布置地雷以阻挡蚂蚁们的进攻。

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

题目大意

求一个区间内，被多少个不同的区间覆盖。

题解

对于区间$[L,R]$的答案，我们可以分成两部分：

在区间$[1,R]$中出现的；我们只用统计起点，所有起点小于R的累加即可。在区间$[1,L-1]$中出现但不在区间$[L,R]$中出现的：我们只需要统计$L-1$以内有多少个结尾。显然第一个答案减去第二个答案即可。统计答案需要使用树状数组。

代码如下：

#include <bits/stdc++.h> using namespace std; inline int read(void) { int s = 0, w = 1;char c = getchar(); while (c<'0' || c>'9') {if (c == '-') w = -1; c = getchar();} while (c>='0' && c<='9') s = s*10+c-48,c = getchar(); return s*w; } int n,m; struct BIT { int S[2000000]; #define lowbit(i) (i & -i) void add(int x,int v) { for (int i=x;i<=n;i+=lowbit(i)) S[i] += v; return; } int ask(int x) { int sum = 0; for (int i=x;i>=1;i-=lowbit(i)) sum += S[i]; return sum; } } tree1, tree2; int main(void) { freopen("greedisland.in","r",stdin); freopen("greedisland.out","w",stdout); n = read(); m = read(); while (m --) { int q = read(), l = read(), r = read(); if (q == 1) tree1.add(l,1), tree2.add(r,1); if (q == 2) printf("%d\n", tree1.ask(r)-tree2.ask(l-1)); } return 0; }