A.origen

先前缀和，以下 \(p_i\) 表示前缀异或和。

考虑将一个数 \(k\) 二进制差分，假设拆成 \(2^a+2^b+2^c\)，则 \(k^2=(2^a+2^b+2^c)\times(2^a+2^b+2^c)\)，也就是指数两两结合。

所以一个数的平方就相当于 \(k^2=\sum\limits_{i=0}^{\lfloor\log_2{k^2}\rfloor} 2^i\times \sum\limits_{j=0}^{i} [k\operatorname{bitand} 2^j][k\operatorname{bitand} 2^{i-j}]\)。所以我们考虑统计所有原序列子区间异或和的第 \(x\) 位与第 \(y\) 位。

设 \(f_{i,x,y,0/1,0/1}\) 为在 \(1\sim i\) 当中，\(a_i\) 的第 \(x,y\) 二进制位为 \(0/1,0/1\) 的个数，\(ans_i\) 为所有 \(k^2\) 中 \(2^i\) 的个数。

设 \(w1=[p_i\operatorname{bitand} 2^x],w2=[p_i\operatorname{bitand} 2^y]\)。

有转移 \(ans_{x+y}=ans_{x+y}+f_{i-1,x,y,w1\oplus 1,w2\oplus 1},f_{i,x,y,w1,w2}=f_{i-1,x,y,w1,w2}+1\)。

最后统计答案即可，第一维可滚掉，时间复杂度 \(O(n\log^2 n)\)。

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=2e5+10,MOD=998244353;
int n,a[MAXN];long long ans[50],f[20][20][2][2];
int main()
{
    freopen("origen.in","r",stdin);
    freopen("origen.out","w",stdout);
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n;for(int i=1;i<=n;++i) cin>>a[i],a[i]^=a[i-1];
    for(int x=0;x<18;++x)
        for(int y=0;y<18;++y)
            f[x][y][0][0]=1;
    for(int i=1;i<=n;++i)
    {
        for(int x=0;x<18;++x)
            for(int y=0;y<18;++y)
            {
                ans[x+y]+=f[x][y][(a[i]>>x)&1^1][(a[i]>>y)&1^1];
                f[x][y][(a[i]>>x)&1][(a[i]>>y)&1]++;
                ans[x+y]%=MOD;
            }
    }
    long long ANS=0,P=1;
    for(int i=0;i<36;++i)
    {
        ANS+=P*ans[i]%MOD;
        P=P*2%MOD;
    }
    cout<<ANS%MOD<<'\n';return 0;
}

B.competition

考虑统计所有组“每组中不能做出来的题数之和”\(sum\)，记总组数 \(N=\dfrac{n(n+1)}{2}\)，最终答案为 \(\dfrac{Nm-sum}{N}\)。

如果你从 \(1\to n\) 扫描，维护出来每道题最后能做出来的时间 \(t_i\)，那么你选择的以 \(i\) 结尾的区间的不能做出来的题数之和就等于 \(im-\sum\limits_{j=1}^{m} t_j\)，（\(im\) 因为有 \(i\) 个区间）。

要维护全局和，区间赋值，线段树即可，动态开点被卡空间，离散化即可。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int MAXN=1e6+10,MOD=1e9+7;
int n,cnt=1,tot,p;ll m,l[MAXN],r[MAXN],ans;
ll a[MAXN<<1],b[MAXN<<2],len[MAXN<<2];
struct tree{int num,add,len;}t[MAXN<<4];
void build(ll l,ll r,int p)
{
    if(l==r){t[p].len=len[l];return ;}
    ll mid=(l+r)>>1;
    build(l,mid,p<<1),build(mid+1,r,p<<1|1);
    t[p].len=(t[p<<1].len+t[p<<1|1].len)%MOD;return ;
}
inline void change(ll l,ll r,int p,ll x,ll y,ll z)
{
    if(x<=l&&y>=r)
    {
        t[p].num=1ll*t[p].len*z%MOD;
        t[p].add=z;return ;
    }
    ll mid=(l+r)>>1;
    if(t[p].add)
    {
        t[p<<1].num=1ll*t[p<<1].len*t[p].add%MOD;
        t[p<<1|1].num=1ll*t[p<<1|1].len*t[p].add%MOD;
        t[p<<1].add=t[p].add,t[p<<1|1].add=t[p].add;
        t[p].add=0;
    }
    if(x<=mid) change(l,mid,p<<1,x,y,z);
    if(y>mid) change(mid+1,r,p<<1|1,x,y,z);
    t[p].num=(t[p<<1].num+t[p<<1|1].num)%MOD;return ;
}
inline long long ksm(long long a,int b)
{
    long long ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%MOD;
        a=a*a%MOD,b>>=1;
    }
    return ans;
}
int main()
{
    freopen("competition.in","r",stdin);
    freopen("competition.out","w",stdout);
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>l[i]>>r[i],a[++tot]=l[i],a[++tot]=r[i];
    a[++tot]=0,a[++tot]=m;sort(a+1,a+1+tot);
    for(int i=1;i<=tot;++i)
    {
        if(i!=1&&a[i]==a[i-1]) continue;
        if(i!=1&&a[i]!=a[i-1]+1)
            b[++p]=a[i-1]+1,len[p]=(a[i]-a[i-1]-1)%MOD;
        b[++p]=a[i],len[p]=1;
    }
    for(int i=1;i<=n;++i)
        l[i]=lower_bound(b+1,b+1+p,l[i])-b,
        r[i]=lower_bound(b+1,b+1+p,r[i])-b;
    build(1,p,1);
    for(int i=1;i<=n;++i)
    {
        change(1,p,1,l[i],r[i],i);
        ans+=(m%MOD*i%MOD-t[1].num+MOD)%MOD;
    }
    ll N=1ll*n*(n+1)/2%MOD;
    cout<<(m%MOD*N%MOD-ans%MOD+MOD)%MOD*ksm(N,MOD-2)%MOD<<'\n';
    return 0;
}

