E. Monotone Subsequence
\(\text{time limit: 2000 ms}\\\text{memory limit: 1024 MB}\)
这是一道交互题
题意:
由 \(\text{Thm. Erdős–Szekeres}\) ,我们知道对任意长为 \(n^2+1\) 的排列必有一个长为 \(n+1\) 的上升子序列或下降子序列。
现在交互库有一个长为 \(n^2+1\) 的排列,但你并不知道。你每次可以选择 \(n^2+1\) 个下标中的任意多个进行询问,交互库会返回这些下标在对应的子序列中为前缀最大值的下标。你可以问不超过 \(n\) 个问题,然后给出一个长度恰好为 \(n+1\) 的单调子序列。
\(1\leq n\leq 100\)
题解:
场上猜到了结论感觉很奇怪没想清楚证明,很犹豫,最后赌一把交上去发现过了。
我们可以一下子询问整个序列,那么我们可以得到一个前缀最大值序列,这肯定是一个上升子序列。同时我们可以知道这个序列中最大值所在位置,即为返回的下标中最大的那个。
我们很难考察答案为下降子序列的情况。考虑极端情况,不妨 \(n=3\) ,排列形如 \(8,9,10,5,6,7,2,3,4,1\) 那么 \(10,7,4,1\) 构成一个答案。发现下降子序列像是和每段最大的有关系。
考虑如下过程,初始集合 \(S\) 为全体下标,每次询问集合 \(S\) ,交互库返回集合 \(T\) 。如果 \(T\) 大小超过 \(n\) 就得到答案,否则将 \(S\) 改为 \(S-T\) 循环这个过程,直到问了 \(n\) 次。对于每个数我们标记 \(1-n\) ,分别表示它是在第几次询问的时候作为 \(T\) 中元素返回。特别地,将序列中第一个没有被标记的数标记成 \(n+1\) 。
我们从右往左扫,找到最靠后的 \(1,2,\dots,n-1,n,n+1\) 这样的标记子序列。我们声称,这个子序列一定是下降子序列。
其实这也是比较显然的。假设已经考虑完成了 \(i+1,i+2,\dots,n+1\) ,对于选出的标记 \(i+1\) 的数,数值记为 \(x\) ,它前面的第一个标记的 \(i\) ,记为 \(y\) ,必有 \(y>x\) 。这是因为在 \(y\) 之后我们没有选择 \(x\) 作为第 \(i\) 次的前缀最大值。因此我们只需保证在 \(x\) 之前存在这样的 \(y\) 。这也是容易的,因为标记 \(i\) 的第一个数一定在标记 \(i+1\) 的第一个数之前(每次询问的第一个数一定被标记)。那么最终标记的 \(1,2,\dots,n+1\) 构成下降子序列。 \(\square\)
模拟上述过程即可通过。
代码:
// Date: 2025-10-03 23:42:54
// Problem: E. Monotone Subsequence
// Contest: Codeforces - Squarepoint Challenge (Codeforces Round 1055, Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/2152/problem/E
// Memory Limit: 1024 MB
// Time Limit: 2000 ms//#pragma GCC optimize(2,3,"Ofast","inline","unroll-loops")
//#pragma GCC optimize("-Ofast", "-finline", "-funroll-loops", "-fno-stack-protector")
//#pragma GCC target("avx")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){ll x=0; bool f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=0; ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();}return f?x:-x;
}
inline void write(ll x){if(x<0) x=-x,putchar('-');if(x>9) write(x/10);putchar('0'+x%10);
}
const ll N=10009;
ll n;
ll p[N];
ll flag[N];
void solve(){cin>>n;for(ll i=1;i<=n*n+1;i++){p[i]=1;flag[i]=0;}ll lft=n*n+1;for(ll i=1;i<=n;i++){cout<<"? "<<lft<<" ";vector<ll> ask;for(ll j=1;j<=n*n+1;j++){if(p[j]){cout<<j<<" ";ask.emplace_back(j);}}cout<<endl;vector<ll> tmp;ll c; cin>>c;for(ll j=1;j<=c;j++){ll x; cin>>x;tmp.emplace_back(x);flag[x]=i;p[x]=0;lft--;}if(c>=n+1){cout<<"! ";for(ll i=0;i<n+1;i++){cout<<tmp[i]<<" ";}cout<<endl;return;}}cout<<"! ";for(ll i=1;i<=n*n+1;i++){if(!flag[i]){flag[i]=n+1;break;}}vector<ll> ans;ll j=n+1;for(ll i=n*n+1;i>=1;i--){if(flag[i]!=j) continue;ans.push_back(i);j--;if(j==0) break;}reverse(ans.begin(),ans.end());for(ll u:ans){cout<<u<<" ";}cout<<endl;
}
ll T;
int main(){cin>>T;while(T--){solve();}return 0;
}
F. Triple Attack
\(\text{time limit: 3000 ms}\\\text{memory limit: 1024 MB}\)
题意:
给定一个递增的时间戳序列 \(x_1,x_2,\dots,x_n\),以及一个非负整数 \(z\)。我们称一个多重集合 \(Y={y_1,y_2,\dots,y_m}\) 为 安全的,如果对于任意三个元素 \(y_i,y_j,y_k\)(\(1\le i<j<k\le m\))都有
现在有 \(q\) 个查询,每个查询给出一对索引 \(1\le l\le r\le n\)。对于每个查询,考虑多重子集 \({x_l,x_{l+1},\dots,x_r}\),要求在该子多重集中选择一个最大的子集使其 安全 。输出每个查询对应的最大可能大小。
\(1\le n,q\le 250000, 1\le z,x_i\le10^9\)
题解:
条件等价于选出的数满足 \(y_{i+2}-y_i>z\) 。我们先来考虑更容易的问题,如果条件是 \(y_{i+1}-y_i>z\) 怎么做?
对于给定的 \(l,r\) ,我们可以贪心选尽可能早的时间。但时间复杂度 \(O(nq)\) ,能不能给力一点?
可以。注意到对每个 \(i\) 其下一个可以转移到的 \(j\) 是固定的,把它预处理出来。然后我们的询问就相当于每次往右跳,倍增处理这个过程,从 \(l\) 出发,找到第一次跳出 \(r\) 的步数。
回到原问题,我们可以看成是两条跳的路径:从 \(l\) 和 \(l+1\) 开始。但是它们可能会跳到同一个位置?这时候我们从该位置 \(i\) 和 \(i+1\) 继续重复这个过程。
我们同样预处理出每个点跳到的右边第一个位置,然后对其倍增处理。如何刻画跳到同一个位置?我们把跳的过程看作在树上跳父亲,那个相同位置即为 \(i\) 和 \(i+1\) 的 \(lca\) , 然后再从 \(lca\) 和 \(lca+1\) 继续跳。我们第一次倍增是用作计算 \(lca\) ,考虑进行第二次倍增,每次从 \(i\) 跳到 \(lca\) ,直到快要跳出 \(r\) 。对于剩下的位置,我们再用第一个数组倍增得到散块的答案。
代码:
// Date: 2025-10-04 13:25:49
// Problem: F. Triple Attack
// Contest: Codeforces - Squarepoint Challenge (Codeforces Round 1055, Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/2152/problem/F
// Memory Limit: 1024 MB
// Time Limit: 3000 ms//#pragma GCC optimize(2,3,"Ofast","inline","unroll-loops")
//#pragma GCC optimize("-Ofast", "-finline", "-funroll-loops", "-fno-stack-protector")
//#pragma GCC target("avx")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){ll x=0; bool f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=0; ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();}return f?x:-x;
}
inline void write(ll x){if(x<0) x=-x,putchar('-');if(x>9) write(x/10);putchar('0'+x%10);
}
const ll N=250009;
ll n,t,a[N];
ll p[20][N],dep[N];
inline ll lca(ll u,ll v){if(dep[u]<dep[v]) swap(u,v);for(ll i=19;i>=0;i--){if(dep[p[i][u]]>=dep[v]) u=p[i][u];}if(u==v) return u;for(ll i=19;i>=0;i--){if(p[i][u]!=p[i][v]){u=p[i][u],v=p[i][v];}}return p[0][u];
}
pair<ll,ll> st[20][N];
inline ll jump(ll l,ll r){ll res=0;for(ll i=19;i>=0;i--){if(p[i][l]<=r){l=p[i][l],res+=(1<<i);}}return res+1;
}
void init(){for(ll i=0;i<=n+5;i++){for(ll j=0;j<=19;j++){p[j][i]=0;st[j][i]=make_pair(0,0);}dep[i]=0;}
}
void solve(){n=read(),t=read()+1;for(ll i=1;i<=n;i++) a[i]=read();init();ll j=1;for(ll i=1;i<=n;i++){while(j<=n&&a[j]<a[i]+t){j++;}p[0][i]=j;}p[0][n+1]=n+1;for(ll i=1;i<20;i++){for(ll j=1;j<=n+1;j++){p[i][j]=p[i-1][p[i-1][j]];}}for(ll i=n;i>=1;i--){dep[i]=dep[p[0][i]]+1;}for(ll i=1;i<=n;i++){ll l=lca(i,i+1);st[0][i]=make_pair(l,dep[i]+dep[i+1]-2*dep[l]);}st[0][n+1]=make_pair(n+1,0);for(ll i=1;i<20;i++){for(ll j=1;j<=n+1;j++){ll u=st[i-1][j].first,d1=st[i-1][j].second;ll v=st[i-1][u].first,d2=st[i-1][u].second;st[i][j]=make_pair(v,d1+d2);}}ll nQ=read();while(nQ--){ll l=read(),r=read();if(r-l+1<=2){printf("%lld\n",r-l+1);continue;}ll ans=0;for(ll i=19;i>=0;i--){if(st[i][l].first<=r){ans+=st[i][l].second,l=st[i][l].first;}}if(l<=r) ans+=jump(l,r);if(l+1<=r) ans+=jump(l+1,r);printf("%lld\n",ans);}
}
int main(){ll T=read();while(T--){solve();}return 0;
}
G. Query Jungle
\(\text{time limit: 3000 ms}\\\text{memory limit: 1024 MB}\)
题意:
有一棵以顶点 \(1\) 为根的无向树,顶点编号为 \(1,\dots,n\)。每个顶点有一个状态:\(1\) 表示该顶点“有怪物”,\(0\) 表示“无怪物”。如果某条从根出发的路径包含某顶点 \(x\)(作为路径上的某个顶点),就称该路径 包含 顶点 \(x\)。
目标:对于当前的顶点状态,求最小整数 \(k\),使存在 \(k\) 条从根 \(1\) 出发的路径,使得每个状态为 \(1\)(有怪物)的顶点至少被一条路径包含。路径之间可以相互重叠。
现在有 \(q\) 次查询,查询给出一个顶点 \(v\):对 \(v\) 的子树(包括 \(v\) 本身)中每个顶点,都将其状态取反(\(0\leftrightarrow1\))。每次查询修改会影响后续查询的状态。每次查询之后,都要求重新计算并输出当前状态下的最小 \(k\)。
题解:
其实是简单题,但完全没有时间去看了。
对树上修改,可以考虑转成欧拉序。如果一个点有怪物,将它欧拉序上对应的两个位置标为 \(23\) ,否则标为 \(01\) 。那么问题的答案就相当于欧拉序上最长的 \(2323\dots\) 子序列的长度 \(\divsymbol 2\) ,修改子树相当于对欧拉序上作 \(0\leftrightarrow2,1\leftrightarrow3\) 的变换。于是我们用线段树维护区间 \(010\dots,101\dots,232\dots,323\dots\) 四者的最长子序列长度即可。
代码:
// Date: 2025-10-04 14:27:21
// Problem: G. Query Jungle
// Contest: Codeforces - Squarepoint Challenge (Codeforces Round 1055, Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/2152/problem/G
// Memory Limit: 1024 MB
// Time Limit: 3000 ms//#pragma GCC optimize(2,3,"Ofast","inline","unroll-loops")
//#pragma GCC optimize("-Ofast", "-finline", "-funroll-loops", "-fno-stack-protector")
//#pragma GCC target("avx")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){ll x=0; bool f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=0; ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();}return f?x:-x;
}
inline void write(ll x){if(x<0) x=-x,putchar('-');if(x>9) write(x/10);putchar('0'+x%10);
}
const ll N=500009;
vector<ll> to[N];
ll n,a[N];
ll tI[N],tO[N],timer;
ll tag[N];
void dfs(ll u,ll fa){tI[u]=++timer;if(a[u]) tag[timer]=2;else tag[timer]=0;for(ll v:to[u]){if(v==fa) continue;dfs(v,u);}tO[u]=++timer;if(a[u]) tag[timer]=3;else tag[timer]=1;
}
struct Segment{ll len01,len10,len23,len32,lazy;
} tr[N*4];
inline void pushtag(ll u){tr[u].lazy^=1;swap(tr[u].len01,tr[u].len23);swap(tr[u].len10,tr[u].len32);
}
inline void pushdown(ll u){if(!tr[u].lazy) return;pushtag(u*2),pushtag(u*2+1);tr[u].lazy=0;
}
inline void pushup(ll u){// 01if(tr[u*2].len01%2==0){tr[u].len01=tr[u*2].len01+tr[u*2+1].len01;if(tr[u*2].len01>0)tr[u].len01=max(tr[u].len01,tr[u*2].len01-1+tr[u*2+1].len10);}else{tr[u].len01=tr[u*2].len01+tr[u*2+1].len10;if(tr[u*2].len01>0)tr[u].len01=max(tr[u].len01,tr[u*2].len01-1+tr[u*2+1].len01); }// 10if(tr[u*2].len10%2==0){tr[u].len10=tr[u*2].len10+tr[u*2+1].len10;if(tr[u*2].len10>0)tr[u].len10=max(tr[u].len10,tr[u*2].len10-1+tr[u*2+1].len01);}else{tr[u].len10=tr[u*2].len10+tr[u*2+1].len01;if(tr[u*2].len10>0)tr[u].len10=max(tr[u].len10,tr[u*2].len10-1+tr[u*2+1].len10); }// 23if(tr[u*2].len23%2==0){tr[u].len23=tr[u*2].len23+tr[u*2+1].len23;if(tr[u*2].len23>0)tr[u].len23=max(tr[u].len23,tr[u*2].len23-1+tr[u*2+1].len32);}else{tr[u].len23=tr[u*2].len23+tr[u*2+1].len32;if(tr[u*2].len23>0)tr[u].len23=max(tr[u].len23,tr[u*2].len23-1+tr[u*2+1].len23); }// 32if(tr[u*2].len32%2==0){tr[u].len32=tr[u*2].len32+tr[u*2+1].len32;if(tr[u*2].len32>0)tr[u].len32=max(tr[u].len32,tr[u*2].len32-1+tr[u*2+1].len23);}else{tr[u].len32=tr[u*2].len32+tr[u*2+1].len23;if(tr[u*2].len32>0)tr[u].len32=max(tr[u].len32,tr[u*2].len32-1+tr[u*2+1].len32); }
}
void build(ll u,ll l,ll r){tr[u].lazy=tr[u].len01=tr[u].len10=tr[u].len23=tr[u].len32=0;if(l==r){if(tag[l]==0) tr[u].len01=1;else if(tag[l]==1) tr[u].len10=1;else if(tag[l]==2) tr[u].len23=1;else if(tag[l]==3) tr[u].len32=1;return;}ll mid=(l+r)/2;build(u*2,l,mid);build(u*2+1,mid+1,r);pushup(u);
}
void upd(ll u,ll l,ll r,ll ql,ll qr){if(ql<=l&&r<=qr){pushtag(u);return;}pushdown(u);ll mid=(l+r)/2;if(ql<=mid) upd(u*2,l,mid,ql,qr);if(mid<qr) upd(u*2+1,mid+1,r,ql,qr);pushup(u);
}
inline ll ask(){ll res=tr[1].len23;return res/2;
}
void solve(){n=read();for(ll i=1;i<=n;i++){a[i]=read();to[i].clear();}for(ll i=1;i<=n-1;i++){ll u=read(),v=read();to[u].emplace_back(v);to[v].emplace_back(u);}timer=0;dfs(1,0);build(1,1,2*n);printf("%lld\n",ask());ll q=read();while(q--){ll u=read();upd(1,1,2*n,tI[u],tO[u]);printf("%lld\n",ask());}
}
int main(){ll T=read();while(T--){solve();}return 0;
}