复杂度: O(n^2).

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5010;
int a[maxn];

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    long long res = 0;
    for (int i = 1; i <= n; i++) {
        long long sum1 = 0, sum2 = 0;
        for (int j = 1; j < i; j++) {
            sum1 += (a[j] < a[i]);
        }
        for (int j = i + 1; j <= n; j++) {
            sum2 += (a[i] < a[j]);
        }
        res += sum1 * sum2;
    }
    cout << res << endl;
    return 0;
}

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;

namespace dts
{
    typedef long long ll;
    
    ll n,a[1<<13];
    
    void main()
    {
        scanf("%lld",&n);
        for (ll i=0;i<n;i++)
            scanf("%lld",&a[i]);
        ll ans=0;
        for (ll i=0;i<n;i++)
        {
            ll cntl=0,cntr=0;
            for (ll j=0;j<i;j++)
                if (a[j]<a[i])
                    cntl++;
            for (ll j=i;j<n;j++)
                if (a[i]<a[j])
                    cntr++;
            ans+=cntl*cntr;
        }
        printf("%lld\n",ans);
    }
};

int main()
{
    dts::main();
}

千万注意最终结果要开longlong....

program p1768;
var
a:array[1..5000]of longint;
b,c,i,j,n:longint;
ans:int64;
begin
readln(n);
for i:=1 to n do read(a[i]);
for i:=2 to n-1 do begin
b:=0;c:=0;
for j:=1 to i-1 do if a[j]<a[i] then inc(b);
for j:=i+1 to n do if a[j]>a[i] then inc(c);
ans:=ans+b*c;
end;
writeln(ans);
end.
呵呵

暴力主席树：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int i,j,k,n,m,s,t;
ll ans;
int root[5005];
struct node
{
int lson,rson,sum;
} tree[5005*20];
int a[100005];
int b[100005];
int tot,num,cnt;
void change(int l,int r,int &p,int x)
{
tree[++cnt] = tree[p];
p = cnt;
tree[p].sum++;
if (l==r) return;
int mid = (l+r)>>1;
if (mid>=x) change(l,mid,tree[p].lson,x);
else change(mid+1,r,tree[p].rson,x);
}
ll ask(int X,int Y,int l,int r,int x,int y)
{
if (l==x&&y==r) return tree[Y].sum-tree[X].sum;
int mid = (l+r)>>1;
if (mid>=y) return ask(tree[X].lson,tree[Y].lson,l,mid,x,y);
else if (mid+1<=x) return ask(tree[X].rson,tree[Y].rson,mid+1,r,x,y);
else return ask(tree[X].lson,tree[Y].lson,l,mid,x,mid)+ask(tree[X].rson,tree[Y].rson,mid+1,r,mid+1,y);
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[++tot] = a[i];
}
sort(b+1,b+1+n);
tot = unique(b+1,b+1+n)-b-1;
for (int i=1;i<=n;i++) a[i] = lower_bound(b+1,b+1+n,a[i])-b;
for (int i=1;i<=n;i++)
{
root[i] = root[i-1];
change(1,tot,root[i],a[i]);
}
for (int i=1;i<n;i++)
for (int j=i+1;j<=n;j++)
if (a[i]+1<=a[j]-1) ans += ask(root[i-1],root[j],1,tot,a[i]+1,a[j]-1);
cout<<ans<<endl;
return 0;
}

P1768顺序对的值
Accepted

记录信息

评测状态 Accepted
题目 P1768 顺序对的值
递交时间 2014-12-06 11:09:23
代码语言 C++
评测机 VijosEx
消耗时间 2836 ms
消耗内存 98228 KiB
评测时间 2014-12-06 11:09:28

评测结果

编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 98220 KiB, score = 10

测试数据 #1: Accepted, time = 156 ms, mem = 98220 KiB, score = 10

测试数据 #2: Accepted, time = 234 ms, mem = 98228 KiB, score = 10

测试数据 #3: Accepted, time = 327 ms, mem = 98228 KiB, score = 10

测试数据 #4: Accepted, time = 312 ms, mem = 98228 KiB, score = 10

测试数据 #5: Accepted, time = 405 ms, mem = 98228 KiB, score = 10

测试数据 #6: Accepted, time = 374 ms, mem = 98228 KiB, score = 10

测试数据 #7: Accepted, time = 374 ms, mem = 98224 KiB, score = 10

