正睿 CSP 七连测 Day2 Oblivion 设 $dp_i$ 表示仅考虑 $1$ 到 $i$ 且 $i$ 邪恶的方案数。考虑枚举一个左端点 $j$，表示 $j$ 到 $i$ 中的人都是善良的，那方案合法当且仅当 $j$ 到 $\lfloor \frac{i+j}{2}\rfloor $ 中所有有指向的都为 L，$\lfloor \frac{i+j}{2}\rfloor +1$ 到 $i $ 中所有有指向的都为 R。同样需要考虑 $i$ 作为第一个邪恶的人的方案数，只需满足 $i$ 以前的所有有指向的人都指向 R 即可。$dp_i$ 对答案产生贡献当且仅当 $i+1$ 到 $n$ 所有有指向的人都指向 L 。复杂度 $O(n^2)$。 考虑进行一些优化，对于这个 $j$ 的统计，我们转换一下思维，设 $l_i$ 表示从 $1$ 到 $n$ 中下标最大的 L，$r_i$ 表示 $i$ 到 $n$ 中下标最小的 R。对于一个符合条件的 $j$，一定有： $$\begin{cases}2l_{i-1}\le i+j \\2r_{j+1}i+j\end{cases}$$ 稍微移项一下就可以得到一个很好用 BIT 维护的差分关系，代码如下： C++#include using namespace std; #define int long long const int N=1e6+5; const int mod=998244353; int n,ans; int suml[N],sumr[N],l[N],r[N],dp[N]; char c[N]; vector g[N]; struct BIT{ int tr[N]; void add(int x,int k){ for(;x0;x-=x&-x) (res+=tr[x])%=mod; return res; } }bit; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cinn; for(int i=1;ic[i]; l[i]=(c[i]=='L'?i:l[i-1]); suml[i]=suml[i-1]+(c[i]=='L'); sumr[i]=sumr[i-1]+(c[i]=='R'); } r[n+1]=n+1; for(int i=n;i=1;i--) r[i]=(c[i]=='R'?i:r[i+1]); for(int i=1;i1; // if(!(sumr[mid]-sumr[j])&&!(suml[i-1]-suml[mid])) (dp[i]+=dp[j])%=mod; // } (dp[i]+=bit.get(i)-bit.get(2*l[i-1]-i-1))%=mod; (dp[i]+=mod)%=mod; if(suml[i]==suml[i-1]&&sumr[i]==sumr[i-1]) (dp[i]#include using namespace std; #define int long long const int N=1e6+5; const int mod=998244353; int n,ans; int suml[N],sumr[N],l[N],r[N],dp[N]; char c[N]; vectorint g[N]; struct BIT{ int tr[N]; void add(int x,int k){ for(;xn;x+=x&-x) (tr[x]+=k)%=mod; } int get(int x){ if(x0) return 0; int res=0; for(;x0;x-=x&-x) (res+=tr[x])%=mod; return res; } }bit; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cinn; for(int i=1;in;i++){ cinc[i]; l[i]=(c[i]=='L'?i:l[i-1]); suml[i]=suml[i-1]+(c[i]=='L'); sumr[i]=sumr[i-1]+(c[i]=='R'); } r[n+1]=n+1; for(int i=n;i=1;i--) r[i]=(c[i]=='R'?i:r[i+1]); for(int i=1;in;i++){ for(int x:g[i]) bit.add(x,-dp[x]); if(!suml[i-1]) dp[i]=1; // for(int j=1;j // int mid=(i+j)1; // if(!(sumr[mid]-sumr[j])&&!(suml[i-1]-suml[mid])) (dp[i]+=dp[j])%=mod; // } (dp[i]+=bit.get(i)-bit.get(2*l[i-1]-i-1))%=mod; (dp[i]+=mod)%=mod; if(suml[i]==suml[i-1]&&sumr[i]==sumr[i-1]) (dp[i]1)%=mod; bit.add(i,dp[i]); if(2*r[i+1]-in) g[2*r[i+1]-i].push_back(i); if(!(sumr[n]-sumr[i])) (ans+=dp[i])%=mod; } cout(ans%mod+mod)%mod; return 0; } 正睿 NOIP 十连测 Day1 序列 按值从大到小进行枚举，设当前所有数中位置最左和最右分别为 $l$，$r$，并且枚举了 $x$ 个数，那有答案为 $r-l+1-x+2$ 树 考虑树上主席树，这个主席树存的是颜色编号区间内各个颜色数量的信息，这样的话答案就可以二分去找了。但是这个信息直接存储的话应该是一个数组，考虑给每个颜色赋一个随机数权值，比较权值即可。 代码： C++#include using namespace std; #define int long long #define ls(p) (tr[(p)].l) #define rs(p) (tr[(p)].r) const int N=3e5+5; int n,q,idx; int rt[N],col[N],dep[N],val[N],fa[N][20]; vector g[N]; struct tree{ int l,r,sum; }tr[N*60]; mt19937_64 rnd(rand()); void read(int &x){ int f=1; x=0; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c='0'&&c1; if(x=0;i--) if(dep[fa[u][i]]=dep[v]) u=fa[u][i]; if(u==v) return u; for(int i=19;i=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0]; } int solve(int u1,int v1,int l1,int f1,int u2,int v2,int l2,int f2,int l,int r){ if(l==r) return l-1; int h1=tr[ls(u1)].sum+tr[ls(v1)].sum-tr[ls(l1)].sum-tr[ls(f1)].sum, h2=tr[ls(u2)].sum+tr[ls(v2)].sum-tr[ls(l2)].sum-tr[ls(f2)].sum; int mid=(l+r)1; if(h1!=h2) return solve(ls(u1),ls(v1),ls(l1),ls(f1),ls(u2),ls(v2),ls(l2),ls(f2),l,mid); else return solve(rs(u1),rs(v1),rs(l1),rs(f1),rs(u2),rs(v2),rs(l2),rs(f2),mid+1,r); } signed main(){ read(n); for(int i=1,u,v;i#include using namespace std; #define int long long #define ls(p) (tr[(p)].l) #define rs(p) (tr[(p)].r) const int N=3e5+5; int n,q,idx; int rt[N],col[N],dep[N],val[N],fa[N][20]; vectorint g[N]; struct tree{ int l,r,sum; }tr[N*60]; mt19937_64 rnd(rand()); void read(int &x){ int f=1; x=0; char c=getchar(); while(c'0'||c'9'){ if(c=='-') f=-1; c=getchar(); } while(c='0'&&c'9') x=(x1)+(x3)+(c^48),c=getchar(); x*=f; } int insert(int f,int l,int r,int x){ int p=++idx; tr[p]=tr[f],tr[p].sum+=val[x]; if(l==r) return p; int mid=(l+r)1; if(xmid) ls(p)=insert(ls(f),l,mid,x); else rs(p)=insert(rs(f),mid+1,r,x); return p; } void dfs(int u,int f){ fa[u][0]=f,dep[u]=dep[f]+1; rt[u]=insert(rt[f],1,n,col[u]); for(int i=1;i20;i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(int v:g[u]){ if(v==f) continue; dfs(v,u); } } int lca(int u,int v){ if(dep[u]dep[v]) swap(u,v); for(int i=19;i=0;i--) if(dep[fa[u][i]]=dep[v]) u=fa[u][i]; if(u==v) return u; for(int i=19;i=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0]; } int solve(int u1,int v1,int l1,int f1,int u2,int v2,int l2,int f2,int l,int r){ if(l==r) return l-1; int h1=tr[ls(u1)].sum+tr[ls(v1)].sum-tr[ls(l1)].sum-tr[ls(f1)].sum, h2=tr[ls(u2)].sum+tr[ls(v2)].sum-tr[ls(l2)].sum-tr[ls(f2)].sum; int mid=(l+r)1; if(h1!=h2) return solve(ls(u1),ls(v1),ls(l1),ls(f1),ls(u2),ls(v2),ls(l2),ls(f2),l,mid); else return solve(rs(u1),rs(v1),rs(l1),rs(f1),rs(u2),rs(v2),rs(l2),rs(f2),mid+1,r); } signed main(){ read(n); for(int i=1,u,v;in;i++){ read(u),read(v); g[u].push_back(v); g[v].push_back(u); } for(int i=1;in;i++) read(col[i]),val[i]=rnd(); dfs(1,0); read(q); while(q--){ int u1,v1,u2,v2; read(u1),read(v1),read(u2),read(v2); int l1=lca(u1,v1),l2=lca(u2,v2),f1=fa[l1][0],f2=fa[l2][0]; int h1=tr[rt[u1]].sum+tr[rt[v1]].sum-tr[rt[l1]].sum-tr[rt[f1]].sum, h2=tr[rt[u2]].sum+tr[rt[v2]].sum-tr[rt[l2]].sum-tr[rt[f2]].sum; if(h1==h2){ printf("%d\n",n); continue; } printf("%d\n",solve(rt[u1],rt[v1],rt[l1],rt[f1],rt[u2],rt[v2],rt[l2],rt[f2],1,n)); } return 0; } 六元组 设三架飞机按停放机场排序后为 $x_a $$\begin{cases}x_b\in[l_a,r_a]\\x_c\in[l_b,r_b]\\x_a\in[l_c,r_c]\end{cases}$$ 考虑枚举 $b$，先算所有 $b\to c$ 的贡献，再算 $a\to b$ 的传递，最后对每个 $c$ 查询 $x_a\in[l_c,r_c]$ 的总贡献。 具体地，把飞机按 $x$ 排序后离散化区间，分块预处理 $f[k][i][j]$ 表示从块 $i$ 出发经过 $k$ 次向右传递后对位置 $j$ 的贡献。$k=0$ 时块内每个点初始为 $1$，$k=1$ 时每个 $b$ 对它区间内的点贡献 $+1$，$k=2$ 时每个 $a$ 对它区间内的点贡献 $+1$。 扫描线枚举 $c$，用差分数组维护当前所有 $a$ 的贡献，整块直接加 $f[2][j][i]$，散块暴力查询差分即可。复杂度 $O(m\sqrt m)$。代码： C++#include using namespace std; const int N=2e5+5,B=450; int n,m,bl; long long ans; int t[N],l[N],r[N],val[N],tag[N],f[3][N/B+5][N]; vector v[N]; struct node{ int x,l,r; }a[N]; bool cmp(node a,node b){ return a.xnm; bl=(m+B-1)/B; for(int i=1;ia[i].xa[i].la[i].r,a[i].r++; sort(a+1,a+m+1,cmp); for(int i=1;i#include using namespace std; const int N=2e5+5,B=450; int n,m,bl; long long ans; int t[N],l[N],r[N],val[N],tag[N],f[3][N/B+5][N]; vectorpairint,int v[N]; struct node{ int x,l,r; }a[N]; bool cmp(node a,node b){ return a.xb.x; } void add(int x,int v){ int b=(x-1)/B+1; for(int i=1;ib;i++) tag[i]+=v; for(int i=(b-1)*B+1;ix;i++) val[i]+=v; } int query(int x){ return tag[(x-1)/B+1]+val[x]; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cinnm; bl=(m+B-1)/B; for(int i=1;im;i++) cina[i].xa[i].la[i].r,a[i].r++; sort(a+1,a+m+1,cmp); for(int i=1;im;i++) t[i]=a[i].x; for(int i=1;im;i++){ l[i]=lower_bound(t+1,t+m+1,a[i].l)-t; r[i]=lower_bound(t+1,t+m+1,a[i].r)-t; v[l[i]].push_back({i,1}); v[r[i]].push_back({i,-1}); } for(int i=1;ibl;i++){ for(int j=(i-1)*B+1;jmin(i*B,m);j++) f[0][i][j]=1; for(int k=1;k2;k++){ for(int j=1;jm;j++){ f[k][i][l[j]]+=f[k-1][i][j]; f[k][i][r[j]]-=f[k-1][i][j]; } for(int j=1;jm;j++) f[k][i][j+1]+=f[k][i][j]; } } for(int i=1;im;i++){ for(auto p:v[i]) add(p.first,p.second); int L=(l[i]-1)/B+1,R=(r[i]-1)/B+1; for(int j=L;jR;j++) ans+=f[2][j][i]; for(int j=(L-1)*B+1;jl[i];j++) ans-=query(l[j])-query(r[j]); for(int j=(R-1)*B+1;jr[i];j++) ans+=query(l[j])-query(r[j]); } coutans"\n"; return 0; }
2026.9.9近期比赛
ooliver