社区讨论
那咋办,平衡树合并都不会写了
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 条回复,欢迎继续交流。
正在加载回复...