layout: post
title: 洛谷试炼场 4-17 树链剖分
author: "luowentaoaa"
catalog: true
mathjax: true
tags:
- 树链剖分
- 数据结构
- 洛谷
[ZJOI2008]树的统计 （入门题,链最大值,链和）
思路
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,q,a[maxn];
vector<int>G[maxn];
int size[maxn],son[maxn],fa[maxn],dep[maxn],top[maxn];
int id[maxn],pre[maxn],cnt=0;
void dfs1(int u,int f,int deep){
size[u]=1;
fa[u]=f;son[u]=0;dep[u]=deep;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==f)continue;
dfs1(v,u,deep+1);
size[u]+=size[v];
if(size[v]>size[son[u]])son[u]=v;
}
}
void dfs2(int u,int root){
id[u]=++cnt;top[u]=root;pre[cnt]=u;
if(son[u])dfs2(son[u],root);
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==fa[u]||v==son[u])continue;
dfs2(v,v);
}
}
int sumv[maxn<<2],maxv[maxn<<2];
inline void pushup(int o){
sumv[o]=sumv[o<<1]+sumv[o<<1|1];
maxv[o]=max(maxv[o<<1],maxv[o<<1|1]);
}
void build(int o,int l,int r){
int mid=(l+r)/2;
if(l==r){
sumv[o]=maxv[o]=a[pre[l]];return;
}
build(o<<1,l,mid);build(o<<1|1,mid+1,r);
pushup(o);
}
void update(int o,int l,int r,int q,int v){
int mid=(l+r)/2;
if(l==r){
sumv[o]=maxv[o]=v;return;
}
if(q<=mid)update(o<<1,l,mid,q,v);
else update(o<<1|1,mid+1,r,q,v);
pushup(o);
}
int querysum(int o,int l,int r,int ql,int qr){
int mid=(l+r)/2,ans=0;
if(ql<=l&&r<=qr)return sumv[o];
if(ql<=mid)ans+=querysum(o<<1,l,mid,ql,qr);
if(qr>mid)ans+=querysum(o<<1|1,mid+1,r,ql,qr);
return ans;
}
int querymax(int o,int l,int r,int ql,int qr){
int mid=(l+r)/2,ans=-inf;
if(ql<=l&&r<=qr)return maxv[o];
if(ql<=mid)ans=max(ans,querymax(o<<1,l,mid,ql,qr));
if(qr>mid)ans=max(ans,querymax(o<<1|1,mid+1,r,ql,qr));
return ans;
}
int qsum(int u,int v){
int ans=0;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
ans+=querysum(1,1,n,id[top[u]],id[u]);
u=fa[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
ans+=querysum(1,1,n,id[v],id[u]);
return ans;
}
int qmax(int u,int v){
int ans=-inf;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
ans=max(ans,querymax(1,1,n,id[top[u]],id[u]));
u=fa[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
ans=max(ans,querymax(1,1,n,id[v],id[u]));
return ans;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;G[u].push_back(v);G[v].push_back(u);
}
for(int i=1;i<=n;i++)cin>>a[i];
fa[1]=1;dfs1(1,0,1);dfs2(1,1);build(1,1,n);
int q;
cin>>q;
while(q--){
int x,y;char s[100];
cin>>s>>x>>y;
if(s[1]=='H')update(1,1,n,id[x],y);
else if(s[1]=='M')cout<<qmax(x,y)<<endl;
else if(s[1]=='S')cout<<qsum(x,y)<<endl;
}
return 0;
}
[P2486 SDOI2011]染色 (区间操作很难 未AC)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,q,col[maxn];
vector<int>G[maxn];
int size[maxn],son[maxn],fa[maxn],dep[maxn],top[maxn];
int id[maxn],pre[maxn],cnt=0;
void dfs1(int u,int f,int deep){
size[u]=1;
fa[u]=f;son[u]=0;dep[u]=deep;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==f)continue;
dfs1(v,u,deep+1);
size[u]+=size[v];
if(size[v]>size[son[u]])son[u]=v;
}
}
void dfs2(int u,int root){
id[u]=++cnt;top[u]=root;pre[cnt]=u;
if(son[u])dfs2(son[u],root);
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==fa[u]||v==son[u])continue;
dfs2(v,v);
}
}
struct node{
int l,r;
int num,lazy,lc,rc;
}my[maxn<<2];
void push_up(int o){
my[o].lc=my[o<<1].lc;my[o].rc=my[(o<<1)|1].rc;
int ans=my[o<<1].num+my[(o<<1)|1].num;
if(my[o<<1].rc==my[(o<<1)|1].lc)ans--;
my[o].num=ans;
}
void push_down(int o){
if(my[o].lazy){
my[o<<1].lazy=my[(o<<1)|1].lazy=my[o].lazy;
my[o<<1].num=my[(o<<1)|1].num=1;
my[o<<1].lc=my[o<<1].rc=my[o].lc;
my[(o<<1)|1].lc=my[(o<<1)|1].rc=my[o].lc;
my[o<<1].lazy=0;
}
}
void build(int o,int l,int r){
int mid=(l+r)/2;
my[o].l=l;my[o].r=r;my[o].num=0;my[o].lazy=0;
if(l==r){
my[o].num=1;
my[o].lc=my[o].rc=col[pre[l]];
return;
}
build(o<<1,l,mid);build((o<<1)|1,mid+1,r);
push_up(o);
}
void update(int o,int l,int r,int x){
if(my[o].l==l&&my[o].r==r){
my[o].num=my[o].lazy=1;
my[o].lc=my[o].rc=x;
return;
}
push_down(o);
int mid=(my[o].l+my[o].r)/2;
if(r<=mid)update(o<<1,l,r,x);
else if(l>mid)update((o<<1)|1,l,r,x);
else{
update(o<<1,l,mid,x);update((o<<1)|1,mid+1,r,x);
}
push_up(o);
}
void uptree(int u,int v,int c){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
update(1,id[top[u]],id[u],c);
u=fa[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
update(1,id[v],id[u],c);
}
int lc,rc;
int query(int o,int l,int r,int L,int R){
if(my[o].l==L)lc=my[o].lc;
if(my[o].r==R)rc=my[o].rc;
if(my[o].l==l&&my[o].r==r)return my[o].num;
push_down(o);
int mid=(my[o].l+my[o].r)/2;
if(r<=mid)return query(o<<1,l,r,L,R);
else if(l>mid)return query((o<<1)|1,l,r,L,R);
else{
int ans=query(o<<1,l,mid,L,R);
ans+=query((o<<1)|1,mid+1,r,L,R);
if(my[o<<1].rc==my[(o<<1)|1].lc)ans--;
return ans;
}
push_up(o);
}
int qutree(int u,int v){
int ans1=-1,ans2=-1,ans=0;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v),swap(ans1,ans2);
ans+=query(1,id[top[u]],id[u],id[top[u]],id[u]);
if(rc==ans1)ans--;
ans1=lc;u=fa[top[u]];
}
if(dep[u]<dep[v])swap(u,v),swap(ans1,ans2);
ans+=query(1,id[v],id[u],id[v],id[u]);
if(rc==ans1)ans--;
if(lc==ans2)ans--;
return ans;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int m;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>col[i];
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
G[u].push_back(v);G[v].push_back(u);
}
dfs1(1,1,1);dfs2(1,1);build(1,1,n);
while(m--){
char s[150];
cin>>s;
int x,y;
if(s[0]=='C'){
int c;cin>>x>>y>>c;
uptree(x,y,c);
}
else{
cin>>x>>y;
cout<<qutree(x,y)<<endl;
}
}
return 0;
}
[P2146 NOI2015]软件包管理器
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,q,col[maxn];
vector<int>G[maxn];
int size[maxn],son[maxn],fa[maxn],dep[maxn],top[maxn];
int id[maxn],pre[maxn],cnt=0;
void dfs1(int u,int f,int deep){
size[u]=1;
fa[u]=f;son[u]=0;dep[u]=deep;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==f)continue;
dfs1(v,u,deep+1);
size[u]+=size[v];
if(size[v]>size[son[u]])son[u]=v;
}
}
void dfs2(int u,int root){
id[u]=++cnt;top[u]=root;pre[cnt]=u;
if(son[u])dfs2(son[u],root);
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==fa[u]||v==son[u])continue;
dfs2(v,v);
}
}
int sum[maxn<<2],lazy[maxn<<2];
void push_up(int o){
sum[o]=sum[o<<1]+sum[o<<1|1];
}
void push_down(int o,int l,int r){
if(lazy[o]){
int mid=(l+r)/2;
if(lazy[o]==-1)sum[o<<1]=sum[o<<1|1]=0,lazy[o<<1]=lazy[o<<1|1]=-1;
else sum[o<<1]=mid-l+1,sum[o<<1|1]=r-mid,lazy[o<<1]=lazy[o<<1|1]=1;
lazy[o]=0;
}
}
void uninstall(int o,int l,int r,int ql,int qr,int x){
if(ql<=l&&r<=qr){
if(!x)lazy[o]=-1,sum[o]=0;
else lazy[o]=1,sum[o]=r-l+1;return;
}
int mid=(l+r)/2;push_down(o,l,r);
if(mid>=ql)uninstall(o<<1,l,mid,ql,qr,x);
if(mid<qr)uninstall(o<<1|1,mid+1,r,ql,qr,x);
push_up(o);
}
void install(int v,int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
uninstall(1,1,n,id[top[x]],id[x],v);
x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
uninstall(1,1,n,id[y],id[x],v);
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
cin>>n;
for(int i=2;i<=n;i++){
int u;
cin>>u;u++;
G[i].push_back(u);
G[u].push_back(i);
}
dfs1(1,1,1);
dfs2(1,1);
int m;cin>>m;
char op[150];
while(m--){
int x;
cin>>op>>x;x++;int p=sum[1];
if(op[0]=='i'){
install(1,x,1);
cout<<abs(p-sum[1])<<endl;
}
else{
uninstall(1,1,n,id[x],id[x]+size[x]-1,0);
cout<<abs(p-sum[1])<<endl;
}
}
return 0;
}
/*
7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0
*/
[P3258 JLOI2014]松鼠的新家 (区间加减)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
vector<int>G[maxn];
int id[maxn],dep[maxn],pre[maxn],fa[maxn],size[maxn],son[maxn],cnt,top[maxn];
void dfs1(int now,int f,int deep){
fa[now]=f;size[now]=1;son[now]=0;dep[now]=deep;
for(auto i:G[now]){
if(i==f)continue;
dfs1(i,now,deep+1);
size[now]+=size[i];
if(size[i]>size[son[now]])son[now]=i;
}
}
void dfs2(int now,int root){
id[now]=++cnt;pre[cnt]=now;top[now]=root;
if(son[now])dfs2(son[now],root);
for(auto i:G[now]){
if(i==fa[now]||i==son[now])continue;
dfs2(i,i);
}
}
int sum[maxn<<2],lazy[maxn<<2];
void push_up(int o){
sum[o]=sum[o<<1]+sum[o<<1|1];
}
void push_down(int o,int l,int r){
if(lazy[o]){
int mid=(l+r)/2;
lazy[o<<1]+=lazy[o];
lazy[o<<1|1]+=lazy[o];
sum[o<<1]+=(mid-l+1)*lazy[o];
sum[o<<1|1]+=(r-mid)*lazy[o];
lazy[o]=0;
}
}
void update(int o,int l,int r,int ql,int qr,int w){
int mid=(l+r)/2;
if(ql<=l&&r<=qr){
lazy[o]+=w;
sum[o]+=(r-l+1)*w;
return;
}
push_down(o,l,r);
if(ql<=mid)update(o<<1,l,mid,ql,qr,w);
if(qr>mid)update(o<<1|1,mid+1,r,ql,qr,w);
push_up(o);
}
void print(int o,int l,int r,int ql,int qr){
cout<<"o=="<<o<<" l="<<l<<" r="<<r<<" ql="<<ql<<" qr="<<qr<<endl;
cout<<"sum="<<sum[o]<<endl;
}
int query(int o,int l,int r,int ql,int qr){
//print(o,l,r,ql,qr);
if(l==r){
return sum[o];
}
int mid=(l+r)/2;
push_down(o,l,r);
if(ql<=mid)return query(o<<1,l,mid,ql,qr);
else return query(o<<1|1,mid+1,r,ql,qr);
}
void uptree(int u,int v,int w){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
update(1,1,cnt,id[top[u]],id[u],w);
u=fa[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
update(1,1,cnt,id[v],id[u],w);
}
int a[maxn];
// 适用于正负整数
template <class T>
inline bool read(T &ret)
{
char c;
int sgn;
if (c = getchar(), c == EOF) return 0; //EOF
while (c != '-' && (c < '0' || c > '9')) c = getchar();
sgn = (c == '-') ? -1 : 1;
ret = (c == '-') ? 0 : (c - '0');
while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
ret *= sgn;
return 1;
}
inline void out(int x)
{
if (x > 9) out(x / 10);
putchar(x % 10 + '0');
}
int main()
{
/* std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);*/
int n;
//cin>>n;
read(n);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<n;i++){
int u,v;
// cin>>u>>v;
read(u);read(v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs1(1,1,1);dfs2(1,1);
for(int i=1;i<n;i++){
uptree(a[i],a[i+1],1);
uptree(a[i+1],a[i+1],-1);
}
for(int i=1;i<=n;i++){
// cout<<query(1,1,n,id[i],id[i])<<endl;
out(query(1,1,n,id[i],id[i]));
puts("");
}
return 0;
}