2026.9.9 - 近期比赛

2026年9月9日 ooliver OI

正睿 CSP 七连测 Day2

Oblivion

设 $d p_{i}$ 表示仅考虑 $1$ 到 $i$ 且 $i$ 邪恶的方案数。考虑枚举一个左端点 $j$ ，表示 $j$ 到 $i$ 中的人都是善良的，那方案合法当且仅当 $j$ 到 $\lfloor \frac{i+j}{2}\rfloor $ 中所有有指向的都为 L， $⌊ \frac{i + j}{2} ⌋ + 1$ 到 $i $ 中所有有指向的都为 R。同样需要考虑 $i$ 作为第一个邪恶的人的方案数，只需满足 $i$ 以前的所有有指向的人都指向 R 即可。 $d p_{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);
    cin>>n;
    for(int i=1;i>c[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;i>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]

`#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(;x>0;x-=x&-x) (res+=tr[x])%=mod;
        return res;
    }
}bit;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;in;i++){
        cin>>c[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'&&c>1;
    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.x>n>>m;
    bl=(m+B-1)/B;
    for(int i=1;i>a[i].x>>a[i].l>>a[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);
    cin>>n>>m;
    bl=(m+B-1)/B;
    for(int i=1;im;i++) cin>>a[i].x>>a[i].l>>a[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;
}`