雅礼集训2019 day7

Inverse

$1 ≤ n ≤ 500,0 ≤ k ≤ 50$1≤n≤500,0≤k≤50, P是一个1到n的排列.
概率$dp$dp好题。
思路：
定义$f_{i,j,k}$fi,j,k​表示$k$k轮变换之后$a_{p_i}>a_{p_j}$api​​>apj​​的概率。
然后考虑对当前轮翻转的区间$[l,r]$[l,r]分类转移。

1. $r&lt;i\ \ or\ \ l&gt;j\ \ or\ \ i&lt;l&lt;r&lt;j$r<i  or  l>j  or  i<l<r<j，则$f_{i,j,k-1}\rightarrow f_{i,j,k}$fi,j,k−1​→fi,j,k​
2. $l\le i\le r&lt;j$l≤i≤r<j，则$f_{l+r-i,j,k-1}\rightarrow f_{i,j,k}$fl+r−i,j,k−1​→fi,j,k​
3. $i&lt;l\le j\le r$i<l≤j≤r，则$f_{i,l+r-j,k-1}\rightarrow f_{i,j,k}$fi,l+r−j,k−1​→fi,j,k​
4. $l\le i&lt;j\le r$l≤i<j≤r，则$1-f_{l+r-j,l+r-i}\rightarrow f_{i,j,k}$1−fl+r−j,l+r−i​→fi,j,k​

利用二阶前缀和来优化转移可以做到$O(n^2k)$O(n2k)
代码：

#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
	static char buf[rlen],*ib,*ob;
	(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
	return ib==ob?-1:*ib++;
}
inline int read(){
	int ans=0;
	char ch=gc();
	while(!isdigit(ch))ch=gc();
	while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
	return ans;
}
typedef long long ll;
const int mod=1e9+7;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
inline void update(int&a,const int&b){a=a+b>=mod?a+b-mod:a+b;}
inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=mul(a,a))if(p&1)ret=mul(ret,a);return ret;}
const int N=505;
int n,k,a[N],f[2][N][N],coe[N][N],tmp=0,ans=0,inv;
int sl[2][N][N],ssl[2][N][N],sm[2][N][N],ssm[2][N][N],sr[2][N][N],ssr[2][N][N];
inline int calc(int x){return x*(x+1)/2;}
inline void init(){
	inv=ksm(calc(n),mod-2);
	for(ri v,i=1;i<n;++i)for(ri j=i+1;j<=n;++j){
		v=a[i]>a[j];
		coe[i][j]=add(calc(j-i-1),add(calc(i-1),calc(n-j)));
		ssl[tmp][i][j]=add(ssl[tmp][i-1][j],sl[tmp][i][j]=add(sl[tmp][i-1][j],v));
		ssr[tmp][i][j]=add(ssr[tmp][i][j-1],sr[tmp][i][j]=add(sr[tmp][i][j-1],v));	
		ssm[tmp][i][j-i]=add(ssm[tmp][i-1][j-i],sm[tmp][i][j-i]=add(sm[tmp][i-1][j-i],dec(1,v)));
		f[tmp][i][j]=v;
	}
}
int main(){
	n=read(),k=read();
	for(ri i=1;i<=n;++i)a[i]=read();
	init();
	while(k--){
		tmp^=1;
		for(ri val,i=1;i<n;++i)for(ri j=i+1;j<=n;++j){
			val=mul(f[tmp^1][i][j],coe[i][j]);
			update(val,dec(dec(ssl[tmp^1][j-1][j],ssl[tmp^1][j-i-1][j]),ssl[tmp^1][i-1][j]));
			update(val,dec(add(ssr[tmp^1][i][n],ssr[tmp^1][i][i-1]),add(ssr[tmp^1][i][i+n-j],ssr[tmp^1][i][j-1])));
			update(val,dec(dec(ssm[tmp^1][n+i-j][j-i],ssm[tmp^1][n-j][j-i]),ssm[tmp^1][i-1][j-i]));
			val=mul(val,inv);
			ssl[tmp][i][j]=add(ssl[tmp][i-1][j],sl[tmp][i][j]=add(sl[tmp][i-1][j],val));
			ssr[tmp][i][j]=add(ssr[tmp][i][j-1],sr[tmp][i][j]=add(sr[tmp][i][j-1],val));
			ssm[tmp][i][j-i]=add(ssm[tmp][i-1][j-i],sm[tmp][i][j-i]=add(sm[tmp][i-1][j-i],dec(1,val)));
			f[tmp][i][j]=val;
		}
	}
	for(ri i=1;i<n;++i)for(ri j=i+1;j<=n;++j)update(ans,f[tmp][i][j]);
	cout<<ans;
	return 0;
}

