题解 P1975 【[国家集训队]排队】

YoungNeal

2018-05-08 17:53:08

Solution

[安利](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; } ```