社区讨论
萌新求助简单题,30行代码都出错,求教
P2486[SDOI2011] 染色参与者 4已保存回复 14
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 14 条
- 当前快照
- 1 份
- 快照标识符
- @mi7yw0ta
- 此快照首次捕获于
- 2025/11/21 05:52 4 个月前
- 此快照最后确认于
- 2025/11/21 06:46 4 个月前
题目是吸引你点进来的,都进来了,就帮忙看看吧(雾)
树剖:Dfs和线段树应该没锅,就是判区间做优的时候可能出了问题,过不去样例
CPP#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int a[100005];
struct Node
{
int v;
Node *next;
}*h[100005],pool[200005];
struct SGTree
{
int le,ri;
int lc,rc;
int la;
int sum;
}t[400005];
int top[100005];
int son[100005];
int size[100005];
int w[100005];
int rw[100005];
int dep[100005];
int f[100005];
int cnt=0,tot=0;
void Adde(int u,int v)
{
Node *p=&pool[++tot];
p->v=v;
p->next=h[u];
h[u]=p;
}
void Dfs1(int u,int fa)
{
int maxsize=-1,maxson=0;
size[u]=1;
f[u]=fa;
for(Node *p=h[u];p;p=p->next)
{
if(p->v!=fa)
{
dep[p->v]=dep[u]+1;
Dfs1(p->v,u);
if(maxsize<size[p->v])
{
maxsize=size[p->v];
maxson=p->v;
}
size[u]+=size[p->v];
}
}
son[u]=maxson;
}
void Dfs2(int u,int fa)
{
cnt++;
w[u]=cnt;
if(son[u])
{
top[son[u]]=top[u];
Dfs2(son[u],fa);
}
for(Node *p=h[u];p;p=p->next)
{
if(p->v!=f[u]&&p->v!=son[u])
{
top[p->v]=p->v;
Dfs2(p->v,p->v);
}
}
}
void BuildT(int id,int l,int r)
{
t[id].le=l;
t[id].ri=r;
t[id].lc=a[rw[l]];
t[id].rc=a[rw[r]];
t[id].la=0;
if(l==r)
{
t[id].sum=1;
return;
}
int Mid=(l+r)/2;
BuildT(id*2,l,Mid);
BuildT(id*2+1,Mid+1,r);
t[id].sum=t[id*2].sum+t[id*2+1].sum;
if(t[id*2].lc==t[id*2+1].rc)
{
t[id].sum--;
}
}
void Push(int id)
{
if(t[id].la)
{
t[id*2].la=t[id].la;
t[id*2+1].la=t[id].la;
t[id].sum=1;
t[id].lc=t[id].la;
t[id].rc=t[id].la;
t[id].la=0;
}
}
void Change(int id,int l,int r,int c)
{
if(t[id].le==l&&t[id].ri==r)
{
t[id].la=c;
return;
}
Push(id);
if(t[id*2].ri>=r)
{
Change(id*2,l,r,c);
}
else if(t[id*2+1].le<=l)
{
Change(id*2+1,l,r,c);
}
else
{
Change(id*2,l,t[id*2].ri,c);
Change(id*2+1,t[id*2+1].le,r,c);
}
t[id].sum=t[id*2].sum+t[id*2+1].sum;
if(t[id*2].rc==t[id*2+1].lc)
{
t[id].sum--;
}
}
int Query(int id,int l,int r)
{
if(t[id].le==l&&t[id].ri==r)
{
return t[id].sum;
}
Push(id);
if(t[id*2].ri>=r)
{
return Query(id*2,l,r);
}
else if(t[id*2+1].le<=l)
{
return Query(id*2+1,l,r);
}
else
{
int ans=Query(id*2,l,t[id*2].ri)+Query(id*2+1,t[id*2+1].le,r);
if(t[id*2].rc==t[id*2+1].lc)
{
ans--;
}
return ans;
}
}
int Modify(int x,int y,int c)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
{
swap(x,y);
}
Change(1,w[top[x]],w[x],c);
x=f[top[x]];
}
if(w[x]>w[y])
{
swap(x,y);
}
Change(1,w[x],w[y],c);
}
int Ask(int x,int y)
{
// cout << "in" <<endl;
int res=0;
while(top[x]!=top[y])
{
// printf("%lld %lld\n",x,y);
if(dep[top[x]]<dep[top[y]])
{
swap(x,y);
}
res+=Query(1,w[top[x]],w[x]);
if(t[w[top[x]]].rc==t[w[f[top[x]]]].lc)
{
res--;
}
x=f[top[x]];
// printf("%lld\n",res);
}
// cout << "s" <<endl;
if(w[x]>w[y])
{
swap(x,y);
}
res+=Query(1,w[x],w[y]);
return res;
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%lld",&a[i]);
}
int uu,vv;
for(int i=1;i<n;++i)
{
scanf("%lld%lld",&uu,&vv);
Adde(uu,vv);
Adde(vv,uu);
}
Dfs1(1,0);
Dfs2(1,1);
for(int i=1;i<=n;++i)
{
if(top[i]==0)
{
top[i]=i;
}
}
for(int i=1;i<=n;++i)
{
rw[w[i]]=i;
}
BuildT(1,1,n);
// for(int i=1;i<=4*n;++i)
// {
// printf("%lld %lld %lld %lld %lld\n",t[i].le,t[i].ri,t[i].lc,t[i].rc,t[i].sum);
// }
// for(int i=1;i<=n;++i)
// {
// printf("%lld %lld %lld %lld\n",top[i],dep[i],w[i],size[i]);
// }
char op;
int x,y,z;
while(m--)
{
cin >> op;
scanf("%lld%lld",&x,&y);
if(op=='Q')
{
printf("%lld\n",Ask(x,y));
}
else
{
scanf("%lld",&z);
Modify(x,y,z);
}
}
return 0;
}
回复
共 14 条回复,欢迎继续交流。
正在加载回复...