T2
考虑对于每一轮游戏，枚举有几个人选择第一个地图，剩下的人选择第二个地图，然后计算对于答案的贡献为 ，其中
表示选择第一个地图的人数，
表示选择第二个地图的人数。在每一轮取到最大值，求出总和即可。
T3
不难发现，由于给定的是 到
的排列，而所有数二进制只有低
位可能有
，最大只能造出
，所以最后排好序的排列一定满足
。
那么现在我们知道了目标排列，二进制的每一位就可以独立地做了。问题变为了求将一个长 的
序列
变成另一个
序列
，最少需要进行多少次邻项交换。
这是经典问题，对于每个 考虑
需要交换多少次，有一个显然的下界是
即有多少个
一定要经过这里。而这个下界显然是可以取到的。
所以直接算每个 的
的和即可，可以使用前缀和做到线性。
那么时间复杂度为 。
T4
阅读条件，第 个人能将瓶子扔给：
中的后缀最大值处的人；
中的前缀最大值处的人；
不难发现，这些柱子形成一个类似 V 型的山谷结构，而第 个人位于谷底。故这些柱子中高度更矮的能扔向且仅能扔向高度更高的。
也就是说，求出第 个人能将瓶子扔到的人的数量
后，从第
个人开始扔瓶子相当于：
- 每一步从
中等概率随机选择一个整数
，令
；
- 若
变成了
，则停止；
这个问题的期望步数可以通过时间复杂度 的 dp 预处理：
- 设
表示
时的期望步数，其中
，则有转移：
而转移显然可以用前缀和优化到 。
而现在问题变成了求 ，显然可以用单调栈前后跑一次求出来。当然这也等价于笛卡尔树中
的深度，可以建笛卡尔树后 dfs 求出。
时间复杂度 。
T5
首先考虑单组询问 怎么做。
我们的目标是走过所有 中的点，最后再加上修建时间。刻画最优走路形态，一次传送作为一个阶段，不难发现单个阶段内只会往一个方向走，因为往回走的位置已经走过且有传送器，直接传送是不劣的。一个传送器最多被传送两次，一次向左走，一次向右走。考虑相邻两个传送器之间我必须要走到的点。有三种情况：
- 只使用左边的传送器，花费
次传送省去最右边不必到达的点数。
- 只使用右边的传送器，花费
- 两边都使用，花费
次传送省去中间连续最长的不必到达的点数。
把他们合并为一种，相当于左右两端的不必到达段自动增长 ，然后只剩第三种。
考虑计数。不难发现每对相邻传送器之间相互独立，且我们只关心它们之间的距离。考虑拆贡献，设 表示相距
时中间所有方案的操作次数和。答案就是
再设 表示放了
段空位，其中最长的一段时
的方案数。处理时可以枚举
，多记一个
表示现在有没有填恰好长
的一段，枚举一段长度填进来，前缀和优化即可。特殊处理第一段和最后一段填入时的转移即可。然后有
最后再算一下建传送门的贡献，就是 。然后处理一下边界情况即可。
T6
只有把 和
加，
减的操作有用。证明考虑我只关心
，要把他变成全正，这样操作把前一个位置
后一个位置
，不难发现其带来的贡献优于其他所有操作。
对于一次查询，考虑 形成的序列
。第一位只能用
来变大，变正后再操作它就不优了，于是我们假装第一位被删除，一直递归下去。于是我们的策略是：每次找到最前面的负数，把它
，后面一位
。直到所有数都是正数时，我们得到答案。
考虑单点修改，记修改前 序列在操作后第
位被加了
次
，那么有
。把修改看作
，则
，这里方便讨论，我们把上取整可能带来的
简写为
。
。不难发现每次
贡献除
，
轮后该次修改对序列的影响大概就没有了。
可是由于上取整的存在，最后可能会有一长段对序列进行 的影响。给出例子：
3 3 2 5 1 3 2 5 1 3...，第一个 改
后面会一直产生影响。刻画这种情况发生的条件，不难发现条件是
奇偶相间。线段树维护奇偶相同的位置，线段树二分找到终止点，支持区间奇偶翻转，暴力下放标记。
做到 。
偷懒写分块可能也能过。
Code
T2
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int a[110][10010];
int n,m;
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];
int res=0;
for(int i=1;i<=m;i++){
int x=0,y=0,mx=0;
for(int j=1;j<=n;j++)x+=(a[j][i]==0),y+=(a[j][i]==1);
for(int i=x;n-i>=y;i++){
int a=i,b=n-i;
mx=max(mx,a*(b+1)+(a+1)*b);
}
res+=mx;
}
cout<<res<<endl;
}
T3
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int S=2000005;
inline int mabs(int x){return x<0?-x:x;}
int n,m,a[S],b[S];
int c[S],d[S];
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
m=1<<n;
for(int i=1;i<=m;i++) cin>>a[i];
for(int i=1;i<=m;i++) b[i]=i-1;
ll ans=0;
for(int i=0;i<n;i++)
{
for(int j=1;j<=m;j++)
{
c[j]=a[j]>>i&1;
d[j]=b[j]>>i&1;
}
int x=0;
for(int j=1;j<=m;j++)
{
x+=c[j]-d[j];
ans+=mabs(x);
}
}
cout<<ans<<'\n';
return 0;
}
T4
#include <iostream>
#include <cstdio>
using namespace std;
#define p 1000000007
inline void add(int &x,int y)
{
x+=y;
if(x>=p) x-=p;
}
inline int qpow(int x,int y)
{
int res=1;
for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
return res;
}
const int S=1000005;
int fra[S],inv[S];
int n,a[S],pos[S];
int top,sta[S];
int fat[S],dep[S];
int f[S];
int main()
{
fra[0]=1;
for(int i=1;i<=S-3;i++) fra[i]=1ll*fra[i-1]*i%p;
inv[S-3]=qpow(fra[S-3],p-2);
for(int i=S-3;i>=1;i--) inv[i-1]=1ll*inv[i]*i%p;
for(int i=1;i<=S-3;i++) inv[i]=1ll*inv[i]*fra[i-1]%p;
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],pos[a[i]]=i;
for(int i=1;i<=n;i++)
{
bool fl=false;
while(top>0&&a[sta[top]]<a[i]) top--,fl=true;
if(fl) fat[sta[top+1]]=i;
fat[i]=sta[top];
sta[++top]=i;
}
dep[0]=-1;
for(int i=n;i>=1;i--)
{
int u=pos[i];
dep[u]=dep[fat[u]]+1;
}
f[0]=0;
for(int i=1,sm=0;i<=n;i++)
{
f[i]=(1ll*sm*inv[i]%p+1)%p;
add(sm,f[i]);
}
for(int i=1;i<=n;i++) cout<<f[dep[i]]<<' ';
cout<<'\n';
return 0;
}
T5
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,mod,g[5001][5001][2],gsum[5001][5001],f[5001][2],pw3[5001],pw2[5001],GONX1,GONX0,FINW,JIEW;
int MOD(int x)
{
return (x>=mod?x-mod:x);
}
signed main()
{
ios::sync_with_stdio(false);
cin>>n>>mod;
pw3[0]=pw2[0]=1;
pw3[1]=3,pw2[1]=2;
for(int i=2;i<=n;i++)
{
pw3[i]=pw3[i-1]*3%mod;
pw2[i]=pw2[i-1]*2%mod;
g[1][i][0]=1;
gsum[1][i]=1;
for(int z=2;z<=n;z++)
{
int far=z-i;
if(far<0) g[z][i][0]=gsum[z-1][i];
else g[z][i][0]=MOD(gsum[z-1][i]-gsum[far][i]+mod);
gsum[z][i]=MOD(gsum[z-1][i]+g[z][i][0]);
far++;
if(far<0) g[z][i][1]=gsum[z-1][i];
else g[z][i][1]=MOD(gsum[z-1][i]-gsum[far][i]+mod);
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
for(int z=2;z<i;z++)
{
(f[i][0]+=(g[i][z][0]-g[i][z-1][0]+mod)*(2+(i-1)-(z-1)))%=mod;
f[i][0]=MOD(f[i][0]-g[i-z+1][z][0]+mod);
f[i][0]=MOD(f[i][0]-g[i-z+1][z][1]+mod);
(f[i][1]+=(g[i][z][0]-g[i][z-1][0]+mod)*(1+(i-1)-(z-1)))%=mod;
f[i][1]=MOD(f[i][1]-g[i-z+1][z][0]+mod);
}
(ans+=pw3[n-i]*f[i][0]%mod*(n-i))%=mod;
(ans+=pw3[n-i+1]*f[i][1])%=mod;
ans=MOD(ans+pw3[n-1]);
ans=(ans+pw3[n-i]*(i-(i==n))%mod*pw2[i-1])%mod;
}
cout<<MOD(ans+(n-1)*pw2[n]%mod);
}
T6
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<vector>
#include<cassert>
#define int long long
#define LAG 80
#define INF 1000000000
using namespace std;
int n,m,rans,b[1000001],a[1000001],num[1000001],ma;
int chng[4000001];
namespace SEG
{
int sam[4000001],rev[4000001];
void dwntg(int o,int l,int r)
{
rev[o<<1]^=rev[o];
rev[o<<1|1]^=rev[o];
rev[o]=0;
if(l+1==r)
{
if(rev[o<<1]) chng[l]=-chng[l];
rev[o<<1]=0;
if(rev[o<<1|1]) chng[r]=-chng[r];
rev[o<<1|1]=0;
}
}
void add(int o,int l,int r,int x,int y)
{
if(x>y) return;
if(x<=l&&r<=y)
{
rev[o]^=1;
return;
}
dwntg(o,l,r);
int mid=l+r>>1;
if(x<=mid) add(o<<1,l,mid,x,y);
if(y>mid) add(o<<1|1,mid+1,r,x,y);
}
void dwntg(int o,int l,int r,int x,int y)
{
if(l==r)
{
if(rev[o]) chng[l]=-chng[l];
rev[o]=0;
return;
}
dwntg(o,l,r);
int mid=l+r>>1;
if(x<=mid) dwntg(o<<1,l,mid,x,y);
if(y>mid) dwntg(o<<1|1,mid+1,r,x,y);
}
void build(int o,int l,int r,int x,int y)
{
if(x>y) return;
if(l==r)
{
if(chng[l]==chng[l-1]||chng[l]==0) sam[o]=1;
else sam[o]=0;
return;
}
dwntg(o,l,r);
int mid=l+r>>1;
if(x<=mid) build(o<<1,l,mid,x,y);
if(y>mid) build(o<<1|1,mid+1,r,x,y);
sam[o]=(sam[o<<1]|sam[o<<1|1]);
}
int find(int o,int l,int r,int x)
{
if(l==r)
{
if(sam[o]) return l-1;
return l;
}
dwntg(o,l,r);
int mid=l+r>>1;
if(x>mid) return find(o<<1|1,mid+1,r,x);
if(x>=l)
{
int w=find(o<<1,l,mid,x);
if(w==mid) return find(o<<1|1,mid+1,r,x);
return w;
}
if(sam[o<<1]) return find(o<<1,l,mid,x);
return find(o<<1|1,mid+1,r,x);
}
}
using namespace SEG;
int gocal()
{
for(int i=1;i<=n;i++) b[i]=a[i];
for(int i=2;i<=n;i+=2)
{
if(b[i-1]<=b[i])
{
if((b[i]-b[i-1])%2) chng[i/2]=1;
else chng[i/2]=-1;
num[i]=(b[i]-b[i-1])/2;
int rnum=num[i]+(chng[i/2]==1);
b[i-1]+=rnum;
b[i]-=rnum;
b[i+1]+=rnum;
rans+=rnum;
}
}
return rans;
}
void gans()
{
cout<<gocal()<<"\n";
}
void flush(int w,int id)
{
int pr=w+w%2,delta=0;
dwntg(1,1,n/2,max(1ll,pr/2-1),min(n/2,(pr+LAG)/2+1));
for(int i=pr;i<=min(n,pr+LAG);i+=2)
{
b[i-1]=a[i-1];
b[i]=a[i];
int rnum=num[i-2]+(chng[(i-2)/2]==1);
b[i-1]+=rnum;
rans-=num[i]+(chng[i/2]==1);
delta=-(num[i]+(chng[i/2]==1));
if(b[i-1]<=b[i])
{
if((b[i]-b[i-1])%2) chng[i/2]=1;
else chng[i/2]=-1;
num[i]=(b[i]-b[i-1])/2;
int rnum=num[i]+(chng[i/2]==1);
b[i-1]+=rnum;
b[i]-=rnum;
rans+=rnum;
delta+=rnum;
}
else
{
chng[i/2]=0;
num[i]=0;
}
}
build(1,1,n/2,max(1ll,pr/2),min(n/2,(pr+LAG)/2));
if(delta!=0&&(pr+LAG)<=n)
{
int wc=find(1,1,n/2,(pr+LAG)/2);
add(1,1,n/2,(pr+LAG)/2+1,wc);
if(wc+1<=n/2)
{
dwntg(1,1,n/2,wc,wc+2);
int rnum=num[wc+wc]+(chng[wc]==1);
b[wc+wc+1]=a[wc+wc+1];
b[wc+wc+2]=a[wc+wc+2];
b[wc+wc+1]+=rnum;
if(b[wc+wc+1]<=b[wc+wc+2])
{
if((b[wc+wc+2]-b[wc+wc+1])%2) chng[wc+1]=1;
else chng[wc+1]=-1;
num[wc+wc+2]=(b[wc+wc+2]-b[wc+wc+1])/2;
}
else
{
chng[wc+1]=0;
num[wc+wc+2]=0;
}
build(1,1,n/2,wc+1,wc+2);
}
rans+=-delta*((wc-(pr+LAG)/2)%2);
}
cout<<rans<<"\n";
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
n=n+n+1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
gans();
build(1,1,n/2,1,n/2);
for(int i=1,w,v;i<=m;i++)
{
cin>>w>>v;
a[w]=v;
flush(w,i);
}
}
京公网安备 11010502036488号