hdoj 4911 Inversion 樹狀數組+離散化

hdoj 4911 Inversion 樹狀數組+離散化

題意：給你n個可以重復的無序數列，問經過k次相鄰交換後最少還有多少對逆序數

求逆序對可以用樹狀數組來做，對於重復的元素，可能在sort的時候交換編號

求和的時候要注意去重，還有一種方法就是穩定排序stable_sort

#include
#include
#include
using namespace std;
#define ll __int64
#define N 100000+10
struct ln{
        int id,va;
}in[N];
int a[N],c[N];
int n;
int cmp(ln x,ln y)
{
        return x.va=1;i-=lowbit(i))
                temp+=c[i];
        return temp;
}
int main()
{
        int k;
        while(scanf("%d%d",&n,&k)!=EOF)
        {
                for(int i=1;i<=n;i++)
                {
                        scanf("%d",&in[i].va);
                        in[i].id=i;
                }
                memset(c,0,sizeof(c));
                sort(in+1,in+n+1,cmp);
                a[in[1].id]=1;
                for(int i=2;i<=n;i++)
                {
                        if(in[i].va!=in[i-1].va)
                        a[in[i].id]=i;
                        else
                        a[in[i].id]=a[in[i-1].id];

                }
                ll ans=0;
                for(int i=1;i<=n;i++)
                {
                   updata(a[i],1);
                   printf("%d %d\n",getSum(a[i]),getSum(a[i]-1));
                   int temp=i-getSum(a[i]-1);
                   temp=temp-(getSum(a[i])-getSum(a[i]-1));
                   ans+=temp;
                }
                if(ans-k<0) printf("0\n");
                else
                printf("%I64d\n",ans-k);

        }
        return 0;
}

#include
#include
#include
using namespace std;
#define ll __int64
#define N 100000+10
struct ln{
        int id,va;
}in[N];
int a[N],c[N];
int n;
int cmp(ln x,ln y)
{
        return x.va=1;i-=lowbit(i))
                temp+=c[i];
        return temp;
}
int main()
{
        int k;
        while(scanf("%d%d",&n,&k)!=EOF)
        {
                for(int i=1;i<=n;i++)
                {
                        scanf("%d",&in[i].va);
                        in[i].id=i;
                }
                memset(c,0,sizeof(c));
                stable_sort(in+1,in+n+1,cmp);
                for(int i=1;i<=n;i++)
                        a[in[i].id]=i;
                ll ans=0;
                for(int i=1;i<=n;i++)
                {
                   updata(a[i],1);

                   int temp=i-getSum(a[i]);

                   ans+=temp;
                }
                if(ans-k<0) printf("0\n");
                else
                printf("%I64d\n",ans-k);

        }
        return 0;
}