多校省选联测22，24

标签：24 省选 ll 多校 int maxn dis top define

多校省选联测24

拱火

发现一条边两侧点的数目都为奇数时这条边产生 $ 1 $ 的贡献

为了保证合法我们每次加入两个点一共需要跑两次

对每一条边维护一颗线段树

如果对于一条边来说第r次加入的两个点在边两侧该叶子的值就为1

那么该边产生的所有贡献就是所有子区间的异或和即$ \sum_{l=1}^n \sum_{r=l}^n \oplus_{i=l}^{r} a_i $

考虑这个东西可以用扫描线搞每次第 $ r $ 次加入时计算每一个区间右端点为 $ r $ 的区间的贡献

此时复杂度为 $ O(n^2\log n) $

考虑优化线段树此时维护的是后缀异或和那么如果我们加入一个0 贡献不变第 $ r $ 次加入一个1时贡献从 $ sum $ 变为 $ (r-1)-sum+1=r-sum $

每次加入两个点时只有两点之间路径上的点（去掉LCA）会加入1 树剖维护区间加区间取负操作即可

总结：扫描线+贡献分析

code

#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#define Sakura int
#define Re register ll
#define _ putchar(' ')
#define el putchar('\n')
#define ll long long
#define fre(x,y) freopen(#x".in","r",stdin),freopen(#y".out","w",stdout);

using namespace std;

const ll maxn=5e5+10;

inline ll read(){
    ll x=0,f=0;char c=getchar();
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}

inline void ot(ll x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) ot(x/10);putchar(x%10|48);
}

vector<ll> G[maxn];
ll n;
ll dfn[maxn],dep[maxn],top[maxn],fa[maxn],size[maxn],son[maxn],tim;
ll ans;

struct Seg {
    ll sum[maxn<<2];
    ll add_tag[maxn<<2];
    bool rev_tag[maxn<<2];

    void empty(ll p,ll l,ll r) {
        sum[p]=add_tag[p]=rev_tag[p]=0;
        if(l==r) return;
        ll mid=l+r>>1;
        empty(p<<1,l,mid);
        empty(p<<1|1,mid+1,r);
    }

    inline void reverse(ll p) {
        rev_tag[p]^=1;
        sum[p]*=-1;
        add_tag[p]*=-1;
    }

    inline void add(ll p,ll len,ll x) {
        sum[p]+=x*len;
        add_tag[p]+=x;
    }

    inline void pushup(ll p) {
        sum[p]=sum[p<<1]+sum[p<<1|1];
    }

    inline void pushdown(ll p,ll l,ll r) {
        if(rev_tag[p]) {
            reverse(p<<1);
            reverse(p<<1|1);
            rev_tag[p]=false;
        }
        if(add_tag[p]) {
            ll mid=l+r>>1;
            add(p<<1,mid-l+1,add_tag[p]);
            add(p<<1|1,r-mid,add_tag[p]);
            add_tag[p]=0;
        }
    }

    void rev(ll p,ll l,ll r,ll L,ll R) {
        if(L>R) return;
        if(L<=l&&r<=R) return reverse(p);
        pushdown(p,l,r);
        ll mid=l+r>>1;
        if(L<=mid) rev(p<<1,l,mid,L,R);
        if(mid<R) rev(p<<1|1,mid+1,r,L,R);
        pushup(p);
    }

    void upd(ll p,ll l,ll r,ll L,ll R,ll x) {
        if(L>R) return;
        if(L<=l&&r<=R) return add(p,r-l+1,x);
        pushdown(p,l,r);
        ll mid=l+r>>1;
        if(L<=mid) upd(p<<1,l,mid,L,R,x);
        if(mid<R) upd(p<<1|1,mid+1,r,L,R,x);
        pushup(p);
    }
}tree;

inline void add(ll x,ll y) {
    G[x].emplace_back(y);
}

inline void add_edge(ll x,ll y) {
    add(x,y);
    add(y,x);
}

void dfs1(ll u) {
    dep[u]=dep[fa[u]]+1;
    size[u]=1;
    for(auto v:G[u])
        if(v!=fa[u]) {
            fa[v]=u;
            dfs1(v);
            if(size[v]>size[son[u]]) son[u]=v;
            size[u]+=size[v];
        }
}

