线段树求助

为什么权值线段树能A，加个离散化就wa了？

Ac:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll; 
const int N=1e7+2,inf=1e9+5;
//#define int long long 
inline int read()
{
    char ch; int f=1,s=0; ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0' && ch<='9'){s=s*10+ch-'0'; ch=getchar();}
    return s*f;
}
int root,a[N],sum[N],n,cnt,ls[N],rs[N],c[N];
ll ans;
void add(int &k,int l,int r,int x)
{
    //cout<<1;
    if(!k) k=++cnt;
    if(l==r)
    {
        sum[k]++;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) add(ls[k],l,mid,x);
    else add(rs[k],mid+1,r,x);
    sum[k]=sum[ls[k]]+sum[rs[k]];
} 
struct node{
    int x,id;
}p[N];
int cmp(node x,node y)
{
    return x.x<y.x;
}
ll ask(int k,int l,int r,int x,int y)
{
    //cout<<2;
    ll res=0;
    if(l>=x && r<=y)
    {
        return sum[k];
    }
    int mid=(l+r)>>1;
    if(x<=mid) res+=ask(ls[k],l,mid,x,y);
    if(y>mid) res+=ask(rs[k],mid+1,r,x,y);
    //res+=ask(ls[k],l,mid,x,mid)+ask(rs[k],mid+1,r,mid+1,y);
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        /*p[i].x=read();
        p[i].id=i;*/
    }   
    //sort(p+1,p+1+n,cmp);
    /*for(int i=1;i<=n;++i)
    {
        c[p[i].id]=i;
    }*/
    //for(int i=1;i<=n;++i) cout<<c[i]<<" ";
    for(int i=1;i<=n;++i)
    {
        ans+=ask(1,1,inf,a[i]+1,inf);
        add(root,1,inf,a[i]);
    }
    printf("%lld",ans);
    return 0;
}   

wa:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll; 
const int N=1e7+2,inf=1e9+5;
//#define int long long 
inline int read()
{
    char ch; int f=1,s=0; ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0' && ch<='9'){s=s*10+ch-'0'; ch=getchar();}
    return s*f;
}
int root,a[N],sum[N],n,cnt,ls[N],rs[N],c[N];
ll ans;
void add(int &k,int l,int r,int x)
{
    //cout<<1;
    if(!k) k=++cnt;
    if(l==r)
    {
        sum[k]++;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) add(ls[k],l,mid,x);
    else add(rs[k],mid+1,r,x);
    sum[k]=sum[ls[k]]+sum[rs[k]];
} 
struct node{
    int x,id;
}p[N];
int cmp(node x,node y)
{
    return x.x<y.x;
}
ll ask(int k,int l,int r,int x,int y)
{
    //cout<<2;
    ll res=0;
    if(l>=x && r<=y)
    {
        return sum[k];
    }
    int mid=(l+r)>>1;
    if(x<=mid) res+=ask(ls[k],l,mid,x,y);
    if(y>mid) res+=ask(rs[k],mid+1,r,x,y);
    //res+=ask(ls[k],l,mid,x,mid)+ask(rs[k],mid+1,r,mid+1,y);
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        //scanf("%d",&a[i]);
        p[i].x=read();
        p[i].id=i;
    }   
    sort(p+1,p+1+n,cmp);
    for(int i=1;i<=n;++i)
    {
        c[p[i].id]=i;
    }
    //for(int i=1;i<=n;++i) cout<<c[i]<<" ";
    for(int i=1;i<=n;++i)
    {
        ans+=ask(1,1,inf,c[i]+1,inf);
        add(root,1,inf,c[i]);
    }
    printf("%lld",ans);
    return 0;
}