测试数据 #8: Accepted, time = 343 ms, mem = 98228 KiB, score = 10

测试数据 #9: Accepted, time = 296 ms, mem = 98228 KiB, score = 10

Accepted, time = 2836 ms, mem = 98228 KiB, score = 100

代码

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>

using namespace std;

int n;
int i , j;
int a[5000 + 2];
int f[5000 + 2][5000 + 2];
unsigned long long ans;

int glc( int t[] , int l , int r )
{
return t[r] - t[l];
}

int main()
{
ans = 0;
scanf( "%d" , &n );
for( i = 0 ; i < n ; i++ )
scanf( "%d" , &a[i] );
for( i = 0 ; i < n ; i++ )
{
f[i][0] = ( a[0] < a[i] );
for( j = 1 ; j < n ; j++ )
f[i][j] = f[i][j - 1] + ( a[j] < a[i] );

}
for( i = 0 ; i < n ; i++ )
for( j = i + 1 ; j < n ; j++ )
if( a[j] > a[i] )
ans += glc( f[j] , i , j ) - glc( f[i] , i - 1 , j );
cout << ans << endl;
return 0;
}

楼下的算法
差不多
我好像是45ms
就是树状数组求比一个数大的数的个数时要先倒过来再求
还有要用long long
C++scanf/printf的格式符让我悲剧了

编译通过...

├ 测试数据 01：答案正确... (0ms, 912KB)

├ 测试数据 02：答案正确... (0ms, 912KB)

├ 测试数据 03：答案正确... (15ms, 912KB)

├ 测试数据 04：答案正确... (0ms, 912KB)

├ 测试数据 05：答案正确... (0ms, 912KB)

├ 测试数据 06：答案正确... (15ms, 912KB)

├ 测试数据 07：答案正确... (15ms, 912KB)

├ 测试数据 08：答案正确... (15ms, 912KB)

├ 测试数据 09：答案正确... (15ms, 912KB)

├ 测试数据 10：答案正确... (15ms, 912KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 93ms / 912KB

时间复杂度可以降到NlgN

首先是n^2的算法，

对于每个val[i]

获得左边比他小的数记为sum1[i]

右边比他大的数记为sum2[i]

那么对于他来说，所能造成的影响就是sum1[i] * sum2[i]

降到lgN则是把求sum1和sum2的用树状数组优化。

编译通过...

├ 测试数据 01：答案正确... (78ms, 98176KB)

├ 测试数据 02：答案正确... (219ms, 98172KB)

├ 测试数据 03：答案正确... (390ms, 98176KB)

├ 测试数据 04：答案正确... (421ms, 98168KB)

├ 测试数据 05：答案正确... (453ms, 98172KB)

├ 测试数据 06：答案正确... (593ms, 98168KB)

├ 测试数据 07：答案正确... (562ms, 98172KB)

├ 测试数据 08：答案正确... (577ms, 98176KB)

├ 测试数据 09：答案正确... (577ms, 98168KB)

├ 测试数据 10：答案正确... (453ms, 98172KB)

预处理：b[i][j]表示a[1] ... a[j]中比a[i]小的数的数量。

设

int get_lower_count(int b[], int l, int r)

{

return b[r] - b[l - 1];

}

枚举左端点i，右端点j，则 get_lower_count(b[j], i + 1, j) - get_lower_count(b[i], i, j)为a[i]...a[j]的“顺序对的值”。因为a...a[j-1]中的值只有3种情况，要么比a[j]大，要么在a[i]与a[j]之间，要么比a[i]小。比a[i]小的数，必然比a[j]小。所以用比a[j]小的数剪掉比a[i]小的数即可。

另外累加时需要用long long

时空复杂度均为n^2

#include<iostream>
using namespace std;

int a[5005];
int n;
long long sum = 0;
int main(){
//freopen("test.txt", "r", stdin);
cin>>n;
int i, j;
for(i = 1; i <= n; ++i){
cin>>a[i];
}
int p,q;
for(i = 1; i < n; ++i){
p = 0;
for(j = 1; j < i; ++j){
if(a[j] < a[i]){
++p;
}
}
if(p == 0){
continue;
}
q = 0;
for(j = i + 1; j <=n; ++j){
if(a[j] > a[i]){
++q;
}
}
sum += p*q;
}
cout<<sum;
return 0;
}