记录编号	550329	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI Online 2020 1st]冒泡排序(民间数据)	最终得分	100
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	通过
代码语言	C++	运行时间	5.858 s
提交时间	2020-03-08 18:38:08	内存使用	35.02 MiB

#include<iostream>
#include<cstdio>
#define int long long int
using namespace std;
int n,m,a1,a2,t1[800001],t2[800001],t3[800001],v[200001],b[200001];
int ls(int x)
{
	return x<<1;
}
int rs(int x)
{
	return x<<1|1;
}
void pushup1(int x)
{
	t1[x]=t1[ls(x)]+t1[rs(x)];
}
void pushup2(int x)
{
	t2[x]=t2[ls(x)]+t2[rs(x)];
}
void pushup3(int x)
{
	t3[x]=t3[ls(x)]+t3[rs(x)];
}
void T1ADD(int x,int l,int r,int p)
{
	if(l==r)
	{
		t1[x]++;
		return;
	}
	int mid=(l+r)>>1;
	if(p<=mid)
		T1ADD(ls(x),l,mid,p);
	else
		T1ADD(rs(x),mid+1,r,p);
	pushup1(x);
} 
int Query1(int x,int l,int r,int nl,int nr)
{
	if(nl<=l&&nr>=r)
	{
		return t1[x];
	}
	int mid=(l+r)>>1,res=0;
	if(nl<=mid)
		res+=Query1(ls(x),l,mid,nl,nr);
	if(nr>mid)
	{
		res+=Query1(rs(x),mid+1,r,nl,nr);
	}
	return res;
}
void Change2(int x,int l,int r,int p,int Val)
{
	if(l==r)
	{
		t2[x]+=Val;
		return;
	}
	int mid=(l+r)>>1;
	if(p<=mid)
		Change2(ls(x),l,mid,p,Val);
	if(p>mid)
	{
		Change2(rs(x),mid+1,r,p,Val);
	}
	pushup2(x);
}
int Query2(int x,int l,int r,int nl,int nr)
{
	if(nl<=l&&nr>=r)
	{
		return t2[x]; 
	}
	int mid=(l+r)>>1,res=0;
	if(nl<=mid)
	{
		res+=Query2(ls(x),l,mid,nl,nr);
	}
	if(nr>mid)
	{
		res+=Query2(rs(x),mid+1,r,nl,nr);
	}
	return res;
}
void Change3(int x,int l,int r,int p,int Val)
{
	if(l==r)
	{
		t3[x]+=Val;
		return;
	}
	int mid=(l+r)>>1;
	if(p<=mid)
		Change3(ls(x),l,mid,p,Val);
	if(p>mid)
	{
		Change3(rs(x),mid+1,r,p,Val);
	}
	pushup3(x);
}
int Query3(int x,int l,int r,int nl,int nr)
{
	if(nl<=l&&nr>=r)
	{
		return t3[x]; 
	}
	int mid=(l+r)>>1,res=0;
	if(nl<=mid)
	{
		res+=Query3(ls(x),l,mid,nl,nr);
	}
	if(nr>mid)
	{
		res+=Query3(rs(x),mid+1,r,nl,nr);
	}
	return res;
}
signed main()
{
	freopen("noi_online2020_bubble.in","r",stdin);
	freopen("noi_online2020_bubble.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&v[i]);
		b[i]=(i-1)-Query1(1,1,n,1,v[i]);//查询出已出现比v[i]小的数个数 
		T1ADD(1,1,n,v[i]); 
		Change2(1,1,n,b[i]+1,b[i]);//避开b[i]为0的情况 
		Change3(1,1,n,b[i]+1,1);//避开b[i]为0的情况 
	}
	/*
	主体思想为构造两颗权值线段树
	t2:保存权值在l到r之间的b[i]的和
	t3:保存权值在l到r之间的b[i]的个数 
	*/
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld",&a1,&a2);
		if(a1==1)
		{
			if(v[a2]>v[a2+1])
			{
				Change2(1,1,n,b[a2+1]+1,-b[a2+1]);
				Change3(1,1,n,b[a2+1]+1,-1);
				b[a2+1]--;
				Change2(1,1,n,b[a2+1]+1,b[a2+1]);
				Change3(1,1,n,b[a2+1]+1,1);
				swap(b[a2],b[a2+1]);
				swap(v[a2],v[a2+1]); 
			}
			else
			{
				Change2(1,1,n,b[a2]+1,-b[a2]);
				Change3(1,1,n,b[a2]+1,-1);
				b[a2]++;
				Change2(1,1,n,b[a2]+1,b[a2]);
				Change3(1,1,n,b[a2]+1,1);
				swap(b[a2],b[a2+1]);
				swap(v[a2],v[a2+1]);
			}
		}
		else
		{
			if(a2>=n)
			{
				printf("%d\n",0);
			}
			else
			{
				printf("%lld\n",Query2(1,1,n,a2+1,n)-a2*(Query3(1,1,n,a2+1,n))); 
			} 
		}
	} 
	return 0;
}