记录编号	566228	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI Online 2020 1st]冒泡排序(民间数据)	最终得分	100
用户昵称	遥时_彼方	是否通过	通过
代码语言	C++	运行时间	1.370 s
提交时间	2021-11-04 12:54:50	内存使用	0.00 MiB

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
int nc,mc;
ll n[200005];
ll ns[200005];
ll f[200005]; 
ll p[200005];
ll ps[200005];
ll lowbit(ll x){return x&-x;}
void addf(ll x,ll d)
{
	while(x<=nc)
	{
//		cout<<x<<endl;
		f[x]+=d;
	    x+=lowbit(x);
	}
	return;
}
void addp(ll x,ll d)
{
	if(x==0) return;
	while(x<=nc)
	{
//		cout<<x<<endl;
		p[x]+=d;
	    x+=lowbit(x);
	}
	return;
}
void addps(ll x,ll d)
{
	if(x==0) return;
	while(x<=nc)
	{
//		cout<<x<<endl;
		ps[x]+=d;
	    x+=lowbit(x);
	}
	return;
}
ll czf(ll x)
{
	ll re=0;
	while(x)
	{
//		cout<<x<<endl;
		re+=f[x];
		x-=lowbit(x);
	}
	return re;
}
ll czp(ll x)
{
	ll re=0;
	while(x)
	{
		re+=p[x];
		x-=lowbit(x);
	}
	return re;
}
ll czps(ll x)
{
	ll re=0;
	while(x)
	{
		re+=ps[x];
		x-=lowbit(x);
	}
	return re;
}
int main()
{
	freopen("noi_online2020_bubble.in","r",stdin);
	freopen("noi_online2020_bubble.out","w",stdout);
    scanf("%d%d",&nc,&mc);
    ll s1,s2;
    for(int i=1;i<=nc;i++)
    {
    	scanf("%lld",&n[i]);
    	s1=i-1-czf(n[i]);
//    	cout<<s1<<":"<<s1<<endl;
    	ns[i]=s1;
    	addp(s1,s1);
    	addps(s1,1);
    	addf(n[i],1);
    }
    for(int i=1;i<=mc;i++)
    {
    	scanf("%lld%lld",&s1,&s2);
    	if(s1==1)
    	{
    		if(n[s2]<n[s2+1])
    		{
    			addp(ns[s2],-ns[s2]);
    			addps(ns[s2],-1);
    			ns[s2]++;
    			addp(ns[s2],ns[s2]);
    			addps(ns[s2],1);
    			swap(n[s2],n[s2+1]);
    			swap(ns[s2],ns[s2+1]);
    		}
    		else
    		{
    			addp(ns[s2+1],-ns[s2+1]);
    			addps(ns[s2+1],-1);
    			ns[s2+1]--;
    			addp(ns[s2+1],ns[s2+1]);
    			addps(ns[s2+1],1);
    			swap(n[s2],n[s2+1]);
    			swap(ns[s2],ns[s2+1]);
    		}
    	}
    	else
    	{
    		if(s2>=nc)
    		{
    			printf("0\n");
    			continue;
    		}
    		s1=czp(nc)-czp(s2)-s2*(czps(nc)-czps(s2));
//    		if(s1<0) s1=0;
    		printf("%lld\n",s1);
//    		cout<<"nc:"<<czp(nc)<<endl;
//    		cout<<"s2:"<<czp(s2)<<endl;
    	}
    }
	return 0;
}