LG6168 [NOI Online #1 提高组] 冒泡排序
这个日好像不难，首先我们可以手算几组冒泡，我们可以发现一个特别的性质。
我们定义 \(c_i\)，满足：
\[c_i=\sum\limits_{j=1}^{i-1} [a_j>a_i]
\]
我们会发现，每进行一次冒泡，每个 \(c_i\) 都会减一，除非 \(c_i\) 已经等于 \(0\) 了。为什么呢？我们从冒泡排序的本质出发，每一轮对于 \([1,r]\) 这一个区间，是把这个区间内最大的数移到了最后一个位置。假设这个最大的数位置为 \(x\)。那么 \([x,r]\) 区间内每个 \(c_i\) 减小 \(1\) 很好理解。那么对于 \([1,x]\) 呢？那不是和 \([1,r]\) 一样的吗？所以递归证明即可。
有了这个性质，我们有：
\[ans=\sum\limits_{i=1}^n \max(0,c_i-k)
\]
我们用权值线段树可以求出 \(c_i\)，清空后，还可以再次也可以再次用于快速求出 \(ans\)。就不想用树状数组哼！
时间复杂度 \(O(n\log n+m\log n)\)
//Don't act like a loser.
//This code is written by huayucaiji
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
//#pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
//#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read() {
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
const int MAXN=2e5+10;
int n,m;
int a[MAXN],c[MAXN];
struct seg_tree {
int sum,num;
}s[MAXN<<2];
void modify(int l,int r,int p,int x,int val) {
if(r<x||x<l) {
return ;
}
if(l==r) {
s[p].num+=val;
s[p].sum+=val*l;
return ;
}
int mid=(l+r)>>1;
modify(l,mid,p<<1,x,val);
modify(mid+1,r,p<<1|1,x,val);
s[p].sum=s[p<<1].sum+s[p<<1|1].sum;
s[p].num=s[p<<1].num+s[p<<1|1].num;
}
int query_num(int l,int r,int p,int x,int y) {
if(r<x||y<l) {
return 0;
}
if(x<=l&&r<=y) {
return s[p].num;
}
int mid=(l+r)>>1;
return query_num(l,mid,p<<1,x,y)+query_num(mid+1,r,p<<1|1,x,y);
}
int query_sum(int l,int r,int p,int x,int y) {
if(r<x||y<l) {
return 0;
}
if(x<=l&&r<=y) {
return s[p].sum;
}
int mid=(l+r)>>1;
return query_sum(l,mid,p<<1,x,y)+query_sum(mid+1,r,p<<1|1,x,y);
}
signed main() {
cin>>n>>m;
for(int i=1;i<=n;i++) {
cin>>a[i];
c[i]=query_num(1,n,1,a[i]+1,n);
modify(1,n,1,a[i],1);
}
memset(s,0,sizeof s);
for(int i=1;i<=n;i++) {
modify(1,n,1,c[i],1);
}
while(m--) {
int opt,x;
opt=read(),x=read();
if(opt==1) {
modify(1,n,1,c[x],-1);
modify(1,n,1,c[x+1],-1);
if(a[x]>a[x+1]) {
swap(c[x],c[x+1]);
swap(a[x],a[x+1]);
c[x]--;
}
else {
swap(c[x],c[x+1]);
swap(a[x],a[x+1]);
c[x+1]++;
}
modify(1,n,1,c[x],1);
modify(1,n,1,c[x+1],1);
}
else {
printf("%lld\n",query_sum(1,n,1,x+1,n)-x*query_num(1,n,1,x+1,n));
}
}
return 0;
}