题解 P1637 【三元上升子序列】

· · 题解

## $Description

本题暴力十分好打，只需O(n^2) 暴力扫两遍，找出第i个数在i前面并且比a[i]小的数有sum[i]个，在i后面并且比a[i]大的数有sum2[i]个。 根据乘法原理，ans=sum[i]*sum2[i]。

但显然，对于30000 的数据，n^2的复杂度显然会T。 这时，我们就要动用一些奇技淫巧优化， 这个玩意可以刺激cpu并发， 比暴力不知道快到哪里去了

Code: 


// luogu-judger-enable-o2
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include<bits/stdc++.h>
#define R register
using namespace std;
typedef long long ll;
inline char gc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return (p1 == p2) && (p2 = (p1 = buf) + 
        fread (buf, 1, 100000, stdin), p1 == p2)? EOF: *p1++;
}
#define int ll
inline ll read(){
    ll res=0,f=1;
    char ch=gc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=gc();}
    while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+ch-'0';ch=gc();}
    return res*f;
}
void write(ll x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
}
const int N=30005;
ll ans,n,sum[N],sum2[N],a[N];
#define debug(x) (cout << "#x = " << (x) << endl)
signed main(){
    n=read();
    for(R int i=1;i<=n;i++) a[i]=read();
    for(R int i=1;i<=n;i++){
        R int j = 1;
        R int a1 = 0, a2 = 0;
        R int a3 = 0, a4 = 0;
        R int a5 = 0, a6 = 0;
        R int a7 = 0, a8 = 0;
        for (; j + 8 <= i; j += 8) {
            if (a[j] < a[i]) ++a1;
            if (a[j + 1] < a[i]) ++a2;
            if (a[j + 2] < a[i]) ++a3;
            if (a[j + 3] < a[i]) ++a4;
            if (a[j + 4] < a[i]) ++a5;
            if (a[j + 5] < a[i]) ++a6;
            if (a[j + 6] < a[i]) ++a7;
            if (a[j + 7] < a[i]) ++a8;
        }
        ll k = i - j;
//      cout << "!" << j << " " << k << endl;
        switch (k) {
            case 0: break;
            case 1: 
                if (a[j] < a[i]) ++a1;
                break;
            case 2: 
                if (a[j] < a[i]) ++a1;
                if (a[j + 1] < a[i]) ++a2;
                break;
            case 3: 
                if (a[j] < a[i]) ++a1;
                if (a[j + 1] < a[i]) ++a2;
                if (a[j + 2] < a[i]) ++a3;
                break;
            case 4: 
                if (a[j] < a[i]) ++a1;
                if (a[j + 1] < a[i]) ++a1;
                if (a[j + 2] < a[i]) ++a2;
                if (a[j + 3] < a[i]) ++a3;
                break;
            case 5: 
                if (a[j] < a[i]) ++a1;
                if (a[j + 1] < a[i]) ++a1;
                if (a[j + 2] < a[i]) ++a2;
                if (a[j + 3] < a[i]) ++a3;
                if (a[j + 4] < a[i]) ++a4;
                break;
            case 6: 
                if (a[j] < a[i]) ++a1;
                if (a[j + 1] < a[i]) ++a2;
                if (a[j + 2] < a[i]) ++a3;
                if (a[j + 3] < a[i]) ++a4;
                if (a[j + 4] < a[i]) ++a5;
                if (a[j + 5] < a[i]) ++a6;
                break;
            case 7: 
                if (a[j] < a[i]) ++a1;
                if (a[j + 1] < a[i]) ++a1;
                if (a[j + 2] < a[i]) ++a2;
                if (a[j + 3] < a[i]) ++a3;
                if (a[j + 4] < a[i]) ++a4;
                if (a[j + 5] < a[i]) ++a5;
                if (a[j + 6] < a[i]) ++a6;
                break;
        }
        sum[i] += a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8;
//      for(R int j=1;j<i;j++)
//          if(a[j]<a[i]) sum[i]++;
    }
    for(R int i=1;i<=n;i++){
        R int j = i + 1;
        R int a1 = 0, a2 = 0;
        R int a3 = 0, a4 = 0;
        R int a5 = 0, a6 = 0;
        R int a7 = 0, a8 = 0;
        for (; j + 7 <= n; j += 8) {
            if (a[j] > a[i]) ++a1;
            if (a[j + 1] > a[i]) ++a2;
            if (a[j + 2] > a[i]) ++a3;
            if (a[j + 3] > a[i]) ++a4;
            if (a[j + 4] > a[i]) ++a5;
            if (a[j + 5] > a[i]) ++a6;
            if (a[j + 6] > a[i]) ++a7;
            if (a[j + 7] > a[i]) ++a8;
        }
        ll k = n - j + 1;
//      cout << "!" << j << " " << k << endl;
        switch (k) {
            case 0: break;
            case 1: 
                if (a[j] > a[i]) ++a1;
                break;
            case 2: 
                if (a[j] > a[i]) ++a1;
                if (a[j + 1] > a[i]) ++a2;
                break;
            case 3: 
                if (a[j] > a[i]) ++a1;
                if (a[j + 1] > a[i]) ++a2;
                if (a[j + 2] > a[i]) ++a3;
                break;
            case 4: 
                if (a[j] > a[i]) ++a1;
                if (a[j + 1] > a[i]) ++a1;
                if (a[j + 2] > a[i]) ++a2;
                if (a[j + 3] > a[i]) ++a3;
                break;
            case 5: 
                if (a[j] > a[i]) ++a1;
                if (a[j + 1] > a[i]) ++a1;
                if (a[j + 2] > a[i]) ++a2;
                if (a[j + 3] > a[i]) ++a3;
                if (a[j + 4] > a[i]) ++a4;
                break;
            case 6: 
                if (a[j] > a[i]) ++a1;
                if (a[j + 1] > a[i]) ++a2;
                if (a[j + 2] > a[i]) ++a3;
                if (a[j + 3] > a[i]) ++a4;
                if (a[j + 4] > a[i]) ++a5;
                if (a[j + 5] > a[i]) ++a6;
                break;
            case 7: 
                if (a[j] > a[i]) ++a1;
                if (a[j + 1] > a[i]) ++a1;
                if (a[j + 2] > a[i]) ++a2;
                if (a[j + 3] > a[i]) ++a3;
                if (a[j + 4] > a[i]) ++a4;
                if (a[j + 5] > a[i]) ++a5;
                if (a[j + 6] > a[i]) ++a6;
                break;
        }
        sum2[i] += a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8;
//      for(R int j=i+1;j<=n;j++)
//          if(a[j]>a[i]) sum2[i]++;
    }
    for(R int i=1;i<=n;i++)
        ans+=sum[i]*sum2[i];
    return write (ans), 0;
}

/*
11
1 2 3 4 5 6 7 8 9 10 11
*/