[国家集训队] 排队-阿南达文事网

[国家集训队] 排队

Luogu

Description

排排坐，吃果果，生果甜嗦嗦，大家笑呵呵。你一个，我一个，大的分给你，小的留给我，吃完果果唱支歌，大家乐和和。
红星幼儿园的小朋友们排起了长长地队伍，准备吃果果。不过因为小朋友们的身高有所区别，排成的队伍高低错乱，极不美观。设第i个小朋友的身高为hi，我们定义一个序列的杂乱程度为:
满足 \(i<j\) 且 \(h_i>h_j\) 的 \((i,j)\) 数量。

幼儿园阿姨每次会选出两个小朋友，交换他们的位置，请你帮忙计算出每次交换后，序列的杂乱程度。为方便幼儿园阿姨统计，在未进行任何交换操作时，你也应该输出该序列的杂乱程度。

Input

第一行为一个正整数n，表示小朋友的数量；
第二行包含n个由空格分隔的正整数h1,h2,…,hn，依次表示初始队列中小朋友的身高；
第三行为一个正整数m，表示交换操作的次数；
以下m行每行包含两个正整数ai和bi，表示交换位置ai与位置bi的小朋友。

Output

输出文件共m+1行，第i行一个正整数表示交换操作i结束后，序列的杂乱程度。

Range

对于100%的数据，\(1\leq m\leq 2\times 10^3,1\leq n\leq 2\times 10^4,1\leq h_i\leq 10^9,a_i\ne b_i,1\leq a_i,b_i\leq n\)。

Solution

这里有一种前缀和思想的做法。
这个思想是受作诗的启发。
在那道题中，我们借用前缀和统计了每个数出现次数，这道题也完全可以嘛！
定义 \(sum[i][j]\) 表示第 \(1-i\) 个块，身高为 \(j\) 的小孩出现的次数。
所有身高先离散化一遍之后，没有任何操作的答案先树状数组求一下。
然后就可以借助以前的答案更新当前了，这个楼下大佬讲了就不啰嗦了。
对于交换 \([l,r]\)，边角暴力，块内统计答案。
如何统计呢？由楼下大佬的公式我们可以知道，如果 \(a[i]<val[l]\)，那么 \(ans++\)。这是将 \(i\) 从 \(belong[l]+1\) 到 \(belong[r]-1\) 循环。
换个思路，如果 \(i\) 代表的不是元素，而是数值呢？
也就是说，将 \(i\) 从1到值域循环，那么如果 \(i<val[l]\)，那么 \(ans\) 就会变大。
变大多少呢？这个值即为 \(sum[belong[r]-1][i]-sum[belong[l]][i]\)。
其他三种情况同理，那么每次答案就求完了。
记得更新 \(sum\) 数组！

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 20005
#define int long longint f[N],len;
int n,m,tot,ans;
int sum[150][N];
int val[N],t[N];
int l[150],r[150];
int block,belong[N];int ask(int x){int b=0;for(;x;x-=x&-x)b+=f[x];return b;
}void add(int x){for(;x<=n;x+=x&-x)f[x]++;
}int query(int a,int b){//printf("a=%lld,b=%lld\n",a,b);if(val[a]==val[b]) return ans;if(belong[a]==belong[b] or belong[a]+1==belong[b]){//puts("dfgfhhg");for(int i=a+1;i<b;i++){if(val[i]<val[a]) ans--;if(val[i]<val[b]) ans++;if(val[i]>val[a]) ans++;if(val[i]>val[b]) ans--;//printf("i=%lld,val=%lld,ans=%lld\n",i,val[i],ans);}if(val[a]>val[b]) ans--;if(val[a]<val[b]) ans++;if(belong[a]+1==belong[b])sum[belong[a]][val[a]]--,sum[belong[a]][val[b]]++;val[a]^=val[b]^=val[a]^=val[b];return ans;}if(val[a]>val[b]) ans--;if(val[a]<val[b]) ans++;for(int i=a+1;i<=r[belong[a]];i++){if(val[i]<val[a]) ans--;if(val[i]<val[b]) ans++;if(val[i]>val[a]) ans++;if(val[i]>val[b]) ans--;}for(int i=b-1;i>=l[belong[b]];i--){if(val[i]<val[a]) ans--;if(val[i]<val[b]) ans++;if(val[i]>val[a]) ans++;if(val[i]>val[b]) ans--;}for(int i=1;i<=len;i++){if(i<val[a]) ans-=sum[belong[b]-1][i]-sum[belong[a]][i];if(i<val[b]) ans+=sum[belong[b]-1][i]-sum[belong[a]][i];if(i>val[a]) ans+=sum[belong[b]-1][i]-sum[belong[a]][i];if(i>val[b]) ans-=sum[belong[b]-1][i]-sum[belong[a]][i];}for(int i=belong[a];i<belong[b];i++){sum[i][val[a]]--;sum[i][val[b]]++;}val[a]^=val[b]^=val[a]^=val[b];/*for(int i=1;i<=tot;i++){for(int j=1;j<=len;j++)printf("i=%lld,j=%lld,sum=%lld\n",i,j,sum[i][j]);}*/return ans;
}void file(){freopen("in.txt","r",stdin);freopen("out2.txt","w",stdout);
}signed main(){//file();scanf("%lld",&n);block=sqrt(n);tot=n/block;if(n%block) tot++;for(int i=1;i<=n;i++)scanf("%lld",&val[i]),t[i]=val[i],belong[i]=(i-1)/block+1;std::sort(t+1,t+1+n);len=std::unique(t+1,t+1+n)-t-1;for(int i=1;i<=n;i++) val[i]=std::lower_bound(t+1,t+1+len,val[i])-t;for(int i=1;i<=tot;i++)l[i]=(i-1)*block+1,r[i]=i*block;for(int i=n;i;i--){ans+=ask(val[i]-1);add(val[i]);sum[belong[i]][val[i]]++;}for(int i=1;i<=tot;i++){for(int j=1;j<=len;j++)sum[i][j]+=sum[i-1][j];}scanf("%lld",&m);printf("%lld\n",ans);while(m--){int x,y;scanf("%lld%lld",&x,&y);if(x>y) x^=y^=x^=y;printf("%lld\n",query(x,y));}return 0;
}

转载于:.html