题目描述

逝者如斯夫,不舍昼夜!

叶良辰认为,他的寿命是无限长的,而且每天都会进步。

叶良辰的生命的第一天,他有1点能力值。第二天,有2点。第n天,就有n点。也就是S[i]=i

但是调皮的小A使用时光机,告诉他第x天和第y天,就可以任意交换某两天的能力值。即S[x]<–>S[y]

小A玩啊玩,终于玩腻了。

叶良辰:小A你给我等着,我有100种办法让你生不如死。除非能在1秒钟之内告知有多少对“异常对”。也就是说,最后的能力值序列,有多少对的两天x,y,其中x<y,但是能力值S[x]>S[y]?

小A:我好怕怕啊。

于是找到了你。

对于30%的数据,x_i,y_i <= 2000

对于70%的数据, x_i,y_i <= 100000

对于100%的数据, x_i.y_i <= 2^31-1 k<=100000

逆序对裸题

由于xy这么大我们来离散化

把只要是交换过的(不管几次)都标记下来,排下序(点权为1)

没交换过的一些区间缩成一个点(点权为区间长度)

然后进行离散化操作,离散成新的段,相邻两点间下标严格递增1(还有一个就是开头没被交换的区间对答案没有影响直接扔掉)

我们离线了交换操作,这个时候就二分查找,把原来应该换哪两个点映射成现在应该换哪两个点

全换完之后就是个裸的逆序对问题,按点权建树状数组,然后统计区间和就行了。

·

//注释是做题的时候瞎写的凑合着看看吧,要说的都说了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<algorithm>
#include<cstdlib>
#define inf 1e18
using namespace std;

struct ch
{
    long long ca,cb;
}oprates[100010]={0};
long long changep[200010]={0};//被操作的区间 
long long setx[200010]={0};//离散化映射 
int k,totlen=0,upat=2;


int final[400010]={0},zonecount[200010]={0};
long long fwt[400010]={0};

inline void uniq()
{
    int old_len=totlen;	
    for (int i=1;i<=old_len;i++) if (changep[i]==changep[i+1]) 
    {
        changep[i]=inf;
        totlen--;
    }
    sort(changep+1,changep+old_len+1);
    
//	for (int i=1;i<=totlen;i++) printf("%lld ",changep[i]); printf("\n");
}
inline void makeset()
{
    fill(zonecount,zonecount+200000,1);
    setx[1]=changep[1];//一定以第一个被交换的位置开始算 
    for (int i=2;i<=totlen;i++)
    {
        if (changep[i]!=changep[i-1]+1)//有一段正常的区间 
        {
            zonecount[upat]=changep[i]-changep[i-1]-1;
            setx[upat]=changep[i-1]+1;
            upat++;
            setx[upat]=changep[i];
            upat++;
        }
        else//相邻的两个元素都交换了 
        {
            setx[upat]=changep[i];
            upat++;
        }
    }
    upat--;
    
//	for (int i=1;i<=upat;i++) printf("%lld ",setx[i]); printf("\n");
}
inline int BinSearch(long long element)
{
    int l=1,r=upat,mid;
    while (l<=r)
    {
        mid=(l+r)>>1;
        if (setx[mid]==element) return mid;
        else if (setx[mid]>element) r=mid-1;
        else l=mid+1;
    }
}

long long getsum(long long pos)
{
    long long res=0;
    while (pos)
    {
        res+=fwt[pos];
        pos-=(pos&(-pos));
    }
    return res;
}

inline void add(long long pos,long long val)
{
    while (pos<=upat)
    {
        fwt[pos]+=val;
        pos+=(pos&(-pos));
    }
}

int main()
{
    scanf("%d",&k);
    for (int i=1;i<=k;i++)
    {
        scanf("%lld%lld",&oprates[i].ca,&oprates[i].cb);
        changep[++totlen]=oprates[i].ca; changep[++totlen]=oprates[i].cb;
    }
    //离散化 
    sort(changep+1,changep+totlen+1);
    uniq();
    makeset();
    
    for (int i=1;i<=upat;i++) final[i]=i;
    for (int i=1;i<=k;i++) 
    {
        int posa=BinSearch(oprates[i].ca),posb=BinSearch(oprates[i].cb);
        swap(final[posa],final[posb]);
        swap(zonecount[posa],zonecount[posb]);
    }
    
//	for (int i=1;i<=upat;i++) printf("%lld ",final[i]); printf("\n");
//	for (int i=1;i<=upat;i++) printf("%lld ",zonecount[i]); printf("\n");
    
    unsigned long long ans=0;
    for (int i=1;i<=upat;i++)
    {
        ans+=zonecount[i]*(getsum(upat)-getsum(final[i]));
        add(final[i],zonecount[i]);
//		cout<<ans<<endl;
    }
    
    printf("%lld\n",ans);
    return 0;
}
分类:

发表评论

电子邮件地址不会被公开。 必填项已用*标注