2026“钉耙编程”中国大学生算法设计暑期联赛（4）-平芜编程栈

sol 6

1003

线段树签到题

注意到最多排2次，如果出现 2 1 0则一定需要排2次，如果已经有序则无需排序，其余情况一次

线段树维护 2 1 0 的出现情况

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f
#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define cnot cout<<"NO"<<"\n"
#define cyes cout<<"YES"<<"\n"
#define cans cout<<ans<<"\n"
#define pb push_back
#define x0 first
#define y0 second
#define lc p<<1
#define rc p<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
#define sp(x) fixed<<setprecision(x)
#define all(v) v.begin(),v.end()
#define fr(i,st,ed) for(int i=st;i<=ed;i++)
#define ffr(i,st,ed,dt) for(int i=st;i<=ed;i+=dt)
using namespace std;
typedef pair<int,string>Pis;
typedef pair<int,int>Pii;
typedef pair<string,string>Pss;
const int N=2e5+10,mod=1e9+7,M=1e6+10;
int lowbit(int x){
return x&(-x);}
struct Node{
bool f;
int l,r;
bool h0,h1,h2,h10,h21,h210;
};
Node tree[N<<2];
int a[N];
void up(int p){
tree[p].f=(tree[lc].f&tree[rc].f&tree[lc].r<=tree[rc].l);
tree[p].l=tree[lc].l;
tree[p].r=tree[rc].r;
tree[p].h0=tree[lc].h0||tree[rc].h0;
tree[p].h1=tree[lc].h1||tree[rc].h1;
tree[p].h2=tree[lc].h2||tree[rc].h2;
tree[p].h10=(tree[lc].h10||tree[rc].h10)||(tree[lc].h1&&tree[rc].h0);
tree[p].h21=(tree[lc].h21||tree[rc].h21)||(tree[lc].h2&&tree[rc].h1);
tree[p].h210=(tree[lc].h210||tree[rc].h210)||(tree[lc].h2&&tree[rc].h10)||(tree[lc].h21&&tree[rc].h0);
}
void build(int p,int l,int r){
if(l==r){
tree[p].f=true;
tree[p].l=tree[p].r=a[l];
tree[p].h0=(a[l]==0);
tree[p].h1=(a[l]==1);
tree[p].h2=(a[l]==2);
tree[p].h10=false;
tree[p].h21=false;
tree[p].h210=false;
return;
}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
up(p);
}
void upd(int p,int l,int r,int pos,int val){
if(l==r){
tree[p].l=tree[p].r=val;
tree[p].h0=(val==0);
tree[p].h1=(val==1);
tree[p].h2=(val==2);
tree[p].h10=false;
tree[p].h21=false;
tree[p].h210=false;
return;
}
int mid=(l+r)>>1;
if(pos<=mid)upd(lc,l,mid,pos,val);
else upd(rc,mid+1,r,pos,val);
up(p);
}
Node que(int p,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return tree[p];
}
int mid=(l+r)>>1;
if(qr<=mid)return que(lc,l,mid,ql,qr);
else if(ql>mid)return que(rc,mid+1,r,ql,qr);
else{
Node resl=que(lc,l,mid,ql,qr);
Node resr=que(rc,mid+1,r,ql,qr);
Node res;
res.f=resl.f&resr.f&(resl.r<=resr.l);
res.l=resl.l;
res.r=resr.r;
res.h0=resl.h0||resr.h0;
res.h1=resl.h1||resr.h1;
res.h2=resl.h2||resr.h2;
res.h10=(resl.h10||resr.h10)||(resl.h1&&resr.h0);
res.h21=(resl.h21||resr.h21)||(resl.h2&&resr.h1);
res.h210=(resl.h210||resr.h210)||(resl.h2&&resr.h10)||(resl.h21&&resr.h0);
return res;
}
}
void init(){
mem(tree,0);
mem(a,0);
}
void solve(){
int n,q;
cin>>n>>q;
init();
fr(i,1,n){
cin>>a[i];
}
build(1,1,n);
while(q--){
int op;
cin>>op;
if(op==1){
int p,x;
cin>>p>>x;
upd(1,1,n,p,x);
}
else{
int l,r;
cin>>l>>r;
Node res=que(1,1,n,l,r);
if(res.f)cout<<0<<"\n";
else if(!res.h210)cout<<1<<"\n";
else cout<<2<<"\n";
}
}
}
signed main(){
GG;
int _t=1;
cin>>_t;
while(_t--){
solve();
}

}
1005

