2019.7.16 义乌模拟赛 T3 白兔的子序列

本文主要是介绍2019.7.16 义乌模拟赛 T3 白兔的子序列，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

卡常题差评。
首先这个东西我们可以枚举中间那个然后扫描线，那么就变成右边不超过某个值的对左边的逆序对个数这个东西可以直接线段树\(O(nlogn)\)搞。
但是这样常数大的和*一样，我们考虑换一种方法。
我们枚举第一个点，那么其实后面的方案数就是大于第一个点随意排列的方案数减去三个点连续上升的方案数。
这个直接树状数组搞就可以了。时间复杂度\(O(nlogn)\)
code:

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define ll long long 
#define db double
#define N 3000000
#define M 50000
#define mod 1000000000
#define mod2 39989
#define eps (1e-7)
#define U unsigned ll
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
using namespace std;
int n,A[N+5];ll ans,now;U seed;
I unsigned long long rd() {seed ^= seed << 13;seed ^= seed >> 7;seed ^= seed << 17;return seed;}
struct BIT{
	ll F[N+5];
	I void insert(int x,int y){while(x<=n) F[x]+=y,x+=x&-x;}
	I ll find(int x){ll ans=0;while(x) ans+=F[x],x-=x&-x;return ans;}
}S1,S2;
int main(){
	freopen("triple.in","r",stdin);freopen("triple.out","w",stdout);
	re int i;scanf("%d%llu",&n,&seed);A[1]=1;for(i=2;i<=n;i++) A[i]=i,swap(A[i],A[rd()%i+1]);
	for(i=1;i<=n;i++){
		now=S1.find(A[i]);ans+=now*(i-1)-S2.find(A[i])-now*(now-1)/2;
		S1.insert(A[i],1);S2.insert(A[i],i);
	}
	printf("%lld\n",ans);
}

这篇关于2019.7.16 义乌模拟赛 T3 白兔的子序列的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！