[COTS 2023] 题 Zadatak

pig1121 · 2024-12-23 13:48:35 · 题解

考虑线段树合并。

先试图用线段树表示状态。注意到合并是中心对齐且 2\mid a_i，故只需要维护正方形的一角（输出时将答案乘以 4）。某一个位置的颜色只与它到中心的水平（或竖直）距离有关，故考虑用线段树维护距中心为某个值的点的颜色。

设节点 i 维护的范围为 [l_i,r_i]，则区域面积 len_i=r_i^2-(l_i-1)^2，另维护 sum_i 表示在 [l_i,r_i] 中黑色区域的总面积，tag_i 表示区间 [l_i,r_i] 是否要整体取反（合并和初始化要用的）。

一开始对 rt_i 打 [1,\frac{a_i}2] 的区间反转（置为黑色）。

进行合并时，叶子节点的值为 sum_u\oplus sum_v （\oplus 表示异或），代价等于 [sum_u>0 \land sum_v>0]\times len_i（只有两者都为黑才会产生 len 的代价），非叶子节点递归合并。

然后你就愉快地 TLE 了……

为神马？

因为你的初始点数可能是满的，每次合并可以退化到 O(n)。

但是我们发现，如果这个区间内的所有数都是同一个值，那我们可以直接合并然后取反，就像这样：

if(tr[u].sum==tr[u].len){
    int res=tr[v].sum;
    pusht(v,1);
    return{v,res};
}

这样相当于每棵树初始只有 O(\log n) 个点，合并 n 次复杂度正确。

哦对了，不要忘记 pushdown，而且由于新建了 n-1 棵树，rt 数组要开 2n。

没了，代码：

#include<iostream>
#include<cassert>
#include<algorithm>
#include<vector>
#define int long long
#define endl '\n'
#ifdef ONLINE_JUDGE
#define getc getc_unlocked
#endif
#define str stdin
using namespace std;

inline void read(int&x){
    x=0;
    int f=1;
    char ch=getc(str);
    while(ch<'0'||'9'<ch){
        if(ch=='-')f=-1;
        ch=getc(str);
    }
    while('0'<=ch&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getc(str);
    }
    x*=f;
}

namespace segtree{
    struct node{
        int ls,rs,sum,len,tag;
    };
    node tr[13000005];
    int tot;
    inline void update(int p){
        tr[p].sum=tr[tr[p].ls].sum+tr[tr[p].rs].sum;
    }
    inline void pusht(int p,int k){
        tr[p].sum=tr[p].len-tr[p].sum;
        tr[p].tag^=k;
    }
    inline void pushdown(int p){
        int ls=tr[p].ls,rs=tr[p].rs;
        if(tr[p].tag){
            pusht(ls,tr[p].tag);
            pusht(rs,tr[p].tag);
            tr[p].tag=0;
        }
    }
    int nnd(int l,int r){
        int p=++tot;
        tr[p].len=r*r-(l-1)*(l-1);
        return p;
    }
    void modify(int&p,int x,int y,int l,int r,int k){
        if(!p)p=nnd(l,r);
        if(x<=l&&r<=y){
            pusht(p,k);
            return;
        }
        int mid=(l+r)>>1;
        if(!tr[p].ls)tr[p].ls=nnd(l,mid);
        if(!tr[p].rs)tr[p].rs=nnd(mid+1,r);
        pushdown(p);
        if(x<=mid)modify(tr[p].ls,x,y,l,mid,k);
        if(mid<y)modify(tr[p].rs,x,y,mid+1,r,k);
        update(p);
    }
    pair<int,int>merge(int u,int v,int l,int r){
    //  cerr<<u<<' '<<v<<' '<<l<<' '<<r<<endl;
        if(!u||!v)return{u|v,0};
        if(!tr[u].sum)return{v,0};
        if(!tr[v].sum)return{u,0};
        if(tr[u].sum==tr[u].len){
            int res=tr[v].sum;
    //      cerr<<tr[u].sum<<' '<<tr[u].len<<' '<<res<<endl<<flush;
            pusht(v,1);
    //      cerr<<tr[v].sum<<endl<<flush;
            return{v,res};
        }
        if(tr[v].sum==tr[v].len){
            int res=tr[u].sum;
    //      cerr<<tr[v].sum<<' '<<tr[v].len<<' '<<res<<endl<<flush;
            pusht(u,1);
    //      cerr<<tr[u].sum<<endl<<flush;
            return{u,res};
        }
        if(l==r){
            int res=(tr[u].sum&&tr[v].sum)*tr[u].len;
    //      cerr<<tr[u].sum<<' '<<tr[v].sum<<' '<<tr[u].len<<' '<<res<<endl;
            tr[u].sum^=tr[v].sum;
            return {u,res};
        }
        int mid=(l+r)>>1;
//      if(!tr[u].ls)tr[u].ls=nnd(l,mid);
//      if(!tr[v].ls)tr[v].ls=nnd(l,mid);
//      if(!tr[u].rs)tr[u].rs=nnd(mid+1,r);
//      if(!tr[v].rs)tr[v].rs=nnd(mid+1,r);
        pushdown(u);pushdown(v);
        int res=0;
        pair<int,int>tmp=merge(tr[u].ls,tr[v].ls,l,mid);
        tr[u].ls=tmp.first,res+=tmp.second;
        tmp=merge(tr[u].rs,tr[v].rs,mid+1,r);
        tr[u].rs=tmp.first,res+=tmp.second;
        update(u);
        return {u,res};
    }
}
int rt[200005],a[100005];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//  freopen("P10834_4.in","r",stdin);
//  freopen("P10834_4.out","w",stdout);
    int n;
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        a[i]/=2;
        segtree::modify(rt[i],1,a[i],1,5e5,1);
    }
    for(int i=1;i<n;i++){
        int x,y;
        read(x);read(y);
        pair<int,int>tmp=segtree::merge(rt[x],rt[y],1,5e5);
        rt[i+n]=tmp.first;
//      cerr<<"MERGE "<<i<<" COMPLETED\n"<<flush;
        cout<<tmp.second*4<<endl;
//      cerr<<i<<endl<<flush;
//      cout<<flush;
    }
    return 0;
}