洛谷P1966

NOIP2013 提高组 火柴排队

尝试CCF老题。果然我已经老了，快排调试半小时。

#include <cstdio>
using namespace std;
const int Mod=1e8-3;
struct Num
{
    int num,id;
    bool operator < (const Num A) const {
        return this->num < A.num;
    }
    bool operator > (const Num A) const {
        return this->num > A.num;
    }
} a[100005];

void sort(Num *L,Num *R) 
{
    if (L+1>=R) return;
    Num *ptl=L, *ptr=R-1, key=*L; ///我靠  这里key指针指向地址，所以当ptl被改变的时候，key也变了。
    while (ptl<ptr) 
    {
        while (ptl<ptr && *ptr>key) ptr--;
        if (ptl<ptr) *ptl=*ptr, ptl++;
        while (ptl<ptr && *ptl<key) ptl++;
        if (ptl<ptr) *ptr=*ptl, ptr--;  //这里一定要加if 不然会出现左右交叉的情况
    }
    *ptr=key;
    sort(L,ptr), sort(ptr+1,R);
}

int n;
class BIT 
{
    private:
        int a[100005];
    public:
        void add(int x,int value)
        {
            for (;x<=n;x+=x&(-x)) a[x]+=value;
        }
        int ask(int x)
        {
            int ret=0;
            for (;x;x-=x&(-x)) ret+=a[x];
            return ret;
        }
}T;

int pos[100005],c[100004],d[100005],ans;

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i].num), a[i].id=i;
    sort(a+1,a+n+1);
    for (int i=1;i<=n;i++) pos[i]=a[i].id;  //b[a[i].id]=i; // Map
    // 第i大的数应该在第id个位置
    // for (int i=1;i<=n;i++) pos[b[i]] = i;
    // for (int i=1;i<=n;i++) printf("%d ",a[i].num); puts("");

    for (int i=1;i<=n;i++) scanf("%d",&a[i].num), a[i].id=i;
    sort(a+1,a+n+1);
    for (int i=1;i<=n;i++) c[a[i].id]=i; //id号位的映射为第i大

    for (int i=1;i<=n;i++) d[i]=pos[c[i]];

    // for(int i=1;i<=n;i++) printf("%d ",d[i]); puts("");
    for (int i=n;i>=1;i--)
    {
        (ans+=T.ask(d[i]))%=Mod;
        T.add(d[i],1);
    }
    printf("%d\n",ans);
    return 0;
}