[CC-CHEFINV]Chef and Swaps

题目大意：

长度为\(n(n\le2\times10^5)\)的数列，\(q(q\le2\times10^5)\)次询问，每次问交换\(A_x\)和\(A_y\)后逆序对个数。询问互相独立。

思路：

一开始先把逆序对求好，然后用主席树计算交换对答案的影响即可。

时间复杂度\(\mathcal O((n+q)\log n)\)。

源代码:

#include<cstdio>

#include<cctype>

#include<vector>

#include<algorithm>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

typedef long long int64;

const int N=2e5+1,logN=20;

int n,m,a[N];

std::vector<int> v;

class FenwickTree {

	private:

		int val[N];

		int lowbit(const int &x) const {

			return x&-x;

		}

	public:

		void modify(int p) {

			for(;p<=m;p+=lowbit(p)) val[p]++;

		}

		int query(int p) const {

			int ret=0;

			for(;p;p-=lowbit(p)) ret+=val[p];

			return ret;

		}

};

FenwickTree bit;

class FotileTree {

	#define mid ((b+e)>>1)

	private:

		struct Node {

			int val,left,right;

		};

		Node node[N*logN];

		int sz,new_node(const int &p) {

			node[++sz]=node[p];

			return sz;

		}

	public:

		int root[N];

		void insert(int &p,const int &b,const int &e,const int &x) {

			p=new_node(p);

			node[p].val++;

			if(b==e) return;

			if(x<=mid) insert(node[p].left,b,mid,x);

			if(x>mid) insert(node[p].right,mid+1,e,x);

		}

		int query(const int &p,const int &q,const int &b,const int &e,const int &l,const int &r) const {

			if(b==l&&e==r) return node[q].val-node[p].val;

			int ret=0;

			if(l<=mid) ret+=query(node[p].left,node[q].left,b,mid,l,std::min(mid,r));

			if(r>mid) ret+=query(node[p].right,node[q].right,mid+1,e,std::max(mid+1,l),r);

			return ret;

		}

	#undef mid

};

FotileTree t;

int main() {

	n=getint();

	const int q=getint();

	for(register int i=1;i<=n;i++) {

		a[i]=getint();

		v.push_back(a[i]);

	}

	std::sort(v.begin(),v.end());

	v.resize(m=std::unique(v.begin(),v.end())-v.begin());

	for(register int i=1;i<=n;i++) {

		a[i]=std::lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;

	}

	int64 tot=0;

	for(register int i=n;i>=1;i--) {

		tot+=bit.query(a[i]-1);

		bit.modify(a[i]);

	}

	for(register int i=1;i<=n;i++) {

		t.insert(t.root[i]=t.root[i-1],1,m,a[i]);

	}

	for(register int i=0;i<q;i++) {

		int x=getint(),y=getint();

		if(x>y) std::swap(x,y);

		const int tmp1=a[x]!=1?t.query(t.root[x],t.root[y],1,m,1,a[x]-1):0;

		const int tmp2=a[x]!=m?t.query(t.root[x],t.root[y],1,m,a[x]+1,m):0;

		const int tmp3=a[y]!=1?t.query(t.root[x],t.root[y],1,m,1,a[y]-1):0;

		const int tmp4=a[y]!=m?t.query(t.root[x],t.root[y],1,m,a[y]+1,m):0;

		printf("%lld\n",tot-tmp1+tmp2+tmp3-tmp4);

	}

	return 0;

}

巴特西

[CC-CHEFINV]Chef and Swaps

[CC-CHEFINV]Chef and Swaps

题目大意：

思路：

源代码:

最新文章

热门文章