题目背景
面对蚂蚁们的疯狂进攻, 小 FF 的 Tower defence 宣告失败人类被蚂蚁们逼到了 Greed Island 上的一个海湾现在, 小 FF 的后方是一望无际的大海, 前方是变异了的超级蚂蚁 小 FF 还有大好前程, 他可不想命丧于此, 于是他派遣手下最后一批改造 SCV 布置地雷以阻挡蚂蚁们的进攻
题目描述
小 FF 最后一道防线是一条长度为 N 的战壕, 小 FF 拥有无数多种地雷, 而 SCV 每次可以在 [L , R] 区间埋放同一种不同于之前已经埋放的地雷 由于情况已经十万火急, 小 FF 在某些时候可能会询问你在[ L , R] 区间内有多少种不同的地雷, 他希望你能尽快的给予答复
对于 30% 的数据: 0<=n, m<=1000;
对于 100% 的数据: 0<=n, m<=10^5.
输入输出格式
输入格式:
第一行为两个整数 n 和 m; n 表示防线长度, m 表示 SCV 布雷次数及小 FF 询问的次数总和
接下来有 m 行, 每行三个整数 Q,L , R; 若 Q=1 则表示 SCV 在 [ L , R ] 这段区间布上一种地雷, 若 Q=2 则表示小 FF 询问当前 [ L , R ] 区间总共有多少种地雷
输出格式:
对于小 FF 的每次询问, 输出一个答案(单独一行), 表示当前区间地雷总数
输入输出样例
输入样例 #1:
- 5 4
- 1 1 3
- 2 2 5
- 1 2 4
- 2 3 5
输出样例 #1:
1 2
坑点: 一开始读题没有读清楚, 要求得是一段区间内有多少段不同的区间包括之前已有的地雷 也就是说不只是简单的覆盖问题
导致我 debug 半天, 还不知道是哪里出了问题
正解:
考虑用两个树状数组维护
对于加操作:
[L,R] add1(L,1) add2(R,1)
那么相当于在第一个树状数组中对 L->n 打上了标记, 但是 R+1->n 的标记是不应该
打上的, 但是在第二个树状数组中对 R->n 打上了标记, 那么第一和第二树状数组中 R+1->n
的标记就可以看为相抵消了
在询问的时候:[L,R]
ans=query1(R)-query2(L-1)
WU: 真正做题的时候还是想不到正解, 努力吧
- #include < iostream > #include < cstdio > #include < cmath > #include < queue > #define ll long long#define inf 2147483600#define DB double using namespace std;
- inline int read() {
- int x = 0,
- w = 1;
- char ch = getchar();
- while (!isdigit(ch)) {
- if (ch == - ) w = -1;
- ch = getchar();
- }
- while (isdigit(ch)) x = (x << 3) + (x << 1) + ch - 0,
- ch = getchar();
- return x * w;
- }
- const int N = 1e5 + 10;
- int n,
- m;
- int t1[N],
- t2[N];
- void add1(int x, int p) {
- while (x <= n) t1[x] += p,
- x += (x & ( - x));
- }
- int qq1(int x) {
- int ans = 0;
- while (x) ans += t1[x],
- x -= (x & ( - x));
- return ans;
- }
- void add2(int x, int p) {
- while (x <= n) t2[x] += p,
- x += (x & ( - x));
- }
- int qq2(int x) {
- int ans = 0;
- while (x) ans += t2[x],
- x -= (x & ( - x));
- return ans;
- }
- int main() {
- n = read();
- m = read();
- while (m--) {
- int op,
- L,
- R;
- op = read();
- L = read();
- R = read();
- if (L > R) swap(L, R);
- if (op == 1) add1(L, 1),
- add2(R, 1);
- else cout << qq1(R) - qq2(L - 1) << endl;
- }
- return 0;
- }
没有洒下汗水, 怎么收获果实
来源: http://www.bubuko.com/infodetail-2503673.html