一条简单的树状数组题目,先写好lowbit , update, sum三个函数。
考虑到sum函数只能求 从1 到某点的总和,所以需要更新两次,更新是只能更新从某点到最后的 , 这样的话,先update(a,1) ,然后再 update(b ,-1)。
就能够完成一次的更新过程了。
最后只要将结果求一下奇偶性即可 ,这个东西吧 …… 我本来是只会 x%2 == 0这种方法的……后来有幸,受祖上福荫庇佑,能够膜拜甫神的代码, 崇敬之情之下发现了求奇偶性的如下代码: x&1 , 好吧……年少无知啊。。。跑去百度了……
C++ 中, &运算符是位运算符,代表与运算, 与运算这种玩意 , 就是两个二进制数, 补成相同位……一一对应一下……同一位置上的数,相同的就取相同的, 不同的就取0.
举例: (10010010)&(00010100) = (0001000)
而x&1 这个吧,因为 1的二进制数是(00000001),前面的0 可以加 ,这样进行 与运算,得到的数只能是x 的最后一位,1就1 ,0就0,不发生变化。 而最后一位是 2的0次方,也就是1, 如果该位上是 0, 那么就是偶数,如果是1,那么x 就是奇数……
多么奇妙的方法……膜拜甫神大人。
最后AC Memory : 688KB Time : 796MS
代码:
#include <iostream> #include <cstring> #include <stdio.h> using namespace std; int n; int ba[100001]; int lowbit(int x) { return (x)&(-x); } void update(int i,int x) { while(i<=n) { ba[i]+=x; i+=lowbit(i); } } int sum(int x) { int s=0; while(x>0) { s+=ba[x]; x-=lowbit(x); } return s; } int main() { int i, j, k; int a, b; while(scanf("%d", &n) != EOF) { if(n == 0) break; memset(ba, 0, sizeof(ba)); for(i = 1; i <= n; ++i) { scanf("%d %d", &a, &b); update(a, 1); update(b+1, -1); } for(i = 1; i <= n; ++i) { printf("%d%c", sum(i), i == n?'\n':' '); } } return 0; }