Subsequence

$n ≤ 10^5,|Ai|≤ 10^7.$n≤105,∣Ai∣≤107.
思路：
先考虑$O(n^2)dp$O(n2)dp做法，$f_{i,j}$fi,j​表示前$i$i个选$j$j个出来的最值。
那么显然$f_{i,j}=\max\{f_{i-1,j},f_{i-1,j-1}+a_i*j\}$fi,j​=max{fi−1,j​,fi−1,j−1​+ai​∗j}
然后通过打表/证明发现对于每一个$i$i，转移方程中满足后一种决策更优的$j$j一定是一段后缀。
证明：

于是可以用平衡树来维护$f_{i}$fi​的差分数组，每次从$f_i$fi​转移到$f_{i+1}$fi+1​的时候直接将$a_i$ai​二分插入，然后将比它打的全部加上这个$a_i$ai​的贡献。
代码：

#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
	static char buf[rlen],*ib,*ob;
	(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
	return ib==ob?-1:*ib++;
}
inline int read(){
	int ans=0;
	bool f=1;
	char ch=gc();
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
	return f?ans:-ans;
}
typedef long long ll;
const int N=1e5+5;
int n;
ll sum=0,a[N];
namespace Splay{
	#define lc (son[p][0])
	#define rc (son[p][1])
	int son[N][2],siz[N],fa[N],rt=0,tot=0;
	ll val[N],add[N];
	inline bool which(const int&x){return x==son[fa[x]][1];}
	inline void pushup(int p){siz[p]=siz[lc]+1+siz[rc];}
	inline void pushnow(int p,ll v){add[p]+=v,val[p]+=v;}
	inline void pushdown(int p){
		if(add[p]){
			if(lc)pushnow(lc,add[p]);
			if(rc)pushnow(rc,add[p]);
			add[p]=0ll;
		}
	}
	inline void rotate(int x){
		int y=fa[x],z=fa[y],t=which(x);
		if(z)pushdown(z),son[z][which(y)]=x;
		pushdown(x),pushdown(y);
		fa[x]=z,fa[y]=x,son[y][t]=son[x][t^1],son[x][t^1]=y;
		if(son[y][t])fa[son[y][t]]=y;
		pushup(y),pushup(x);
	}
	inline void splay(int x){while(fa[x]){if(fa[fa[x]])rotate(which(x)^which(fa[x])?x:fa[x]);rotate(x);}rt=x;}
	inline int build(ll v,int ft,int t){return val[++tot]=v,siz[tot]=1,fa[tot]=ft,son[tot][0]=son[tot][1]=0,ft?son[ft][t]=tot:0,tot;}
	inline int insert(ll v){
		int p=rt,ft=0,t=0;
		ll coe=0;
		while(p){
			pushdown(ft=p);
			if((coe+siz[lc]+1)*v>val[p])p=lc,t=0;
			else coe+=siz[lc]+1,p=rc,t=1;
		}
		return splay(p=build((coe+1)*v,ft,t)),p;
	}
	inline void solve(int p){
		pushdown(p);
		if(lc)solve(lc);
		cout<<(sum+=val[p])<<' ';
		if(rc)solve(rc);
	}
}
int main(){
	n=read();
	for(ri i=1;i<=n;++i)a[i]=read();
	for(ri p,i=1;i<=n;++i){
		p=Splay::insert(a[i]);
		if(Splay::son[p][1])Splay::pushnow(Splay::son[p][1],a[i]);
	}
	Splay::solve(Splay::rt);
	return 0;
}

Convex

