首页 > 代码库 > [luoguP2184] 贪婪大陆（树状数组）
[luoguP2184] 贪婪大陆（树状数组）
传送门
用两个树状数组，cr 维护 1....x 中 r 的数量
cl 维护 1....x 中 l 的数量
求答案的时候只需要求 y 前面 被作为左端点 的个数 - x 前面 被作为右端点的个数
——代码
1 #include <cstdio> 2 3 using namespace std; 4 5 const int MAXN = 1000001; 6 int n, m; 7 int cl[MAXN], cr[MAXN]; 8 9 inline void add1(int x) { for(; x <= n; x += x & -x) cl[x]++; }10 inline void add2(int x) { for(; x <= n; x += x & -x) cr[x]++; }11 inline int query1(int x) { int ans = 0; for(; x; x -= x & -x) ans += cl[x]; return ans; }12 inline int query2(int x) { int ans = 0; for(; x; x -= x & -x) ans += cr[x]; return ans; }13 14 int main()15 {16 int i, j, x, y, z;17 scanf("%d %d", &n, &m);18 for(i = 1; i <= m; i++)19 {20 scanf("%d %d %d", &z, &x, &y);21 if(z == 1)22 {23 add1(x);24 add2(y);25 }26 else printf("%d\n", query1(y) - query2(x - 1));27 }28 return 0;29 }
[luoguP2184] 贪婪大陆（树状数组）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。