嗯……这题是个标题党……【妈蛋其实大部分题目都是标题党啊我发现。。。
一开始不会做,即便empty大神提示说这是个树状数组的题目……给empty大人丢脸了……【事后Empty大神狠狠得指责了我。。。
嗯……说正事,这题得求和……
求出某个数之后的,比它大的数的个数n,这样形成的组合就是C(n,2),然后再减去三个顺次增大的,就得到要求的那种x<z<y的形式了。
然后是怎么求那个n , 嗯……树状数组,求出在他之前比它小的,
RunID |
user |
Problem |
Result |
Memory |
Time |
Language | Length |
Submit Time |
---|---|---|---|---|---|---|---|---|
2248124 | congjiujiu | D | Accept | 688KB | 359MS | G++ | 732B | 2014-05-13 19:43:30 |
代码:
#include <cstdio> #include <iostream> #include <cstring> using namespace std; int a, n, c[100001]; long long ans, tmp, tmp1; int lowbit(int x) { return x&(-x); } void update(int i) { while(i<=n) { c[i]+=1; i+=lowbit(i); } } int sum(int i) { int s=0; while(i>0) { s += c[i]; i-=lowbit(i); } return s; } int main() { int i, T, cnt=1; scanf("%d", &T); while(T--) { scanf("%d", &n); ans = 0; memset(c,0,sizeof(c)); for(i=1; i<=n; i++) { scanf("%d", &a); update(a); tmp = sum(a-1); tmp1 = (n-a)-(i-1-tmp); ans -= tmp*tmp1; if(tmp1>=2) ans += tmp1*(tmp1-1)/2; } ans %=100000007; printf("Case #%d: %I64d\n", cnt++, ans); } return 0; }