C.tour

发现最多连成一棵树，每次就是在森林中选取两个树合并。

拆路径，记 \(L=lca(x,y)\)，\(x\to y\) 拆成 \(x\to L,L\to y\)。

记 \(dis_i\) 为 \(i\) 到根路径上的权值和。

第一段 \(i\in x\to L\) 满足条件，等价于 \(dis_x-dis_i\geq a_i\)。

第二段 \(i\in L\to y\) 满足条件，等价于 \((dis_x-dis_L+a_L)+(dis_i-dis_L-a_i)\geq a_i\)。

移项，主席树维护点到根信息，转换成树链上小于等于某个数个数。合并启发式合并暴力重构，感觉平凡，但我赛时没想到。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int MAXN=1e5+10,INF=500010000;
int testmode,lastans,n,q,a[MAXN],dis[MAXN];
int dep[MAXN],f[MAXN][20],fa[MAXN],siz[MAXN];
vector <int> v[MAXN];
struct segment_tree
{
    int root[MAXN],cnt;
    struct tree{int num,ls,rs;}t[MAXN<<8];
    inline void change(int l,int r,int p,int q,int x)
    {
        t[q].ls=t[p].ls,t[q].rs=t[p].rs;
        if(l==r){t[q].num=t[p].num+1;return ;}
        int mid=(l+r)>>1;
        if(x<=mid) change(l,mid,t[p].ls,t[q].ls=++cnt,x);
        else change(mid+1,r,t[p].rs,t[q].rs=++cnt,x);
        t[q].num=t[t[q].ls].num+t[t[q].rs].num;return ;
    }
    inline int query(int l,int r,int p,int q,int x,int y)
    {
        if(x<=l&&y>=r) return t[q].num-t[p].num;
        int mid=(l+r)>>1,ans=0;
        if(x<=mid) ans+=query(l,mid,t[p].ls,t[q].ls,x,y);
        if(y>mid) ans+=query(mid+1,r,t[p].rs,t[q].rs,x,y);
        return ans;
    }
}X,Y;
inline void work(int i,int fa)
{
    X.change(-INF,INF,X.root[fa],X.root[i]=++X.cnt,a[i]+dis[i]);
    Y.change(-INF,INF,Y.root[fa],Y.root[i]=++Y.cnt,2*a[i]-dis[i]);
    return ;
}
inline int lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y]) x=f[x][__lg(dep[x]-dep[y])];
    if(x==y) return x;
    for(register int i=__lg(dep[x]);i>=0;--i)
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
void dfs(int x,int fa=0)
{
    for(int i=0;i<=__lg(dep[x]);++i) f[x][i]=0;
    dep[x]=dep[fa]+1,dis[x]=dis[fa]+a[x];
    f[x][0]=fa,work(x,fa);
    for(int i=1;i<=__lg(dep[x]);++i)
        f[x][i]=f[f[x][i-1]][i-1];
    for(int y:v[x]) if(y!=fa) dfs(y,x);
    return ;
}
inline int find(int x){return (x==fa[x])?x:fa[x]=find(fa[x]);}
int main()
{
    freopen("tour.in","r",stdin);
    freopen("tour.out","w",stdout);
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>testmode>>n>>q;
    for(int i=1;i<=n;++i)
        cin>>a[i],dep[i]=1,dis[i]=a[i],work(i,0),fa[i]=i,siz[i]=1;
    while(q--)
    {
        int opt,x,y;cin>>opt>>x>>y;
        if(testmode) x^=lastans,y^=lastans;
        if(opt==0)
        {
            v[x].push_back(y),v[y].push_back(x);
            int fax=find(x),fay=find(y);
            if(siz[fax]<siz[fay]) swap(x,y),swap(fax,fay);
            siz[fax]+=siz[fay],fa[fay]=fax,dfs(y,x);
        }
        else
        {
            int L=lca(x,y),ans=0;
            ans+=X.query(-INF,INF,X.root[f[L][0]],X.root[x],-INF,dis[x]);
            ans+=Y.query(-INF,INF,Y.root[L],Y.root[y],-INF,dis[x]+a[L]-2*dis[L]);
            cout<<(lastans=ans)<<'\n';
        }
    }
    return 0;
}