[NOI Online #1 提高组] 冒泡排序
树状数组or线段树维护逆序对
手推样例得到两个结论：
- 操作1会使逆序对发生\(\pm 1\)的变化
- 操作2，每一轮冒泡排序，会使所有逆序对 $ \geq 1$ 的数组的逆序对$ -1 $
- 对于操作1，只需要算一下交换的两个数的大小，对总的逆序对的变化即可
- 但对于操作2，要算出\(\min(n - 1, k)\)轮后的逆序对数量。这里可以有进行一个前缀和的操作，用树状数组去维护，用一个桶存逆序对至少为\(x\)的数有多少个，再把它们取相反数插入到树状数组中，来实现某轮减少了多少逆序对的前缀和。
- 对于操作1，同样也要用到树状数组去维护改变的总的逆序对数量，和上文提到的某轮减少了多少逆序对的操作
对于查询第\(k\)轮和其他细节具体见代码
// AC one more times
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<long long,long long> PLL;
const int mod = 1e9+7;
const int N = 5e5+10;
template<class T>
struct BIT {
T c[N];
int size;
void resize(int s) { size = s;}
T query(int x) { // 1 ... x
assert(x <= size);
T s = 0;
for (; x; x -= x & (-x)) {
s += c[x];
}
return s;
}
void modify(int x, T s) { // a[x] += s
//assert(x != 0);
if(x==0) return;
for (; x <= size; x += x & (-x)) {
c[x] += s;
}
}
};
BIT<LL> tr;
int n,q;
LL a[N],b[N],re[N],sum=0;
LL s[N];
void solve()
{
cin>>n>>q;
tr.resize(n+2);
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=tr.query(n)-tr.query(a[i]);
sum+=b[i];
re[b[i]]++;
tr.modify(a[i],1);
}
memset(tr.c,0,sizeof tr.c);
tr.modify(1,sum);
for(int i=n-1;i>=1;i--)
s[i]=s[i+1]+re[i];
for(int i=0;i<=n-1;i++)
tr.modify(i+2,-1ll*s[i]);
while(q--)
{
int op, t;
cin>>op>>t;
if(op==2)
{
t=min(t,n);
cout<<tr.query(t+2)<<endl;
}
else if(op==1)
{
if(a[t]>a[t+1])
{
swap(b[t],b[t+1]);
tr.modify(1,-1);
tr.modify(b[t]+2,1);
b[t]--;
swap(a[t],a[t+1]);
}
else
{
swap(b[t],b[t+1]);
b[t+1]++;
tr.modify(1,1);
tr.modify(b[t+1]+2,-1);
swap(a[t],a[t+1]);
}
}
}
return;
}
int main()
{
std::ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int TC = 1;
//cin >> TC;
for(int tc = 1; tc <= TC; tc++)
{
//cout << "Case #" << tc << ": ";
solve();
}
return 0;
}