21.3.13数据结构练习

T1

题意

给定一个数\(n\)和一个长为\(n\)的数组\(a_1,a_2,a_3,···,a_n\),求

当中每一行的逆序对个数之和。
\(\%30\)使用\(\ n^3\)暴力，每行两两暴力统计即可
\(\%60\)使用\(\ n^2\)暴力，基于暴力1，滚动过程可以通过计算每个数贡献值来维护新的个数
正解时间复杂度为\(O(n\ log\ n)\)

solution

法一：归并排序

归并排序过程中可以\(O(n\ log\ n)\)地计算逆序对个数，在归并过程中每次右边的数插进来就将\(cnt\)加上此时左边队列中剩余数的个数即可

inline void msort(int l,int r)
{
	if(l==r)return;
	int mid=(l+r)>>1;
	msort(l,mid);msort(mid+1,r);
	for(int i=l;i<=r;i++)c[i]=b[i];
	int lid=l,rid=mid+1,nid=l-1;
	while(lid<=mid&&rid<=r)
	{
		nid++;
		if(c[lid]<=c[rid])
		{
			b[nid]=c[lid++];
		}else
		{
			b[nid]=c[rid++];
			cnt+=mid-lid+1;
		}
	}
	while(lid<=mid)b[++nid]=c[lid++];
	while(rid<=r)  b[++nid]=c[rid++];
	return;
}

注意最后要清空两边的队列
接下来计算每个数在数组中比它大和比它小的数的个数，也就是当该数从队头移到队尾时逆序对个数产生的变化数。
全部代码如下

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
	int x=0,f=1;char c=getchar();
	while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
	while(c>=‘0‘&&c<=‘9‘)x=(x<<1)+(x<<3)+c-‘0‘,c=getchar();
	return x*f;
}
int n,a[1000010],bi[100010];
int si[1000010],cnt;
int b[1000010],c[1000010];
inline void msort(int l,int r)
{
	if(l==r)return;
	int mid=(l+r)>>1;
	msort(l,mid);msort(mid+1,r);
	for(int i=l;i<=r;i++)c[i]=b[i];
	int lid=l,rid=mid+1,nid=l-1;
	while(lid<=mid&&rid<=r)
	{
		nid++;
		if(c[lid]<=c[rid])
		{
			b[nid]=c[lid++];
		}else
		{
			b[nid]=c[rid++];
			cnt+=mid-lid+1;
		}
	}
	while(lid<=mid)b[++nid]=c[lid++];
	while(rid<=r)  b[++nid]=c[rid++];
	return;
}
signed main()
{
	freopen("rotinv.in","r",stdin);
	freopen("rotinv.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)b[i]=a[i]=read();
	msort(1,n);
	for(int i=1;i<=n;i++)
	{
		bi[i]=lower_bound(b+1,b+n+1,a[i])-b-1;
		si[i]=n+b-upper_bound(b+1,b+n+1,a[i])+1;
	}
	int sum=cnt;
	for(int i=2;i<=n;i++)
	{
		cnt=cnt-bi[i-1]+si[i-1];
		sum+=cnt;
	}
	printf("%lld",sum);
	return 0;
}

法二：树状数组

见此神仙的博文

法三：线段树

和法二差不多，懒得写了
其实就是不会

T2

题意

给定两个数\(n,m\)和一个长为\(n\)的数组\(h_1,h_2,h_3,···,h_n\),共有\(m\)个询问，对于每个询问\(l_i\ ,\ r_i\),求\(h\)在\(l_i\)到\(r_i\)范围内以\(h_{l_i}\)为首的最长上升子序列
\(\%30\)的数据使用\(n^2\)暴力，直接模拟即可
正解复杂度为\(O(m\ log\ n)\),然而\(O(n\sqrt{n}\,log\!\sqrt{n})\)的分块可以草过去，毕竟\(1 \le n,m \le 10^5\)

分块做法

咕咕咕

T3

不会

21.3.13数据结构练习

原文：https://www.cnblogs.com/orzlsw/p/14529713.html