学过AVL的看这个应该很好理解

中序遍历就是原数组的顺序，也就是询问等价两个节点的lca为根，左边的部分后缀子树和右边的部分前缀子树的最大深度

首先AVL建树，然后类似bfs求深度/高度，树上st表求lca；

考虑如何求前缀/后缀子树的深度

以前缀举例

我们先考虑一个节点往父亲节点跳的过程--如果该节点对于父亲而言是左节点，那么它不在被范围包裹的前缀，无需考虑，如果是右节点，那么它贡献的方式是当前子树的值与它父亲节点左子树的值取max,

显式表示：f(x)=max(1+h[lc(p)],x+1)

对于每一个这样的操作都可以抽象成：f(x)=max(a,x+b)

考虑多个函数的复合：

设：

f(x)=max⁡(a,x+b)g(x)=max(c,x+d)

先应用 g，再应用 f：

f(g(x))=max⁡(a,g(x)+b)=max⁡(a,max⁡(c,x+d)+b)=max⁡(a,c+b,x+d+b)

所以组合后仍然是同样形式：

f∘g(x)=max⁡(max⁡(a,c+b),x+(b+d))

也就是代码的meg部分

这部分操作同样可以在st建表过程一并完成；

后缀取反同理

查询给出底部节点的x，查询路径，考虑左/右取max即可

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f
#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define cnot cout<<"NO"<<"\n"
#define cyes cout<<"YES"<<"\n"
#define cans cout<<ans<<"\n"
#define pb push_back
#define x0 first
#define y0 second
//#define lc p<<1
//#define rc p<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
#define sp(x) fixed<<setprecision(x)
#define all(v) v.begin(),v.end()
#define fr(i,st,ed) for(int i=st;i<=ed;i++)
#define ffr(i,st,ed,dt) for(int i=st;i<=ed;i+=dt)
using namespace std;
typedef pair<int,string>Pis;
typedef pair<int,int>Pii;
typedef pair<string,string>Pss;
const int N=20,mod=1e9+7,M=1e6+10;
int lowbit(int x){
return x&(-x);}
struct Fn{
int a,b;
};
Fn meg(Fn f,Fn g){
return {max(f.a,g.a+f.b),f.b+g.b};
}
int calc(Fn f,int x){
return max(f.a,x+f.b);
}
void solve(){
int n,q;
cin>>n>>q;
vector<int>a(n+1),lc(n+1),rc(n+1),fa(n+1),stk;
fr(i,1,n){
cin>>a[i];
int lst=0;
while(!stk.empty()&&a[stk.back()]>a[i]){
lst=stk.back();
stk.pop_back();
}
if(!stk.empty()){
rc[stk.back()]=i;
fa[i]=stk.back();
}
if(lst){
lc[i]=lst;
fa[lst]=i;
}
stk.pb(i);
}
int rt=stk[0];
vector<int>dep(n+1),h(n+1),ord;
stk={rt};
while(!stk.empty()){
int u=stk.back();
stk.pop_back();
ord.pb(u);
if(lc[u]){
dep[lc[u]]=dep[u]+1;
stk.pb(lc[u]);
}
if(rc[u]){
dep[rc[u]]=dep[u]+1;
stk.pb(rc[u]);
}
}
reverse(all(ord));
for(int u:ord)h[u]=1+max(h[lc[u]],h[rc[u]]);
const Fn INF={-inf,0};
array<vector<int>, N> up;
array<vector<Fn>, N> pre, suf;
fr(j, 0, N - 1) {
up[j].resize(n + 1);
pre[j].assign(n + 1, INF);
suf[j].assign(n + 1, INF);
}
fr(u,1,n){
if(u==rt){
up[0][u]=u;
continue;
}
int p=fa[u];
up[0][u]=p;
if(rc[p]==u)pre[0][u]={1+h[lc[p]],1};
if(lc[p]==u)suf[0][u]={1+h[rc[p]],1};
}
fr(j,1,N-1){
fr(u,1,n){
int p=up[j-1][u];
up[j][u]=up[j-1][p];
pre[j][u]=meg(pre[j-1][p],pre[j-1][u]);
suf[j][u]=meg(suf[j-1][p],suf[j-1][u]);
}
}
auto lca=[&](int u,int v){
if(dep[u]<dep[v])swap(u,v);
int d=dep[u]-dep[v];
fr(j,0,N-1){
if((d>>j)&1)u=up[j][u];
}
if(u==v)return u;
for(int j=N-1;j>=0;j--){
if(up[j][u]!=up[j][v]){
u=up[j][u];
v=up[j][v];
}
}
return fa[u];
};
auto path=[&](int u,int v,const auto&f){
Fn res=INF;
int d=dep[v]-dep[u];
fr(j,0,N-1){
if((d>>j)&1){
res=meg(f[j][v],res);
v=up[j][v];
}
}
return res;
};
auto pref=[&](int u,int v){
return calc(path(u,v,pre),1+h[lc[v]]);
};
auto suff=[&](int u,int v){
return calc(path(u,v,suf),1+h[rc[v]]);
};
while(q--){
int l,r;
cin>>l>>r;
int m=lca(l,r);
int L=l<m?suff(lc[m],l):0;
int R=m<r?pref(rc[m],r):0;
cout<<1+max(L,R)<<"\n";
}
}
signed main(){
GG;
int _t=1;
cin>>_t;
while(_t--){
solve();
}

}
1006

