Codeforces Round #825 (Div. 2)
\(A\)
3min
#include<bits/stdc++.h>
using namespace std;
int a[105],b[105];
int main(){
int t;cin>>t;
while(t--){
int n;cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
for(int i=1;i<=n;++i)cin>>b[i];
int ans=0;
for(int i=1;i<=n;++i){
ans+=(a[i]!=b[i]);
}
int a1=0,b1=0;
for(int i=1;i<=n;++i){
a1+=(a[i]==1);
b1+=(b[i]==1);
}
ans=min(ans,abs(a1-b1)+1);
cout<<ans<<endl;
}
return 0;
}
\(B\)
7min
#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y){
if(y==0)return x;
return gcd(y,x%y);
}
int a[100005],b[100005];
int main(){
int t;cin>>t;
while(t--){
int n;cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];a[n+1]=0;
for(int i=2;i<=n;++i){
b[i]=a[i-1]/gcd(a[i-1],a[i])*a[i];
}
b[1]=a[1];b[n+1]=a[n];
int fl=1;
for(int i=1;i<=n;++i){
if(gcd(b[i],b[i+1])!=a[i])fl=0;
}
if(fl)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
\(C\)
6min
#include<bits/stdc++.h>
using namespace std;
int a[200005];
int main(){
int t;cin>>t;
while(t--){
int n;cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
long long ans=0;int l=1;
for(int i=1;i<=n;++i){
l=max(i-a[i]+1,l);
ans+=i-l+1;
}
cout<<ans<<endl;
}
return 0;
}
\(D\)
跟 \(C\) 同理， 设前 \(i\) 个 \(i-a[i]+1\) 的最大值为 \(Max_i\)，答案即为 \(\sum i-Max_i+1\)。于是只要动态维护前缀最大值之和就好了。
于是我突然想起 楼房重建，于是赶紧 rush，虽然但是细节忘光了，比赛时没调出来。。。
需要注意的细节：
①节点 \(up\) 函数较为特殊，每次需要查询右儿子的信息。每次是相当于区间查询，但一定恰好完全覆盖当前节点，所以就可以直接利用节点信息计算。（考场上以为可能出现真子集，就没继续写了 QAQ
#include<bits/stdc++.h>
using namespace std;
#define N 200005
int a[N],Maxn[N];
struct seg{
int l,r,maxn;
long long sum;
}t[N<<3];
long long ques(int p,long long k){
if(t[p].l==t[p].r)return max(t[p].sum,k);
int mid=(t[p].l+t[p].r)>>1;
if(k>=t[p<<1].maxn)return 1ll*(t[p<<1].r-t[p<<1].l+1)*k+ques(p<<1|1,k);
else return ques(p<<1,k)+t[p].sum-t[p<<1].sum;
}
void up(int p){
t[p].maxn=max(t[p<<1].maxn,t[p<<1|1].maxn);
t[p].sum=t[p<<1].sum+ques(p<<1|1,t[p<<1].maxn);
}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r){
t[p].maxn=Maxn[l];
t[p].sum=Maxn[l];
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
up(p);
}
void change(int p,int l){
if(t[p].l==t[p].r){
t[p].maxn=Maxn[l];
t[p].sum=Maxn[l];
return ;
}
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid)change(p<<1,l);
else change(p<<1|1,l);
up(p);
}
int main(){
int n;cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
for(int i=1;i<=n;++i){
Maxn[i]=i-a[i]+1;
Maxn[i]=max(Maxn[i],1);
}
build(1,1,n);
int q;cin>>q;
while(q--){
int p,x,tmp;cin>>p>>x;
long long ans=1ll*n*(n+1)/2+n;
tmp=Maxn[p];
Maxn[p]=max(1,p-x+1);
change(1,p);
ans-=t[1].sum;
cout<<ans<<endl;
Maxn[p]=tmp;
change(1,p);
}
return 0;
}
附上码风较好的一份代码
//By Erinyes
#include<bits/stdc++.h>
#define maxn 200005
#define int long long
using namespace std;
int n,q;
int a[maxn];
struct sgt{
struct node{int l,r,pos,sum;}t[maxn*4];
#define l(p) t[p].l
#define r(p) t[p].r
#define pos(p) t[p].pos
#define sum(p) t[p].sum
#define len(p) (r(p)-l(p)+1)
int getsum(int p,int k){
if(len(p)==1) return max(k,pos(p));
int mid=l(p)+r(p)>>1;
if(pos(p<<1)<=k) return len(p<<1)*k+getsum(p<<1|1,k);
else return getsum(p<<1,k)+sum(p)-sum(p<<1);
}
void update(int p){
pos(p)=max(pos(p<<1),pos(p<<1|1));
sum(p)=sum(p<<1)+getsum(p<<1|1,pos(p<<1));
}
void build(int p,int l,int r){
l(p)=l,r(p)=r;
if(l==r){pos(p)=sum(p)=max(l-a[l]+1,1ll);return;}
int mid=l+r>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r); update(p);
}
void change(int p,int x,int k){
if(len(p)==1){pos(p)=sum(p)=max(x-k+1,1ll);return;}
int mid=l(p)+r(p)>>1;
x<=mid?change(p<<1,x,k):change(p<<1|1,x,k); update(p);
}
}s;
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
s.build(1,1,n); cin>>q;
while(q--){
int x,k; cin>>x>>k;
s.change(1,x,k);
cout<<n*(n+1)/2-s.t[1].sum+n<<endl;
s.change(1,x,a[x]);
}
return 0;
}
但其实考试的时候我也想过直接分讨，但没想清楚，考后才发现简单得一批
也是要维护前缀最大值之和，设修改后 \(p\) 右边第一个大于 \(Max_i\) 的为 \(q\) ，那么 \([1,p-1]\) 和 \([q,n]\) 都可以预处理（后者是用二分+ \(RMQ\) 维护），而 \([p,q-1]\) 可以直接计算，那不就结束了？？？
#include<bits/stdc++.h>
#define N 200005
using namespace std;
int a[N],f[N][20],T=19,e[21],lo[N];
long long pre_sum[N],suf_sum[N];
inline int get(int l,int r){
if(l>r)return 1;
int len=lo[r-l+1];
return max(f[l][len],f[r-e[len]+1][len]);
}
inline int to(int x,int n){
int l=x+1,r=n+1;
while(l<r){
int mid=(l+r)>>1;
if(get(x+1,mid)>a[x])r=mid;
else l=mid+1;
}
return l;
}
int main(){
int n;cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
a[i]=max(i-a[i]+1,1);
f[i][0]=a[i];
}
a[0]=0,a[n+1]=n+1;f[n+1][0]=n+1;
for(int i=1,maxn=0;i<=n;++i){
maxn=max(maxn,a[i]);
pre_sum[i]=pre_sum[i-1]+maxn;
}
e[0]=1;
for(int i=1;i<=T;++i)e[i]=e[i-1]<<1;
lo[1]=0;
for(int i=2;i<N;++i)lo[i]=lo[i>>1]+1;
for(int len=1;len<=T;++len){
for(int i=1;i<=n+1-e[len]+1;++i){
f[i][len]=max(f[i][len-1],f[i+e[len-1]][len-1]);
}
}
for(int i=n;i;--i){
int x=to(i,n);
suf_sum[i]=suf_sum[x]+1ll*a[i]*(x-i);
}
int q;cin>>q;
while(q--){
int p,x,pre,ind;cin>>p>>x;
long long ans=1ll*n*(n+1)/2+n,sum=0;
pre=a[p];
a[p]=max(p-x+1,get(1,p-1));
ind=to(p,n);
sum=pre_sum[p-1]+1ll*a[p]*(ind-p)+suf_sum[ind];
ans-=sum;
cout<<ans<<endl;
a[p]=pre;
}
return 0;
}