Участник:Rimon/Boba Inversion

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/submit/BOBAINV/

C++ (gcc 8.3)

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int X=0; bool flag=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
    if(flag) return X;
    return ~(X-1);
}
int a[10000];
int ans[5020][5020];
int main()
{
    int n;
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    for(int i=1;i<=n;i++)
    {
            ans[1][i] +=ans[1][i-1];
            for(int j=1;j<i;j++)
            {
                if(a[i]<a[j])
                {
                    ans[1][i]++;
                }
            }
 
    }
    for(int i=2;i<=n;i++)
    {
        int tmp=0;
        for(int j=i;j<=n;j++)
        {
            if(a[j]<a[i-1])
            {
                tmp++;
            }
            ans[i][j]=ans[i-1][j]-tmp;
        }
    }
    int m;
    scanf("%d",&m);
    while(m--)
    {
        int l,r;
        l=read();
        r=read(); 
        printf("%d\n",ans[l][r]);
    } 
}