題目大意是給定一串1到n的排列(設為數組a)，求其中滿足a[x]
直接求這樣的排列個數並不好求，我們可以轉化為求a[x]
用left數組記錄i位置前比a[i]小的元素個數，left數組可由樹狀數組預處理得到，那麼我們可以得到求排列個數的公式（具體見碼）
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL long long const LL maxn = 100000 + 5; LL C[2 * maxn], lef[maxn], n; //lef數組表示i之前比a[i]小的數的個數 LL lowbit(LL x) { return x&(-x); } void add(LL x, LL d){ while(x <= n) { C[x] += d; x += lowbit(x); } } LL sum(LL x) { LL ret = 0; while(x > 0) { ret += C[x]; x -= lowbit(x); } return ret; } int main() { LL t, kase = 0; scanf("%I64d", &t); while(t--) { memset(C, 0, sizeof(C)); scanf("%I64d", &n); LL ans = 0; for(LL i = 1; i <= n; i++) { LL tmp; scanf("%I64d", &tmp); lef[i] = sum(tmp); add(tmp, 1); // prLLf("%I64d\n", lef[i]); ans = ans + (n + lef[i] + 1 - tmp - i) * (n + lef[i] - tmp - i) / 2 - (n + lef[i] + 1 - tmp - i) * lef[i]; } printf("Case #%I64d: %I64d\n", ++kase, ans % 100000007); } return 0; }
C++調用python 本文以實例code講解 C++ 調用
線段樹： 圖中的元素【a，b】表示該節點存儲的&
概念性東東 webservice目的：異構平台之間的交
每次可以翻動一個、二個或三個硬幣。（Mock Turt
經典排序算法——堆排序 對於一個int數組，請編寫一個堆
