POJ2352 线状数组与超时

本文主要是介绍POJ2352 线状数组与超时，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题本身不难，就是一个线状数组求逆序数的简化。一开始没看清题，题目是按升序输入的，先按y在按x已经升序输入了，所以只要考虑x的大小即可，那么简单，直接线状数组走起。但是这里我第一次碰到了做ACM最不愿意碰到的事–超时，上网查了一下，发现算法明明一样，但他们的能过，最后终于发现了问题和解决方案。

因为不需要离散化，update中不能到n，那么就干脆一直计算到maxn，所以这里是要花很多的时间的，那么问题就在：当x=1，从1到maxn都要+1，可以想见这边时间爆炸了，所以这边导致超时。
那么网上的解决方案是：反正就是求个相对大小的比较，所以只要所有的输入值都变大，最后结果应该是不变的，那么就每一个输入都+1，最小也是从2开始，那么就减小了很大一部分时间，因为前面的那个影响后面的是比较多的。
因为我们数组一般习惯开的稍微大一些，所以，比如我maxn取32005，那么后面就可以从6开始，不影响结果，但如果从11开始就不行了。
这应该是算树状数组避免超时的一个小技巧，还是有必要记一下的(适用于一个个输入计算时，一开始全部输入再计算可以用maxN与输入值比较算出输入的最大值在update中使用，也可以减少时间)

代码如下：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;const int maxn =32005;
int n;
int c[maxn];int lowbit(int k)
{return k&(-k);
}
void update(int t)
{while (t <= maxn){c[t] ++;t += lowbit(t);}
}int getsum(int t)
{int sum=0;while (t >= 1){sum += c[t];t -= lowbit(t);}return sum-1;//计算时把自己算上了，所以-1
}int main()
{int i;int x, y;int num[maxn];while (~scanf("%d", &n)){memset(num, 0, sizeof(num));memset(c, 0, sizeof(c));for (i = 1; i <= n; i++){scanf("%d%d", &x, &y);x+=5; //关键在这一句update(x);num[getsum(x)]++;}for (i = 0; i < n; i++)printf("%d\n", num[i]);}return 0;
}