HDU 5147 Sequence II - c++编程基础

题意：

n（5*10^5）个不同的数字组成的序列a 寻找满足如下约束条件的数字组数： i1

思路：

明显考察的是nlogn的算法我们发现其实ai1和ai2可以放在一起考虑同理ai3和ai4 这两组并没有相互影响

我们来看答案是怎么构成的假设枚举i3的位置那么我们希望知道“i3后面有几个数大于ai3” 这个可以通过树状数组处理

同理假设我们知道i2也希望知道“i2前面有几个数小于ai2” 这个也可以树状数组

那么再利用i3>i2 则答案就可以表示为 sum( num(>ai3) * sum( num(

代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               using namespace std; typedef long long LL; #define N 50000 #define lowbit(x) (x&(-x)) inline void scand(int &ret) { char c; ret = 0; while ((c = getchar()) < '0' || c > '9') ; while (c >= '0' && c <= '9') ret = ret * 10 + (c - '0'), c = getchar(); } int t, n; int c[N + 10], d[N + 10], g[N + 10]; LL ans; void add(int f[], int x, int key) { while (x <= N) { f[x] += key; x += lowbit(x); } } int sum(int f[], int x) { int res = 0; while (x) { res += f[x]; x -= lowbit(x); } return res; } struct node { int val, id; } nd[N + 10]; bool cmp1(node fa, node fb) { return fa.val < fb.val; } bool cmp2(node fa, node fb) { return fa.id < fb.id; } int main() { scand(t); while (t--) { scand(n); for (int i = 1; i <= n; i++) { scand(nd[i].val); nd[i].id = i; } sort(nd + 1, nd + n + 1, cmp1); memset(c, 0, sizeof (c)); memset(d, 0, sizeof (d)); for (int i = 1; i <= n; i++) { int tmp = sum(c, nd[i].id); add(c, nd[i].id, 1); add(d, nd[i].id, tmp); g[nd[i].id] = sum(c, nd[i].id - 1); } sort(nd + 1, nd + n + 1, cmp2); ans = 0; for (int i = 3; i <= n; i++) { int tmp = nd[i].val - 1; tmp = n - i - (tmp - g[i]); ans += (LL) (tmp) * sum(d, i - 1); } printf("%I64d\n", ans); } return 0; }