$4 ≤ n ≤ 2×10^6,|xi|,|yi|≤ 10^9.$4≤n≤2×106,∣xi∣,∣yi∣≤109. 保证给出的多边形严格为凸包.
思路：
假设一根对角线将多边形分成了$S_a\le S_b$Sa​≤Sb​两部分，然后它对答案的贡献就是$All\_area-2*S_a$All_area−2∗Sa​，这启发我们只用求$S_a$Sa​的和，然后用类似旋转卡壳的方法可以卡出每一个点对$(l,r)$(l,r)满足$线lr$线lr左边的面积不超过右边的。
发现答案是这么个东西：$\sum_{lim=l+2}^{r}\sum_{i=l+2}^{lim}(p_{i}-p_l)*(p_{i-1}-p_l)$∑lim=l+2r​∑i=l+2lim​(pi​−pl​)∗(pi−1​−pl​)
由于叉积具有分配律因此可以展开这个式子的后面变成求$\sum_{lim=l+2}^{r}\sum_{i=l+2}^{lim}p_i*p_{i-1}-p_l*p_{i-1}-p_i*p_l$∑lim=l+2r​∑i=l+2lim​pi​∗pi−1​−pl​∗pi−1​−pi​∗pl​
$\Rightarrow Ans_{l,r}=\sum_{i=l+2}^{r}(r-i)(p_i*p_{i-1}-pl*p_{i-1}-p_i*p_l)$⇒Ansl,r​=∑i=l+2r​(r−i)(pi​∗pi−1​−pl∗pi−1​−pi​∗pl​)
于是维护一下$\sum p_i*p_{i-1}$∑pi​∗pi−1​和$\sum p_i$∑pi​就可以了。
代码：

#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
	static char buf[rlen],*ib,*ob;
	(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
	return ib==ob?-1:*ib++;
}
inline int read(){
	int ans=0;
	bool f=1;
	char ch=gc();
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
	return f?ans:-ans;
}
typedef long long ll;
const int mod=1e9+7;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
inline void update(int&a,const int&b){a=a+b>=mod?a+b-mod:a+b;}
inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=mul(a,a))if(p&1)ret=mul(ret,a);return ret;}
const int N=2e6+5;
int n,s1[N<<1],ss1[N<<1],all=0,ans=0;
ll area=0;
struct pot{
	int x,y;
	pot(int x=0,int y=0):x(x),y(y){}
	friend inline pot operator+(const pot&a,const pot&b){return pot(add(a.x,b.x),add(a.y,b.y));}
	friend inline pot operator-(const pot&a,const pot&b){return pot(dec(a.x,b.x),dec(a.y,b.y));}
	friend inline pot operator*(const pot&a,const int&b){return pot(mul(a.x,b),mul(a.y,b));}
	friend inline int operator^(const pot&a,const pot&b){return dec(mul(a.x,b.y),mul(a.y,b.x));}
}a[N<<1],b[N],s2[N<<1],ss2[N<<1];
inline void modify(int l,int r){
	if(r<l)r+=n;
	int S1=0,sum;
	pot S2,S3;
	S1=dec(dec(ss1[r-1],ss1[l]),mul(dec(s1[r-1],s1[l]),2*n-r+1));
	S2=(ss2[r]-ss2[l+1])-(s2[r]-s2[l+1])*(2*n-r);
	S3=(ss2[r-1]-ss2[l])-(s2[r-1]-s2[l])*(2*n-r+1);
	sum=dec(S1,add(S2^a[l],a[l]^S3));
	update(ans,dec(mul(all,r-l-1),mul(2,sum)));
}
inline ll calc(int i,int j,int k){return (ll)(b[i].x-b[k].x)*(b[j].y-b[k].y)-(ll)(b[j].x-b[k].x)*(b[i].y-b[k].y);}
int main(){
	n=read();
	for(ri i=1;i<=n;++i)a[i].x=((b[i].x=read())%mod+mod)%mod,a[i].y=((b[i].y=read())%mod+mod)%mod,a[n+i]=a[i];
	for(ri i=3;i<=n;++i)area+=calc(i,i-1,1),update(all,(a[i]-a[1])^(a[i-1]-a[1]));
	a[n*2+1]=a[1];
	for(ri i=1;i<=n*2;++i){
		s1[i]=add(s1[i-1],a[i+1]^a[i]);
		ss1[i]=add(ss1[i-1],mul(n*2-i+1,a[i+1]^a[i]));
		s2[i]=s2[i-1]+a[i];
		ss2[i]=ss2[i-1]+a[i]*(n*2-i+1);
	}
	ll sum=0;
	for(ri l=1,r=2;l<=n;++l){
		while(sum+calc(r==n?1:r+1,r,l)<=area/2)sum+=calc(r==n?1:r+1,r,l),r=r==n?1:r+1;
		modify(l,r),sum-=calc(r,l+1,l);
	}
	cout<<ans;
	return 0;
}