WC2024 游记&题解

· · 个人记录

DAY -2

篮球，乒乓球，羽毛球，足球，gen，开幕式，gen，睡觉

DAY -1

冬眠，gen，冬眠，足球，乒乓球，gen，哦论文交流还挺有意思，gen，睡觉

DAY 0

选讲ez，gen，懒得听课了，羽毛球，gen，睡觉

DAY 1

T1 怎么那么傻逼啊。

T2 怎么那么傻逼啊。

T3 好神秘。T3 好神秘。哦我会特殊性质。

T3 好神秘。T3 好神秘。哦我会 m=1 了。哦我会 m\le 5 了。

哦我会 n\le 5000 了。最后一档是不是要用我们 qoj5425 的方法啊！

然后再线段树合并一下。

开摆了。100+100+85

查分，没挂

听评讲，怎么直接跳过划分等价类的部分了。

诶是不是直接哈希就行了？？？？？？唐完了。

坤皇指出这个划分等价类在 CF1830C 里也有，而且我当时写的是 O(n\log n) 的确定性做法，具体似乎是线段树优化建图。

题解

T1

正着一遍背包，倒着一遍背包

T2

线段树优化 dp 即可

T3

思考 m=1 的做法。考虑不要管它给定的是一个区间，当成是一个普通的集合。

对于每个节点，你发现我们必须得知道 X=\sum\limits_{x\in S\cap [L,R)}a_x 或者 Y=\sum\limits_{x\in [L,R)}a_x-\sum\limits_{x\in S\cap [L,R)}a_x ，因为你通过外面的节点能得到的信息只有 \sum\limits_{x\in [L,R)}a_x 。继续思考，如果知道了 \sum\limits_{x\in [L,R)}a_x ，那一定是同时知道 X,Y ，否则就不合法了。若不知道 \sum\limits_{x\in [L,R)}a_x ，那一定是知道 X,Y 中的一个。

于是只有 3 种状态，直接 dp 即可。

进一步思考 m\le 5 ，只有 2^m+1 种状态，即 f(x,S) 和 g(x) ，且不存在 f(ls,x)f(rs,y)(x\neq y) 的情况，所以可以做到 O(n2^m) 。

更进一步的，你发现可能的 S 是不多的。记 s_i 是哪些区间包含了 i ，根据转移的形式，f(u,x) 中的 x 只可能是 u 子树中的某个 s_i ，这样就是 O(n^2) 的了。

怎么优化到 O(n\log n) 呢？可以线段树合并优化 dp 的过程。

问：怎么快速区分不同的 s_i 呢？

错误答案：这不是我们 qoj 5425 吗，你维护一下双向链表用线段树维护一下再启发式分裂一下！

正确答案：哈希即可。

贴个后来写的代码

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,X[200100],m,step;
#define ull unsigned long long
ull cf[200100],qc[200100];
int ls[12010000],rs[12001000],T[401000],f[400100],ne,cn,su[12010000];
int tg[12001000];
mt19937 rnd(time(0));
void up(int &o,int l,int r,int x){
    o=++cn,tg[o]=su[o]=1;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(x<=mid)up(ls[o],l,mid,x);
    else up(rs[o],mid+1,r,x);
}
int px,py,so;
void ad(int x,int z){if(!x)return;tg[x]=1ll*tg[x]*z%mod;su[x]=1ll*su[x]*z%mod;}
void pd(int x){ad(ls[x],tg[x]),ad(rs[x],tg[x]),tg[x]=1;}
int merge(int x,int y,int l,int r){
    if(!x&&!y)return 0;
    if(!x||!y){
        if(!x)ad(y,px);else ad(x,py);
        return x+y;
    }
    if(l==r){
        (so+=1ll*su[x]*su[y]%mod)%=mod;
        su[x]=(1ll*su[x]*py+1ll*su[y]*px+1ll*su[x]*su[y])%mod;
        return x;
    }
    pd(x),pd(y);int mid=(l+r)>>1;
    ls[x]=merge(ls[x],ls[y],l,mid);
    rs[x]=merge(rs[x],rs[y],mid+1,r);
    su[x]=(su[ls[x]]+su[rs[x]])%mod;
    return x;
}
int dfs(int l,int r){
    int u=++ne;
    if(l+1==r){
        int o=lower_bound(qc+1,qc+m+1,cf[l])-qc;
        f[u]=1;up(T[u],1,m,o);return u;
    }
    int mi=X[++step],ls=dfs(l,mi),rs=dfs(mi,r);
    px=f[ls],py=f[rs],f[u]=2ll*px*py%mod;
    (f[u]+=1ll*px*su[T[rs]]%mod)%=mod;
    (f[u]+=1ll*py*su[T[ls]]%mod)%=mod;
    so=0,T[u]=merge(T[ls],T[rs],1,m);
    (f[u]+=so)%=mod;
    return u;
}
int ask(int p,int l,int r,int x){
    if(!p)return 0;if(l==r)return su[p];
    pd(p);int mid=(l+r)>>1;
    if(x<=mid)return ask(ls[p],l,mid,x);
    return ask(rs[p],mid+1,r,x);
}
int main(){
    int md;
    scanf("%d%d",&n,&md);
    for(int i=1;i<n;i++)scanf("%d",&X[i]);
    for(int i=1,l,r;i<=md;i++){
        scanf("%d%d",&l,&r);ull e=rnd()*rnd()*rnd();
        cf[l]^=e,cf[r]^=e;
    }
    for(int i=1;i<n;i++)cf[i]^=cf[i-1];
    for(int i=0;i<n;i++)qc[++m]=cf[i];sort(qc+1,qc+m+1);m=unique(qc+1,qc+m+1)-qc-1;
    dfs(0,n);
    int ans=f[1];
    for(int i=1;i<=m;i++)if(qc[i]==0)(ans+=ask(T[1],1,m,i))%=mod;
    return printf("%d",ans),0;
}