思路详解参见:http://blog.sina.com.cn/s/blog_691ce2b70101lolv.html
这里用树状数组实现,时间要快很多。
//0 KB 113 ms
#include <stdio.h>
#include <string.h>
#define lowbit(x) (x &(-x))
const int M = 100005;
const int N = 20005;
int ar[M],val[N],lmin[N],rmin[N];
void add (int x)
{
while (x <= M)
ar[x] += 1,x += lowbit(x);
}
int sum(int x)
{
int res = 0;
while (x > 0)
res += ar[x],x -= lowbit(x);
return res;
}
int main ()
{
int T,n,i......
阅读全文