void dfs2(ll u,ll topf) {
    top[u]=topf;
    dfn[u]=++tim;
    if(son[u]) dfs2(son[u],topf);
    for(auto v:G[u]) if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
}

inline void upd(ll x,ll y,ll z) {
    // ot(x),_,ot(y),_,ot(z),el;
    while(top[x]!=top[y]) {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        tree.rev(1,1,n,dfn[top[x]],dfn[x]);
        tree.upd(1,1,n,dfn[top[x]],dfn[x],z);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y]) swap(x,y);
    tree.rev(1,1,n,dfn[y]+1,dfn[x]);
    tree.upd(1,1,n,dfn[y]+1,dfn[x],z);
}

inline void solve(ll st) {
    for(Re i=st,d=1;i<n;i+=2,d++) {
        upd(i,i+1,d);
        ans+=tree.sum[1];
    }
}

Sakura main() {
    fre(fire,fire);
    n=read();
    for(Re i=1;i<n;++i) add_edge(read(),read());
    dfs1(1);
    dfs2(1,1);
    solve(1);
    tree.empty(1,1,n);
    solve(2);
    ot(ans);
}

卷积之王

sto Kaguya orz

考虑 $ max $ 这个操作似乎不可以 $ DFT $ （反正我不会

考虑按最高位是 $ 0 $ 还是 $ 1 \quad $ 将两个序列分别拆为 $ A,B $ 和 $ C,D \quad $ $ A,C $ 最高位为 $ 1 $

显然去掉最高位 $ A,B \quad $ $ C,D $ 分别同构

那么卷积出来最高位为 $ 0 $ 的部分显然只能由 $ B * D $ 得到

最高位为 $ 1 $ 的可以由 $ A * C ,A * D, C * B $ 得到

由于同构发现 $ \max( A * C ,A * D ) = A * \max( C ,D) $

这样上述三次计算可以合并成两次

复杂度：$ T(n) = 3T ( \frac{n}{2} ) + O(n) \quad $ 即 $ O(3^k) $

总结：同构类型合并计算卷积矩阵幂次等

code

#pragma GCC optimize("Ofast")
#include <iostream>
#define Sakura int
#define Re register int
#define _ putchar(' ')
#define el putchar('\n')
#define fre(x,y) freopen(#x".in","r",stdin),freopen(#y".out","w",stdout);

using namespace std;

const int maxn=1<<17;

inline int read(){
	int x=0,f=0;char c=getchar();
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return f?-x:x;
}

inline void ot(int x) {
	if(x<0) putchar('-'),x=-x;
	if(x>9) ot(x/10);putchar(x%10|48);
}

int n,N;
int a[maxn],b[maxn],c[maxn];
int d[maxn],top;

void solve(int *a,int *b,int *c,int n) {
	if(n<=32) {
		for(Re i=0;i<n;++i)
			for(Re j=0;j<n;++j)
				c[i|j]=max(c[i|j],a[i]+b[j]);
		return;
	}
	solve(a,b,c,n>>1);
	int *sav=d+top;
	top+=n>>1;
	for(Re i=0;i<(n>>1);++i) sav[i]=a[i],a[i]=max(a[i],a[i+(n>>1)]);
	solve(a,b+(n>>1),c+(n>>1),n>>1);
	for(Re i=0;i<(n>>1);++i) a[i]=sav[i];
	for(Re i=0;i<(n>>1);++i) sav[i]=b[i],b[i]=max(b[i],b[i+(n>>1)]);
	solve(a+(n>>1),b,c+(n>>1),n>>1);
	for(Re i=0;i<(n>>1);++i) b[i]=sav[i];
	top-=n>>1;
}

Sakura main() {
	fre(ztl,ztl);
	n=read();
	N=1<<n;
	for(Re i=0;i<N;++i) a[i]=read();
	for(Re i=0;i<N;++i) b[i]=read();
	solve(a,b,c,N);
	for(Re i=0;i<N;++i) ot(c[i]),_;
}