糖果 二维树状数组

糖果 （二维树状数组）

题目描述

　　小姜找到了童话中“糖果国”，这里大到摩天大厦，小到小花小草都是用糖果建造而成的。更加神奇的是，天空中飘满了五颜六色的糖果云，很快糖果雨密密麻麻从天而落，红色的是草蓦糖，黄色的是柠檬糖，绿色的是薄荷糖，黑色的是巧克力糖……任何时候天空中所有的云朵颜色都不相同，不同颜色的云朵在不断地落下相应颜色的糖果。小姜发现天空中会不断出现一些云朵，而有的云朵在某一时刻又会自动消失，而云朵在存在时会不断地落下相应颜色的糖果，小姜有许多容量无限且袋口宽度不同的口袋，小姜完全接到一种糖果，当且仅当下落该种糖果的那朵云被袋口完全包含，小姜想知道每次他拿出一个袋口为[L,R]的口袋后他能完全接到多少种糖果。

输入

　　第一行，一个正整数N，表示所有事件的总数。 　　接下来N行，每行第一个数为flag。 　　如果flag=1，后面有两个正整数　X,Y　表示天空中出现一朵范围为[X,Y]的云。 　　如果flag=2，后面有两个正整数　X,Y　表示一朵范围为[X,Y]的云从天空消失。 　　如果flag=3，后面也是两个正整数　X,Y　表示小姜拿出一个袋口范围为[X,Y]的口袋。

输出

对于每一个小姜拿出口袋的操作，输出这个口袋能完全接到多少种糖果。

样例输入

5 1 1 2 1 3 4 3 1 3 2 1 2 3 1 3

样例输出

1 0

数据范围

1 ≤ N ≤ 200000，1 ≤ X,Y ≤ 1010，1 ≤ flag ≤ 3

备注

（1）给出袋子并经行查询时，是查询拿出袋子瞬间所能接到的糖果种类。 （2）糖果从云上掉下不计时间（即认为是瞬间），且云会不断的掉下糖果，直到消失。

解题思路：

暴力：这道题暴力的话，应该可以过20%的数据； 正解: 首先根据暴力思路不难想出在统计一个袋子能接的糖果种数时，需要计算所有包含于[L,R]这个区间的云数；所以就是在所有现存的云中找到x>=L&&y<=R的云数。再看数据范围，因为x,y都很小。所以我们就可以把这一段区间抽象成二维平面上的点来做。这样问题的解就变成了求一个点右下方的点的数量。点的数量用二维树状数组来维护就行了。

Code

#include<cstdio> #define lowbit(x) (x & -x) const int MAXN = 1015; int arr[MAXN][MAXN], n, id, x, y; inline void Read(int &Ret){ char ch; int flg = 1; while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') flg = -1; Ret = ch - '0'; while(ch = getchar(), ch >= '0' && ch <= '9') Ret = Ret * 10 + ch - '0'; ungetc(ch, stdin); Ret *= flg; } inline void update(int x, int y, int v){ int k; while(x <= 1010){ k = y; while(k <= 1010){ arr[x][k] += v; k += lowbit(k); } x += lowbit(x); } } inline int getsum(int x, int y){ int k, sum = 0; while(x){ k = y; while(k){ sum += arr[x][k]; k -= lowbit(k); } x -= lowbit(x); } return sum; } int main(){ Read(n); while(n --){ Read(id); Read(x); Read(y); if(id == 1) update(x, y, 1); else if(id == 2) update(x, y, -1); else printf("%d\n",getsum(1010, y) - getsum(x - 1, y)); } return 0; }