1-n内的每一个数一定要出现>=1次

反向思考，在1-n成排列时，最后一个数必然为n个数的中位数，我们反向模拟删数的过程，具体的，对于每一个中位数，我们考虑它作为中位数需要在原数组中满足的条件（即删除两个数）

如果当前的数的个数-1>=1,说明它仍然需要在b数组出现，也就是需要作为中位数，不能删

维护还未考虑的数和可以被删除的数

对于一个中位数p，如果它的出现次数-1>=1,说明它还需要作为中位数，此时删除它的两边，如果=0，说明它不需要被作为中位数了，分别考虑中位数左移/右移，左移需要删除p和nxt[p](在可删除数组中），右移反之，分别考虑可行性

由此引出一个必要性判断，每[p-d,p+d]需要承担d的中位数，在rem（余量）数组先行判断

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f
#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define cnot cout<<"NO"<<"\n"
#define cyes cout<<"YES"<<"\n"
#define cans cout<<ans<<"\n"
#define pb push_back
#define x0 first
#define y0 second
#define lc p<<1
#define rc p<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
#define sp(x) fixed<<setprecision(x)
#define all(v) v.begin(),v.end()
#define fr(i,st,ed) for(int i=st;i<=ed;i++)
#define ffr(i,st,ed,dt) for(int i=st;i<=ed;i+=dt)
using namespace std;
typedef pair<int,string>Pis;
typedef pair<int,int>Pii;
typedef pair<string,string>Pss;
const int N=2e4+10,mod=1e9+7,M=1e6+10;
int lowbit(int x){
return x&(-x);}
void solve(){
int n;
cin>>n;
int m=(n+1)/2;
int t=n+m;
vector<int>cnt(n+1);
fr(i,1,t){
int x;
cin>>x;
cnt[x]++;
}
fr(i,1,n)if(cnt[i]==0){
cout<<-1<<"\n";
return;
}
vector<int>rem(n+1,0);
fr(i,1,n)rem[i]=cnt[i]-1;
int sum=0;
fr(d,0,m-1){
sum+=rem[m-d];
if(d)sum+=rem[m+d];
if(sum<=d){
cout<<-1<<"\n";
return;
}
}
int p=m;
set<int>zr,al;
fr(i,1,n){
al.insert(i);
if(!rem[i])zr.insert(i);
}
vector<Pii>res;
fr(stp,1,m-1){
if(!al.count(p)||rem[p]<=0){
cout<<-1<<"\n";
return;
}
rem[p]--;
if(!rem[p]){
zr.insert(p);
}
if(rem[p]){
auto it1=zr.lower_bound(p);
auto it2=zr.upper_bound(p);
if(it1==zr.begin()||it2==zr.end()){
cout<<-1<<"\n";
return;
}
int l=*prev(it1),r=*it2;
res.pb({l,r});
al.erase(l);
al.erase(r);
zr.erase(l);
zr.erase(r);
}
else{
auto it=al.find(p);
auto pre=it,suf=next(it);
bool f=0;
if(pre!=al.begin())f=1,pre--;
if(f&&rem[*pre]){
auto it2=zr.upper_bound(p);
if(it2==zr.end()){
cout<<-1<<"\n";
return;
}
int np=*pre;
int r=*it2;
res.pb({p,r});
zr.erase(p);
zr.erase(r);
al.erase(p);
al.erase(r);
p=np;
}
else{
if(suf==al.end()||rem[*suf]<=0){
cout<<-1<<"\n";
return;
}
auto it1=zr.lower_bound(p);
if(it1==zr.begin()){
cout<<-1<<"\n";
return;
}
int l=*prev(it1);
int np=*suf;
res.pb({p,l});
zr.erase(p);
zr.erase(l);
al.erase(p);
al.erase(l);
p=np;
}
}
}
if(al.size()!=1){
cout<<-1<<"\n";
return;
}
reverse(all(res));
cout<<p<<" ";
for(auto [x,y]:res){
cout<<x<<" "<<y<<" ";
}
cout<<"\n";
}
signed main(){
GG;
int _t=1;
cin>>_t;
while(_t--){
solve();
}

}
1007

考虑循环位移某些数位相同，把他们变成出现最多的那个数即可

线段树维护dp

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f
#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define cnot cout<<"NO"<<"\n"
#define cyes cout<<"YES"<<"\n"
#define cans cout<<ans<<"\n"
#define pb push_back
#define x0 first
#define y0 second
#define lc p<<1
#define rc p<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
#define sp(x) fixed<<setprecision(x)
#define all(v) v.begin(),v.end()
#define fr(i,st,ed) for(int i=st;i<=ed;i++)
#define ffr(i,st,ed,dt) for(int i=st;i<=ed;i+=dt)
using namespace std;
typedef pair<int,string>Pis;
typedef pair<int,int>Pii;
typedef pair<string,string>Pss;
const int N=5e5+10,mod=998244353,M=1e6+10;
int lowbit(int x){
return x&(-x);}
struct Node{
int Mincnt,sum,lazy;
};
Node tree[N<<2];
void up(int p){
tree[p].Mincnt=min(tree[lc].Mincnt,tree[rc].Mincnt);
tree[p].sum=0;
if(tree[p].Mincnt==tree[lc].Mincnt)tree[p].sum+=tree[lc].sum;
if(tree[p].Mincnt==tree[rc].Mincnt)tree[p].sum+=tree[rc].sum;
tree[p].sum%=mod;
}
void f(int p,int val){
tree[p].Mincnt+=val;
tree[p].lazy+=val;
}
void down(int p,int l,int r){
if(tree[p].lazy){
f(lc,tree[p].lazy);
f(rc,tree[p].lazy);
tree[p].lazy=0;
}
}
void build(int p,int l,int r){
if(l==r){
tree[p].Mincnt=0;
tree[p].sum=0;
tree[p].lazy=0;
return;
}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
up(p);
}
void setval(int p,int l,int r,int pos,int val){
if(l==r){
tree[p].sum=val;
return;
}
down(p,l,r);
int mid=(l+r)>>1;
if(pos<=mid)setval(lc,l,mid,pos,val);
else setval(rc,mid+1,r,pos,val);
up(p);
}
void upd(int p,int l,int r,int ql,int qr,int val){
if(ql<=l&&r<=qr){
f(p,val);
return;
}
down(p,l,r);
int mid=(l+r)>>1;
if(ql<=mid)upd(lc,l,mid,ql,qr,val);
if(qr>mid)upd(rc,mid+1,r,ql,qr,val);
up(p);
}
Node que(int p,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return tree[p];
}
down(p,l,r);
int mid=(l+r)>>1;
bool fl=0,fr=0;
Node L,R;
if(ql<=mid){
L=que(lc,l,mid,ql,qr);
fl=1;
}
if(qr>mid){
R=que(rc,mid+1,r,ql,qr);
fr=1;
}
if(!fl)return R;
if(!fr)return L;
Node res;
res.Mincnt=min(L.Mincnt,R.Mincnt);
res.sum=0;
if(res.Mincnt==L.Mincnt)res.sum+=L.sum;
if(res.Mincnt==R.Mincnt)res.sum+=R.sum;
res.sum%=mod;
return res;
}
int n;
int dp[N];
void init(int n){
mem(dp,0);
mem(tree,0);
dp[0]=1;
}
void solve(){
cin>>n;
init(n);
vector<int>a(n+1,0);
fr(i,1,n){
cin>>a[i];
}
build(1,1,n);
vector<vector<int>>pos(n+1);
int L=0;
fr(i,1,n){
int x=a[i];
auto&v=pos[x];
setval(1,1,n,i,dp[i-1]);
if(v.size()){
int l=(v.size()>=4?v[v.size()-4]+1:1),r=v.back();
upd(1,1,n,l,r,-1);
}
v.pb(i);
int l=(v.size()>=4?v[v.size()-4]+1:1);
upd(1,1,n,l,i,1);
if(v.size()>=5)L=max(L,v[v.size()-5]);
Node RES=que(1,1,n,L+1,i);
dp[i]=(RES.Mincnt==0?RES.sum:0);
}
cout<<dp[n]<<"\n";
}
signed main(){
GG;
int _t=1;
cin>>_t;
while(_t--){
solve();
}

}
1011

签到

队友敲的

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl "\n"
LL mod=998244353;
LL ksm(LL a,LL n){
LL res=1;
while(n){
if(n&1)res=res*a%mod;
n/=2;
a=a*a%mod;
}
return res%mod;
}

void solve(){
LL n,q;
cin>>n>>q;
vector<LL>a(n+1);
LL cnt=0;
for(int i=1;i<=n;i++){
cin>>a[i];
cnt+=a[i];
}
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
}

while(q--){
LL x;
cin>>x;
if(a[x])cout<<0<<endl;
else cout<<cnt+1<<endl;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
LL T=1;
// build();
cin>>T;
while(T--){
solve();
}
}

2026“钉耙编程”中国大学生算法设计暑期联赛（4）

三分钟搞定Windows日志监控：告别混乱，用这款免费神器轻松管理网络设备日志

MacOS终极zsh配置指南：从基础到深度学习优化

AI新闻日报_2026-08-12-AI Coding 权限范式重构 / 10 亿用户里程碑 / 具身智能资本与基模双线冲刺

终极指南：3步掌握Minecraft地图工具，快速找到宝藏位置

编译原理核心概念与实践指南：从理论到实验的完整学习路径

DCloud生态全解析：从uni-app跨端开发到流应用分发的技术实践