一场模拟赛

#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <vector>
using namespace std;

#define FILENAME "card"

#if (defined D)
#define DEBUG(...) printf(__VA_ARGS__)
#define PRINTARR(formatstr, arr, beginoff, size)				\
do{printf(#arr ":");											\
for (int __i = beginoff; __i <= beginoff + size - 1; __i++)		\
    printf("\t%d", __i);										\
printf("\n");													\
for (int __i = beginoff; __i <= beginoff + size - 1; __i++)		\
    printf("\t" formatstr, arr[__i]);							\
printf("\n"); }while(false)
#define PASS printf("Passing function \"%s\" on line %d\n", __func__, __LINE__)
#define ASSERT(expr) do{\
    if(!(expr)){\
        printf("Debug Assertation Failed on line %d, in function %s:\n  Expression: %s\n",__LINE__,__func__,#expr);\
        abort();\
    }\
}while(false)
#else
#define DEBUG(...)
#define PRINTARR(a, b, c, d)
#define PASS
#define ASSERT(expr)
#endif

const int bufferreadsize = 30 * 1024 * 1024;
const int bufferwritesize = 1024;
char buffer[bufferreadsize], *buffertop = buffer;
#define GETCHAR *(buffertop++)
#define UNGETCHAR(c) (--buffertop)

template<typename IntType>
inline IntType read() {
    IntType val = 0;
    int c;
    bool invflag = false;
    while (!isdigit(c = GETCHAR))
        if (c == '-')
            invflag = true;
    do {
        val = (val << 1) + (val << 3) + c - '0';
    } while (isdigit(c = GETCHAR));
    UNGETCHAR(c);
    if (invflag)
        return -val;
    else
        return val;
}
template<>
inline string read<string>() {
    string str;
    str.clear();
    int c;
    while (iscntrl(c = GETCHAR) || c == ' ' || c == '\t');
    do {
        str.push_back(c);
    } while (!(iscntrl(c = GETCHAR) || c == ' ' || c == '\t'));
    UNGETCHAR(c);
    return str;
}
template<typename IntType>
inline void read(IntType& x) { x = read<IntType>(); }

char bufferwrite[bufferwritesize], *writetop = bufferwrite;
#define PUTCHAR(c) (*(writetop++) = (c))

inline void putstr(char* str) {
    while ((*str) != '\0') {
        PUTCHAR(*str);
        str++;
    }
}

template<typename IntType>
inline void println(IntType val) {
    if (val == 0)
        PUTCHAR('0');
    if (val < 0) {
        PUTCHAR('-');
        val = -val;
    }
    char buf[16], *buftop = buf + 15;
    while (val > 0) {
        *buftop = (val % 10 + '0');
        buftop--;
        val /= 10;
    }
    for (buftop++; buftop <= buf + 15; buftop++)
        PUTCHAR(*buftop);
    PUTCHAR('\n');
}

/******************** End of quickread template ********************/

const int MaxN=100000+10;

int n,a[MaxN];
vector<int> pos[MaxN];

struct node{
    int left,right;
    node* lson,*rson;
    int sum;
};

node* root;
node mem[2*MaxN],*memtop=mem;
#define ALLOCATE (++memtop)

void build(int left=1,int right=n,node*& p=root){
    p=ALLOCATE;
    p->left=left;
    p->right=right;
    if(left==right)
        p->sum=1;
    else{
        int mid=(left+right)/2;
        build(left,mid,p->lson);
        build(mid+1,right,p->rson);
        p->sum=p->lson->sum+p->rson->sum;
    }
}

void setval(int pos,int val,node* p=root){
    if(p->left==pos&&p->right==pos){
        p->sum=val;
        return;
    }
    if(p->lson->right>=pos)
        setval(pos,val,p->lson);
    else
        setval(pos,val,p->rson);
    p->sum=p->lson->sum+p->rson->sum;
}

int query(int left,int right,node* p=root){
    if(right<left)
        return 0;
    if(p->left==left&&p->right==right)
        return p->sum;
    if(p->lson->right>=right)
        return query(left,right,p->lson);
    else if(p->rson->left<=left)
        return query(left,right,p->rson);
    else
        return (query(left,p->lson->right,p->lson)+
                query(p->rson->left,right,p->rson));
}



int main(int argc, char* argv[]) {
#if (defined LOCAL) || (defined ONLINE_JUDGE)
    FILE* in = stdin, *out = stdout;
#else
    FILE* in = fopen(FILENAME ".in", "rb");
    FILE* out = fopen(FILENAME ".out", "wb");
#endif
    fread(buffer, 1, bufferreadsize, in);
    fclose(in);

    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        pos[a[i]].push_back(i);
    }

    build();

    int ans=0;
    for(int i=1;i<=100000;i++){
        if(pos[i].empty())
            continue;
        DEBUG("a=%d has contents\n",i);
        for(int j=0;j<pos[i].size();j++)
            setval(pos[i][j],0);
        int k=query(1,n);
        for(int j=0;j<pos[i].size();j++){
            DEBUG("    a[%d]=%d",pos[i][j],i);
            int l=query(1,pos[i][j]-1),r=k-l;
            DEBUG(", l=%d, r=%d\n",l,r);
            ans+=min(l,r);
        }
    }

    println(ans);

    fwrite(bufferwrite, 1, writetop - bufferwrite, out);
    fclose(out);
    return 0;
}