【bzoj 3531】[Sdoi 2014]トラベルダイナミックポイントの線分ツリー
2889 ワード
動的に点を開く線分ツリーc本の線分ツリーCCは1つのノードを削除することに対応して、1つのノードCWを増加して1つのノードQSを修正して対応する線分ツリーの中の部分の和を問い合わせることに対応します
QMクエリ対応セグメントツリーの最大値
動的開点とは,各ノードが使用するときに再開し,不要なノードを多く取り除くことができる.
合計O(nlogn)レベルのノード
QMクエリ対応セグメントツリーの最大値
動的開点とは,各ノードが使用するときに再開し,不要なノードを多く取り除くことができる.
合計O(nlogn)レベルのノード
#include
#include
#include
#include
#include
#include
#define maxn 200010
#define N 10000100
using namespace std;
struct yts
{
int lch,rch,mx,sum,l,r;
}t[N];
int root[maxn],head[maxn],to[maxn],next[maxn],w[maxn],c[maxn],st[maxn];
int fa[20][maxn],dep[maxn],seq[maxn],size[maxn],dd[maxn],e[maxn],rank[maxn];
bool vis[maxn];
char s[5];
int n,m,num,tot,T;
void addedge(int x,int y)
{
num++;to[num]=y;next[num]=st[x];st[x]=num;
}
void dfs(int x)
{
e[++tot]=x;size[x]=1;
for (int p=st[x];p;p=next[p])
if (to[p]!=fa[0][x])
{
fa[0][to[p]]=x;
dep[to[p]]=dep[x]+1;
dfs(to[p]);
size[x]+=size[to[p]];
if (size[to[p]]>size[dd[x]]) dd[x]=to[p];
}
}
int go_up(int x,int d)
{
for (int i=17;i>=0;i--)
if (d&(1<dep[y]) x=go_up(x,dep[x]-dep[y]);
else y=go_up(y,dep[y]-dep[x]);
if (x==y) return x;
for (int i=17;i>=0;i--)
if (fa[i][x]!=fa[i][y]) x=fa[i][x],y=fa[i][y];
return fa[0][x];
}
void update(int i)
{
t[i].mx=max(t[t[i].lch].mx,t[t[i].rch].mx);
t[i].sum=t[t[i].lch].sum+t[t[i].rch].sum;
}
void modify(int &i,int l,int r,int x,int d)
{
if (!i)
{
i=++tot;
t[i].lch=t[i].rch=t[i].mx=t[i].sum=0;
t[i].l=l;t[i].r=r;
}
if (l==r)
{
t[i].mx=t[i].sum=d;
return;
}
int mid=(t[i].l+t[i].r)/2;
if (x<=mid) modify(t[i].lch,l,mid,x,d);
if (middep[z])
{
ans=max(ans,query_mx(root[col],rank[head[x]],rank[x]));x=fa[0][head[x]];
}
ans=max(ans,query_mx(root[col],rank[z],rank[x]));
while (dep[head[y]]>dep[z])
{
ans=max(ans,query_mx(root[col],rank[head[y]],rank[y]));y=fa[0][head[y]];
}
ans=max(ans,query_mx(root[col],rank[z],rank[y]));
printf("%d
",ans);
}
if (s[1]=='S')
{
int z=LCA(x,y),col=c[x],ans=0;
while (dep[head[x]]>dep[z])
{
ans+=query_sum(root[col],rank[head[x]],rank[x]);x=fa[0][head[x]];
}
ans+=query_sum(root[col],rank[z],rank[x]);
while (dep[head[y]]>dep[z])
{
ans+=query_sum(root[col],rank[head[y]],rank[y]);y=fa[0][head[y]];
}
ans+=query_sum(root[col],rank[z],rank[y]);
ans-=query_sum(root[col],rank[z],rank[z]);
printf("%d
",ans);
}
}
return 0;
}