不会卡常求助！

或者算法复杂度对不对。

在排队（P1975）过了。

#include <iostream>
#include <cmath>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int size=(1<<20)+1;
char buf[size],*p1=buf,*p2=buf;
char buffer[size];
int op1=-1;
const int op2=size-1;
inline char readchar() {
	if(p1!=p2) {
		return *p1++;
	}
	return p1==(p2=(p1=buf)+fread(buf,1,size-1,stdin))?EOF:*p1++;
}
inline void flush() {
	fwrite(buffer,1,op1+1,stdout),op1=-1;
}
inline void writechar(const char &x) {
	if(op1==op2) flush();
	buffer[++op1]=x;
}
inline int read() {
	int s=1,c=readchar(),x=0;
	while(c<=32) {
		c=readchar();
	}
	if(c=='-') {
		s=-1,c=readchar();
	}
	for(; ('0'<=c && c<='9'); c=readchar()) {
		x=x*10+c-'0';
	}
	return x*s;
}
inline void write(long long x) {
	if(x<0) {
		writechar('-'),x=-x;
	}
	char s[25];
	int n=0;
	while(x || !n) {
		s[n++]='0'+x%10,x/=10;
	}
	while(n--) {
		writechar(s[n]);
	}
} 
const int N=2e5+5,M=450;
int n,m;
int idx[N];//块的下标 
int a[N];
int tree[M][N];
inline void insert(int idx,int &num,int d){
	for (int i=num;i<=n;i+=i&-i){
		tree[idx][i]+=d;
	}
}
long long sm;
inline long long query(int idx,int t){
	sm=0;
	for (int i=t;i;i-=i&-i){
		sm+=tree[idx][i];
	}
	return sm;
}
int main(){
	n=read();
	m=sqrt(n);
	register int i;
	for (i=1;i<=n;++i){
		idx[i]=(i-1)/m;
	}
	register long long ans=0;
	for (i=1;i<=n;++i){
		a[i]=i;
		insert(M-1,a[i],1);
		insert(idx[i],a[i],1);//块中加上 
		ans+=i-query(M-1,a[i]);
	}
	register int t=read();
	register int u,v,idx1,idx2;
	for (int _=0;_<t;++_){
		u=read();
		v=read();
		if (u>v){
		    swap(u,v);
		}
		idx1=idx[u],idx2=idx[v];
		if (a[u]<a[v]){
			++ans;
		}
		if (a[u]>a[v]){
			--ans;
		}
		if (idx1==idx2 || idx1+1==idx2){//块太小了
			for (i=u+1;i<v;++i){
				if (a[i]>a[u]) ++ans;
				if (a[i]<a[u]) --ans;
				if (a[i]>a[v]) --ans;
				if (a[i]<a[v]) ++ans;
			}
			insert(idx2,a[u],1);
			insert(idx1,a[v],1);
			insert(idx1,a[u],-1);
			insert(idx2,a[v],-1);
			swap(a[u],a[v]);
//			cout<<"1145141919810"<<endl;
//			printf("%lld\n",ans);
			write(ans);
			writechar('\n');
			continue;
		}
//		cout<<"klfewjfkljewfkejf"<<endl;
		for (i=u+1;idx[i]==idx1;++i){
			if (a[i]>a[u]) ++ans;
			if (a[i]<a[u]) --ans;
			if (a[i]>a[v]) --ans;
			if (a[i]<a[v]) ++ans;
		}
		for (i=v-1;idx[i]==idx2;--i){
			if (a[i]>a[u]) ++ans;
			if (a[i]<a[u]) --ans;
			if (a[i]>a[v]) --ans;
			if (a[i]<a[v]) ++ans;
		}
//		for (int i=1;i<=n;++i){
//			cout<<a[i]<<" ";
//		}
//		cout<<endl;
//		cout<<"ans : "<<ans<<endl;
		for (i=idx1+1;i<idx2;++i){
			ans+=query(i,N-1)-query(i,a[u]);
			ans-=query(i,a[u]-1);//小于他的
			ans-=query(i,N-1)-query(i,a[v]); 
			ans+=query(i,a[v]-1);
		}
		insert(idx2,a[u],1);
		insert(idx1,a[v],1);
		insert(idx1,a[u],-1);
		insert(idx2,a[v],-1);
		swap(a[u],a[v]);
//		printf("%lld\n",ans);
		write(ans);
		writechar('\n');
	}
	flush();
	return 0;
}