A. Inverse
分析
设 (f[o][i][j]) 为第 (o) 次操作后 (a[i]>a[j]) 的概率
因为期望具有线性性，所以最后可以直接统计概率之和
暴力的做法是每次枚举反转的区间以及点对
设反转的区间为 ([l,r])
如果 (i>r || j<l || (i<l && j>r))，反转对当前两个点之间的关系没有影响，直接由 (f[o-1][i][j]) 继承即可
如果 (i geq l && i leq r&& j>r)，由 (f[o-1][l+r-i][j]) 转移
如果 (i<l && j geq l && j leq r)，由 (f[o-1][i][l+r-j]) 转移
否则由 (f[o-1][l+r-i][l+r-j]) 转移
发现这个东西可以前缀和套前缀和优化
以第二个转移为例
设 (sum1[o][i][j]=sumlimits_{p=1}^if[o][p][j],sum2[o][i][j]=sumlimits_{p=1}^isum1[o][p][j])
(egin{aligned}f[o][i][j]&= sumlimits_{l=1}^isumlimits_{r=i}^{j-1}f[o-1][l+r-i][j]\&=sum_{l=1}^isum_{r=0}^{j-i-1}f[o-1][l+r][j]\&=sumlimits_{l=1}^isum1[o-1][j-i-1+l][j]-sum1[o-1][l-1][j]\&=sum2[o-1][j-1][j]-sum2[o-1][j-i-1][j]-sum2[o-1][i-1][j]end{aligned})
另外几个同理
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<map>
#include<vector>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=505,mod=1e9+7;
inline int addmod(rg int now1,rg int now2){
return now1+=now2,now1>=mod?now1-mod:now1;
}
inline int delmod(rg int now1,rg int now2){
return now1-=now2,now1<0?now1+mod:now1;
}
inline int mulmod(rg long long now1,rg int now2){
return now1*=now2,now1>=mod?now1%mod:now1;
}
inline int ksm(rg int ds,rg int zs){
rg int nans=1;
while(zs){
if(zs&1) nans=mulmod(nans,ds);
ds=mulmod(ds,ds);
zs>>=1;
}
return nans;
}
int n,a[maxn],k;
int f[55][maxn][maxn],s1[55][maxn][maxn],s2[55][maxn][maxn],s3[55][maxn][maxn],s4[55][maxn][maxn],s5[55][maxn][maxn],s6[55][maxn][maxn];
int js(rg int val){
return (val+1)*val/2;
}
void solve(){
rg int ny=ksm((n+1)*n/2,mod-2);
for(rg int i=1;i<=n;i++){
for(rg int j=1;j<=n;j++){
if(a[i]>a[j]) f[0][i][j]=1;
}
}
for(rg int o=1;o<=k;o++){
for(rg int i=1;i<=n;i++){
for(rg int j=1;j<=n;j++){
s1[o-1][i][j]=addmod(s1[o-1][i-1][j],f[o-1][i][j]);
s2[o-1][i][j]=addmod(s2[o-1][i-1][j],s1[o-1][i][j]);
s3[o-1][i][j]=addmod(s3[o-1][i][j-1],f[o-1][i][j]);
s4[o-1][i][j]=addmod(s4[o-1][i][j-1],s3[o-1][i][j]);
s5[o-1][i][j]=addmod(s5[o-1][i-1][j-1],f[o-1][i][j]);
s6[o-1][i][j]=addmod(s6[o-1][i-1][j-1],s5[o-1][i][j]);
}
}
for(rg int i=1;i<=n;i++){
for(rg int j=i+1;j<=n;j++){
f[o][i][j]=mulmod(f[o-1][i][j],mulmod(ny,js(i-1)+js(n-j)+js(j-i-1)));
f[o][i][j]=addmod(f[o][i][j],mulmod(ny,delmod(delmod(s2[o-1][j-1][j],s2[o-1][j-i-1][j]),s2[o-1][i-1][j])));
f[o][i][j]=addmod(f[o][i][j],mulmod(ny,delmod(delmod(s4[o-1][i][n],s4[o-1][i][n-j+i]),delmod(s4[o-1][i][j-1],s4[o-1][i][i-1]))));
f[o][i][j]=addmod(f[o][i][j],mulmod(ny,delmod(delmod(s6[o-1][n][n+i-j],s6[o-1][n-i][n-j]),s6[o-1][j-1][i-1])));
}
}
for(rg int i=1;i<=n;i++){
for(rg int j=i+1;j<=n;j++){
f[o][j][i]=delmod(1,f[o][i][j]);
}
}
}
rg int ans=0;
for(rg int l=1;l<=n;l++){
for(rg int r=l;r<=n;r++){
ans=addmod(ans,f[k][l][r]);
}
}
printf("%d
",ans);
}
int main(){
n=read(),k=read();
for(rg int i=1;i<=n;i++) a[i]=read();
solve();
return 0;
}
B. Subsequence
分析
貌似是之前的一道原题
有一个十分显然的 (O(n^2)) 的暴力做法
设 (dp[i][j]) 为前 (i) 个数中选择了 (j) 个数的最大价值
那么 (dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+a[i] imes j))
前面的含义是不选 (i)，后面的含义是选了 (i) 并且把它作为第 (j) 个
经过严谨的打表我们发现，对于原来 (i) 这个物品一定存在一个明显的分界点 (p)
使得当 (j<p) 的时候存在 (dp[i][j]) 由 (dp[i-1][j-1]) 转移而来
当 (j geq p) 的时候由 (dp[i-1][j-1]+a[i] imes j) 转移而来
此时有一个十分神仙的想法是处理出一个差分数组 (g) 使得 (g[i][j]=dp[i][j]-dp[i][j-1])
于是对于 (g) 数组的取值我们可以作出以下分类讨论:
(g[i][j]=dp[i][j]-dp[i][j-1]=dp[i-1][j]-dp[i-1][j-1]=g[i-1][j](j<p))
(g[i][j]=dp[i][j]-dp[i][j-1]=dp[i-1][j-1]+a[i] imes j-dp[i-1][j-1]=a[i] imes j(j=p))
(g[i][j]=dp[i][j]-dp[i][j-1]=dp[i-1][j-1]+a[i] imes j-dp[i-1][j-2]-a[i] imes (j-1)=g[i-1][j-1]+a[i](j>p))
假设我们现在已经有了 (g[i]) 的一个数组要去得到 (g[i+1])
我们可以发现如果我们以 (g[i][j]-a[i] imes j)作为排序标准序列是单调递减的
就可以二分插入来查找 (p) 点的位置
(p) 点之前的 (g) 数组直接继承，(p) 点就是 (a[i] imes j)，之后就是 (g[i-1][j-1]+a[i])
为什么要以 (g[i][j]-a[i] imes j) 排序呢
因为前面提到我们需要一个单调递减的序列
我们二分插入之前的序列是单调的
我们要保证插入之后也是单调的
因为插入对前面的位置没有影响都是直接继承相对大小关系不变
(p) 点之后的位置都需要加一个 (a[i])可能会破坏单调性
但是由于我们的排序标准是 (g[i][j]-a[i] imes j)
后面的位置由于向后挪了一位 (j−1)也会变大(1)，正好把多出来的 (a[i])减没了，单调性依然满足
于是我们现在需要的是一个支持二分查找,插入,区间加法的数据结构,平衡树即可
代码
#include<cstdio>
#include<set>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#define rg register
const int maxn=3e5+5;
int n,rt,sta[maxn],tp,a[maxn];
long long g[maxn];
struct trr{
int ch[2],fa,siz;
long long laz,val;
}tr[maxn];
void push_up(rg int da){
tr[da].siz=tr[tr[da].ch[0]].siz+tr[tr[da].ch[1]].siz+1;
}
void push_down(rg int da){
if(!tr[da].laz) return;
rg int lc=tr[da].ch[0],rc=tr[da].ch[1];
if(lc){
tr[lc].laz+=tr[da].laz;
tr[lc].val+=tr[da].laz;
}
if(rc){
tr[rc].laz+=tr[da].laz;
tr[rc].val+=tr[da].laz;
}
tr[da].laz=0;
}
void xuanzh(rg int x){
rg int y=tr[x].fa;
rg int z=tr[y].fa;
rg int k=tr[y].ch[1]==x;
if(z) tr[z].ch[tr[z].ch[1]==y]=x;
tr[x].fa=z;
tr[y].ch[k]=tr[x].ch[k^1];
tr[tr[x].ch[k^1]].fa=y;
tr[x].ch[k^1]=y;
tr[y].fa=x;
push_up(y);
push_up(x);
}
void splay(rg int x){
tp=0;
sta[tp=1]=x;
for(rg int i=x;tr[i].fa!=0;i=tr[i].fa) sta[++tp]=tr[i].fa;
for(rg int i=tp;i>=1;i--) push_down(sta[i]);
while(tr[x].fa!=0){
rg int y=tr[x].fa;
rg int z=tr[y].fa;
if(z!=0) (tr[z].ch[1]==y)^(tr[y].ch[1]==x)?xuanzh(x):xuanzh(y);
xuanzh(x);
}
rt=x;
}
void solve(rg int now,rg int id){
int totsiz=1,p,lp;
while(now){
push_down(now);
if(tr[now].val>1LL*a[id]*(totsiz+tr[tr[now].ch[0]].siz)){
totsiz+=tr[tr[now].ch[0]].siz+1;
now=tr[lp=now].ch[p=1];
} else {
now=tr[lp=now].ch[p=0];
}
}
tr[id].fa=lp;
tr[lp].ch[p]=id;
tr[id].val=1LL*a[id]*totsiz;
tr[id].siz=1;
splay(id);
tr[tr[id].ch[1]].laz+=a[id];
tr[tr[id].ch[1]].val+=a[id];
}
void dfs(rg int now){
push_down(now);
if(tr[now].ch[0]) dfs(tr[now].ch[0]);
g[++tp]=tr[now].val;
if(tr[now].ch[1]) dfs(tr[now].ch[1]);
}
int main(){
scanf("%d",&n);
for(rg int i=1;i<=n;i++) scanf("%d",&a[i]);
rt=1,tr[1].val=a[1],tr[1].siz=1;
for(rg int i=2;i<=n;i++) solve(rt,i);
tp=0;
dfs(rt);
for(rg int i=1;i<=n;i++){
g[i]+=g[i-1];
printf("%lld ",g[i]);
}
printf("
");
return 0;
}
C. Convex
分析
暴力的做法是枚举对角线，求出对角线两侧两个多边形的面积之差
考虑一个类似于旋转卡壳的过程
从一号节点开始枚举，同时维护一个指针
若指针和当前节点围成的多边形的面积小于等于总面积的一半，把指针继续向后移动一位
否则计算两个点之间所有对角线的贡献
可以通过维护横纵坐标的前缀和、叉积的前缀和以及叉积前缀和的前缀和做到 (O(1)) 计算
因为要比较面积大小，所以有些地方不能取模
代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=8e6+5,mod=1e9+7;
inline int addmod(rg int now1,rg int now2){
return now1+=now2,now1>=mod?now1-mod:now1;
}
inline int delmod(rg int now1,rg int now2){
return now1-=now2,now1<0?now1+mod:now1;
}
inline int mulmod(rg long long now1,rg int now2){
return now1*=now2,now1>=mod?now1%mod:now1;
}
int n,jlx[maxn],jly[maxn],sumx[maxn],sumy[maxn],sum2[maxn],sum3[maxn];
long long sum1[maxn];
long long ans,sum;
long long getarea(rg int i,rg int j){
return 1LL*jlx[i]*jly[j]-1LL*jly[i]*jlx[j];
}
long long getans(rg int i,rg int j){
return sum1[j-1]-sum1[i-1]+getarea(j,i);
}
long long getans2(rg int i,rg int j){
return sum1[j-1]-sum1[i-1];
}
int getit(rg long long val){
return (val%mod+mod)%mod;
}
int js(rg int i,rg int j){
rg int nans=delmod(mulmod(delmod(sumx[j],sumx[i+1]),getit(jly[i])),mulmod(delmod(sumy[j],sumy[i+1]),getit(jlx[i])));
nans=addmod(nans,delmod(delmod(sum2[j-1],sum2[i]),mulmod(j-i-1,sum3[i-1])));
nans=delmod(mulmod(j-i-1,sum%mod),mulmod(nans,2));
return nans;
}
int main(){
n=read();
for(rg int i=1;i<=n;i++) jlx[i]=read(),jly[i]=read();
std::reverse(jlx+1,jlx+n+1);
std::reverse(jly+1,jly+n+1);
for(rg int i=n+1;i<=n+n;i++) jlx[i]=jlx[i-n],jly[i]=jly[i-n];
for(rg int i=1;i<=n;i++) sum+=getarea(i,i+1);
for(rg int i=1;i<=n+n;i++) sumx[i]=addmod(sumx[i-1],getit(jlx[i]));
for(rg int i=1;i<=n+n;i++) sumy[i]=addmod(sumy[i-1],getit(jly[i]));
for(rg int i=1;i<=n+n;i++) sum1[i]=getarea(i,i+1)+sum1[i-1];
for(rg int i=1;i<=n+n;i++) sum3[i]=addmod(sum3[i-1],getit(getarea(i,i+1)));
for(rg int i=1;i<=n+n;i++) sum2[i]=addmod(sum3[i],sum2[i-1]);
rg int tail=3;
for(rg int i=1;i<=n;i++){
while(getans(i,tail)*2<=sum) tail++;
if(tail-1>=i+2) ans=addmod(ans,js(i,tail-1));
}
printf("%d
",ans);
return 0;
}