题解 P1975 【[国家集训队]排队】
YoungNeal
2018-05-08 17:53:08
[安利](http://www.cnblogs.com/YoungNeal/p/9009902.html)一下博客~
看到楼下大佬都在块内排序加树状数组,蒟蒻想发表一下自己的做法。
这里有一种前缀和思想的做法。
这个思想是受[作诗](https://www.luogu.org/problemnew/show/P4135)的启发。
在那道题中,我们借用前缀和统计了每个数出现次数,这道题也完全可以嘛!
定义 $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$ 数组!
```cpp
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 20005
#define int long long
int 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;
}
```