社区讨论

那咋办,平衡树合并都不会写了

AT_arc149_d[ARC149D] Simultaneous Sugoroku参与者 11已保存回复 14

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
14 条
当前快照
1 份
快照标识符
@mk81ptb5
此快照首次捕获于
2026/01/10 16:31
上个月
此快照最后确认于
2026/01/13 13:30
上个月
查看原帖
帮忙调一下谢谢喵。
CPP
#include<bits/stdc++.h>
#define cint const int
#define uint unsigned int
#define cuint const unsigned int
#define ll long long
#define cll const long long
#define ull unsigned long long
#define cull const unsigned long long
using namespace std;
namespace FastIO
{
    const int BUF_SIZE=1<<20;
    char in_buf[BUF_SIZE],out_buf[BUF_SIZE];
    char* in_ptr=in_buf+BUF_SIZE;
    char* out_ptr=out_buf;
    char get_char()
    {
        if(in_ptr==in_buf+BUF_SIZE)
        {
            in_ptr=in_buf;
            fread(in_buf,1,BUF_SIZE,stdin);
        }
        return *in_ptr++;
    }
    void put_char(char c)
    {
        if(out_ptr==out_buf+BUF_SIZE)
        {
            fwrite(out_buf,1,BUF_SIZE,stdout);
            out_ptr=out_buf;
        }
        *out_ptr++=c;
    }
    struct Flusher
    {
        ~Flusher()
        {
            if(out_ptr!=out_buf)
            {
                fwrite(out_buf,1,out_ptr-out_buf,stdout);
            }
        }
    } flusher;
}
#define getchar FastIO::get_char
#define putchar FastIO::put_char
inline int read()
{
    int x=0;
    bool zf=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            zf=0;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return zf?x:-x;
}
void print(cint x)
{
    if(x==0)
    {
        putchar('0');
        return;
    }
    char buf[12];
    int len=0,y=x;
    if(y<0)
    {
        putchar('-');
        y=-y;
    }
    while(y)
    {
        buf[len++]=(y%10)+'0';
        y/=10;
    }
    while(len--)
    {
        putchar(buf[len]);
    }
}
inline void princh(cint x,const char ch)
{
    print(x);
    putchar(ch);
}
mt19937 mt(chrono::system_clock().now().time_since_epoch().count());
cint N=3e5;
int n,q;
int a[N+1];
int tid,ans[N+1];
int f[N+1];
int find(cint u)
{
    if(f[u]==u)return u;
    find(f[u]);
    ans[u]=max(ans[u],ans[f[u]]);
    return (f[u]=f[f[u]]);
}
#define pair pair<int,int>
#define x first
#define y second
struct FHQ_Treap{
    int rt;
    struct node{
        ll tag,x;
        uint w;
        int ls,rs;
    }t[N+1];
    inline void adp(cint p,cll x)
    {
        t[p].tag+=x;
        t[p].x+=x;
    }
    inline void push_down(cint p)
    {
        if(t[p].tag)
        {
            adp(t[p].ls,t[p].tag);
            adp(t[p].rs,t[p].tag);
            t[p].tag=0;
        }
    }
    pair split(cint p,cll x)
    {
        if(!p)return {0,0};
        pair res;
        push_down(p);
        if(t[p].x>=x)
        {
            res=split(t[p].ls,x);
            t[p].ls=res.y;
            res.y=p;
            return res;
        }
        else
        {
            res=split(t[p].rs,x);
            t[p].rs=res.x;
            res.x=p;
            return res;
        }
    }
    int merge(int p,int q)
    {
        if(!p||!q)return (p|q);
        push_down(p);
        push_down(q);
        if(t[p].w<t[q].w)swap(p,q);
        if(t[p].x==t[q].x)
        {
            f[q]=p;
            t[p].ls=merge(t[p].ls,t[q].ls);
            t[p].rs=merge(t[p].rs,t[q].rs);
            return p;
        }
        pair res=split(q,t[p].x);
        t[p].ls=merge(t[p].ls,res.x);
        t[p].rs=merge(t[p].rs,res.y);
        return p;
    }
    void down(cint p)
    {
        if(!p)return;
        push_down(p);
        down(t[p].ls);
        down(t[p].rs);
    }
    void insert(cint p,cint x)
    {
        t[p]={0,x,(uint)mt(),0,0};
        rt=merge(rt,p);
    }
    void update(cint d)
    {
        pair res=split(rt,0);
        adp(res.x,d);
        adp(res.y,-d);
        rt=merge(res.x,res.y);
    }
    void zero(cint p)
    {
        if(!p)return;
        ans[p]=tid;
        zero(t[p].ls);
        zero(t[p].rs);
    }
    void solve()
    {
        pair resl=split(rt,0),resr=split(resl.y,1);
        zero(resr.x);
        rt=merge(resl.x,resr.y);
    }
    int ask(cint p)
    {
        return t[p].x;
    }
}T;
#define YES putchar('Y'),putchar('e'),putchar('s'),putchar(' ')
#define NO putchar('N'),putchar('o'),putchar(' ')
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    n=read();
    q=read();
    for(int i=1;i<=n;++i)
    {
        a[i]=read();
        f[i]=i;
        T.insert(i,a[i]);
    }
    for(tid=1;tid<=q;++tid)
    {
        T.update(read());
        T.solve();
    }
    T.down(T.rt);
    for(int i=1;i<=n;++i)
    {
        find(i);
        if(ans[i])
        {
            YES;
            princh(ans[i],'\n');
        }
        else
        {
            NO;
            princh(T.ask(i),'\n');
        }
    }
    return 0;
}

回复

14 条回复,欢迎继续交流。

正在加载回复...