P3714 [BJOI2017]树的难题
这道题上来一看，求路径，点分治无疑，可是当把板子敲完之后，才发现有点不对劲。
现在每条路的步数可以记录，贡献在ｄｆｓ的时候标记上ｆａ的颜色种类也可以解决，主要问题是同颜色段只算一次，对于每个分治中心，不同的ｄｉｓ拼到一起后头上的东西是不是相同的，这就是个问题。点分治本来就够暴力了，如果这个问题还暴力搞，复杂度不论时间还是空间都会炸飞。
正解是给出了单调队列的做法，复杂度O(n* logn)，但是我对单调队列挺反感的，所以就转眼看到了学长的线段树做法，然后顿悟。
主要是预处理每个节点的儿子按照颜色排序，这样保证相同颜色一定相邻，这个活交给vector来干，排完序以后再去建边。然后回到老问题上，开出两颗线段树，一颗记录颜色不相同的，一颗记录颜色相同的，每次儿子颜色改变之后把ｒｏｏｔ２合并到ｒｏｏｔ１上，ｒｏｏｔ２归零。每换一个分治中心，再把ｒｏｏｔ１归零。这样查询ｍａｘ就可以解决。还有个问题需要注意，线段树必然伴随着节点归零的操作，可是不能在每一个分治结束后就全部归零，这样效率太低。我们可以插入一个节点就清一个，这样的话是用多少清多少，效率会提高。复杂度O(n* log^2n)比单调队列多出来一个log，不过还是可以通过的，主要是简单粗暴理解方便。
#include<bits/stdc++.h>
#define N 500001
#define m1(x) memset(x,0,sizeof(x))
using namespace std;
int rt,tot,cnt,n,m,sum,ji,head[N],w[N],col[N],zhong[N],siz[N],l,r,qqq,root1,root2,ans=-0x3f3f3f3f;
bool bo[N],vis[N];
struct jjj
{int to,next,val;
}bian[N];
struct zzz
{int l,r,maxn;
}tree[400001*40];
struct aaa
{int col,v;
aaa(){}
aaa(int a,int b){col=a,v=b;}
};
vector<aaa> g[N];
inline bool cmp(aaa i,aaa j)
{return i.col>j.col;}
inline void pushup(int x)
{tree[x].maxn=max(tree[tree[x].l].maxn,tree[tree[x].r].maxn);}
inline void clear(int ji)
{tree[ji].l=tree[ji].r=0;tree[ji].maxn=-0x3f3f3f3f;}
inline int insert(int x,int l,int r,int pos,int val)
{ if(!x)x=++ji,clear(ji);
if(l==r)
{ tree[x].maxn=max(val,tree[x].maxn);
return x;
}
int mid=(l+r)>>1;
if(mid<pos)tree[x].r=insert(tree[x].r,mid+1,r,pos,val);
else tree[x].l=insert(tree[x].l,l,mid,pos,val);
pushup(x);
return x;
}
inline int merge(int x,int y,int l,int r)
{ if(!x or !y)return x+y;//cout<<' '<<"cao"<<x<<' '<<tree[x].maxn<<endl;
if(l==r)
{ tree[x].maxn=max(tree[x].maxn,tree[y].maxn);
tree[y].maxn=-0x3f3f3f3f;
return x;
}
int mid=(l+r)>>1;
tree[x].l=merge(tree[x].l,tree[y].l,l,mid);
tree[x].r=merge(tree[x].r,tree[y].r,mid+1,r);
pushup(x);
return x;
}
inline int query(int x,int l,int r,int L,int R)
{ if(!x or l>r)return -0x3f3f3f3f;
if(l>=L and r<=R){
return tree[x].maxn;}
int mid=(l+r)>>1,ccc=-0x3f3f3f3f;
if(mid<R)ccc=max(ccc,query(tree[x].r,mid+1,r,L,R));
if(mid>=L)ccc=max(ccc,query(tree[x].l,l,mid,L,R));
return ccc;
}
struct baa{int dp,ds;}p[N];
namespace AYX
{ inline void add(int u,int v,int c)
{ bian[++tot].to=v;
bian[tot].val=c;
bian[tot].next=head[u];
head[u]=tot;
}
inline void get_root(int x,int fa)
{ siz[x]=1;zhong[x]=0;
for(int i=head[x];i;i=bian[i].next)
{ int v=bian[i].to;
if(vis[v] or v==fa)continue;
get_root(v,x);
siz[x]+=siz[v];
zhong[x]=max(zhong[x],siz[v]);
}
zhong[x]=max(zhong[x],sum-siz[x]);
if(zhong[x]<zhong[rt])rt=x;
}
inline void get_dis(int x,int fa,int dis,int dep,int pre)
{ if(dep>r)return ;
p[++cnt]=(baa){dep,dis};
for(int i=head[x];i;i=bian[i].next)
{ int v=bian[i].to;
if(v==fa or vis[v])continue;
if(bian[i].val==pre)
get_dis(v,x,dis,dep+1,pre);
else
get_dis(v,x,dis+w[bian[i].val],dep+1,bian[i].val);
}
}
inline void calc(int x)
{ ji=0;clear(ji);root1=0;root2=0;int pre=0;
for(int i=head[x];i;i=bian[i].next)
{ int v=bian[i].to;
if(vis[v])continue;
if(bian[i].val!=pre)
{ root1=merge(root1,root2,1,n);
root2=0;
pre=bian[i].val;
}
get_dis(v,x,w[bian[i].val],1,bian[i].val);
for(int i=1;i<=cnt;++i)
{ int dp=p[i].dp,ds=p[i].ds;
if(root2)ans=max(ans,max(query(root2,1,n,max(1,l-dp),r-dp)+ds-w[pre],query(root1,1,n,max(1,l-dp),r-dp)+ds));
else ans=max(ans,query(root1,1,n,max(1,l-dp),r-dp)+ds);
if(dp>=l and dp<=r)ans=max(ans,ds);
}
for(int i=1;i<=cnt;++i)root2=insert(root2,1,n,p[i].dp,p[i].ds);
cnt=0;
}
}
inline void solve(int x)
{ vis[x]=1;calc(x);
for(int i=head[x];i;i=bian[i].next)
{ int v=bian[i].to;
if(vis[v])continue;
zhong[rt=0]=1234567;
sum=siz[v];
get_root(v,x);
solve(rt);
}
}
inline short main()
{ scanf("%d%d%d%d",&n,&m,&l,&r);
for(int i=1;i<=m;++i)scanf("%d",&w[i]);
for(int i=1;i<n;++i)
{ int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a].push_back(aaa(c,b));g[b].push_back(aaa(c,a));
}
for(int i=1;i<=n;++i)sort(g[i].begin(),g[i].end(),cmp);
for(int i=1;i<=n;++i)
for(int j=0;j<g[i].size();++j)
add(i,g[i][j].v,g[i][j].col);
zhong[rt=0]=sum=n;get_root(1,0);solve(rt);
printf("%d\n",ans);
return 0;
}
}
signed main()
{return AYX::main();}
P3345 [ZJOI2015]幻想乡战略游戏
点分树的题特征好明显，时间长，点分治带修改。。而且套路都一样，把树建出来，然后记贡献，计算时容斥的求。
这道题总的来说就两个操作，ａｄｄ和ｑｕｅｒｙ。ａｄｄ好说，往上加就行。ｑｕｅｒｙ要找最优代价，考虑到最优解一定在一个方向，所以可以先假定根最优，然后往下搜，遇上更优的就转到那一个子树上，接着搜。知道本身最优了就可以停了。然后就解决了。
#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;
struct OriginalTree
{ struct egde{int to,nxt,w;}bian[N<<1];
int head[N],tot,cnt,dis[N],logg[N<<2],pos[N],st[N<<1][21];
bool vis[N];
inline void add(int x,int y,int c)
{ bian[++tot].to=y;
bian[tot].nxt=head[x];
head[x]=tot;
bian[tot].w=c;
}
inline void dfs(int x,int fa)
{ pos[x]=++cnt;
st[pos[x]][0]=dis[x];
for(int i=head[x];i;i=bian[i].nxt)
{ int v=bian[i].to;
if(v==fa)continue;
dis[v]=dis[x]+bian[i].w;
dfs(v,x);
st[++cnt][0]=dis[x];
}
}
inline int getdis(int u,int v)
{ if(pos[u]>pos[v])swap(u,v);
int k=logg[pos[v]-pos[u]+1];
return dis[u]+dis[v]-2*min(st[pos[u]][k],st[pos[v]-(1<<k)+1][k]);
}
inline void getRMQ()
{ logg[0]=-1;
for(int i=1;i<=(N<<2);++i)logg[i]=logg[i>>1]+1;
dfs(1,0);
for(int j=1;(1<<j)<=cnt;++j)
for(int i=1;i+(1<<j)-1<=cnt and i<=cnt;++i)
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}T;
struct zxb
{int u,v,w,nxt;}bian[N];
int n,Q,Lastroot,maxn,root,head[N],zhong[N],dis1[N],dis2[N],siz[N],par[N],sumv[N],sum,cnt,tot;
bool vis[N];
namespace AYX
{ inline void innt()
{ scanf("%lld%lld",&n,&Q);
for(int i=1;i<n;++i)
{ int x,y,c;
scanf("%lld%lld%lld",&x,&y,&c);
T.add(x,y,c);T.add(y,x,c);
}
T.getRMQ();
}
inline void getroot(int x,int fa)
{ siz[x]=1;zhong[x]=0;
for(int i=T.head[x];i;i=T.bian[i].nxt)
{ int v=T.bian[i].to;
if(v==fa or vis[v])continue;
getroot(v,x);
siz[x]+=siz[v];
zhong[x]=max(zhong[x],siz[v]);
}
zhong[x]=max(zhong[x],sum-siz[x]);
if(zhong[x]<zhong[root])root=x;
}
inline void add(int x,int rt,int v)
{ bian[++cnt].w=v;
bian[cnt].u=x;
bian[cnt].v=rt;
bian[cnt].nxt=head[x];
head[x]=cnt;
}
inline void work(int x,int fa)
{ vis[x]=1;par[x]=fa;
for(int i=T.head[x];i;i=T.bian[i].nxt)
{ int v=T.bian[i].to;
if(vis[v])continue;
sum=siz[v];root=0;
getroot(v,0);
add(x,root,v);
work(root,x);
}
}
inline void ins(int x,int val)
{ sumv[x]+=val;
for(int i=x;par[i];i=par[i])
{ int dist=T.getdis(par[i],x);
dis1[par[i]]+=dist*val;
dis2[i]+=dist*val;
sumv[par[i]]+=val;
}
}
inline int calc(int x)
{ int aaa=dis1[x];
for(int i=x;par[i];i=par[i])
{ int dist=T.getdis(par[i],x);
aaa+=dis1[par[i]]-dis2[i];
aaa+=dist*(sumv[par[i]]-sumv[i]);
}
return aaa;
}
inline int query(int x)
{ int tmp=calc(x);
for(int i=head[x];i;i=bian[i].nxt)
{ int v=bian[i].w;
int aaa=calc(v);
if(aaa<tmp)return query(bian[i].v);
}
return tmp;
}
inline short main()
{ innt();
zhong[root=0]=sum=n;
getroot(1,0);
Lastroot=root;work(root,0);root=Lastroot;
for(int i=1;i<=Q;++i)
{ int x,y;
scanf("%lld%lld",&x,&y);
ins(x,y);
printf("%lld\n",query(root));
}
return 0;
}
}
signed main()
{return AYX::main();
}
P3241 [HNOI2015]开店
#include<bits/stdc++.h>
#define N 150005
#define int long long
using namespace std;
int dep[N],ans;
struct OriginalTree
{ int cnt,tot,head[N],dis[N],pos[N],st[N<<1][21],lg[N<<1];
struct edge{int to,nxt,w;}bian[N<<1];
inline void add(int u,int v,int val)
{ bian[++cnt].to=v;
bian[cnt].nxt=head[u];
head[u]=cnt;
bian[cnt].w=val;
}
inline void dfs(int x,int fa)
{ pos[x]=++tot;
st[pos[x]][0]=dis[x];
for(int i=head[x];i;i=bian[i].nxt)
{ int v=bian[i].to;
if(v==fa)continue;
dis[v]=dis[x]+bian[i].w;
dfs(v,x);
st[++tot][0]=dis[x];
}
}
inline int getdis(int x,int y)
{ if(pos[x]<pos[y])swap(x,y);
int k=lg[pos[x]-pos[y]+1];
return dis[x]+dis[y]-2*min(st[pos[y]][k],st[pos[x]-(1<<k)+1][k]);
}
inline void RMQ()
{ lg[0]=-1;
for(int i=1;i<N<<1;++i)lg[i]=lg[i>>1]+1;
dfs(1,0);
for(int j=1;(1<<j)<=tot;++j)
for(int i=1;i+(1<<j)-1<=tot and i<=tot;++i)
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}T;
int n,m,Q,cnt,tot,zhong[N],age[N],siz[N],root,lastroot,sum,A,par[N];
bool vis[N];
struct ayx
{int year,val;
friend bool operator < (ayx i,ayx j){return i.year<j.year;}
};
vector<ayx>dis1[N];
vector<ayx>dis2[N];
vector<int>val1[N];
vector<int>val2[N];
namespace AYX
{ inline void innt()
{ scanf("%lld%lld%lld",&n,&Q,&A);
for(int i=1;i<=n;++i)scanf("%lld",&age[i]);
for(int i=1;i<n;++i)
{ int x,y,c;
scanf("%lld%lld%lld",&x,&y,&c);
T.add(x,y,c);T.add(y,x,c);
}
T.RMQ();
}
inline void getroot(int x,int fa)
{ siz[x]=1;zhong[x]=0;
for(int i=T.head[x];i;i=T.bian[i].nxt)
{ int v=T.bian[i].to;
if(vis[v] or v==fa)continue;
getroot(v,x);
zhong[x]=max(zhong[x],siz[v]);
siz[x]+=siz[v];
}
zhong[x]=max(zhong[x],sum-siz[x]);
if(zhong[x]<zhong[root])root=x;
}
inline void ins(int x,int age)
{ dis1[x].push_back((ayx){age,0});
for(int i=x;par[i];i=par[i])
{ int dist=T.getdis(par[i],x);
dis1[par[i]].push_back((ayx){age,dist});
dis2[i].push_back((ayx){age,dist});
}
}
inline void work(int x,int fa)
{ vis[x]=1;par[x]=fa;ins(x,age[x]);
for(int i=T.head[x];i;i=T.bian[i].nxt)
{ int v=T.bian[i].to;
if(vis[v] or v==fa)continue;
sum=siz[v];zhong[root=0]=n;
getroot(v,0);
work(root,x);
}
}
inline void query(int x,int l,int r)
{ int posl=lower_bound(dis1[x].begin(),dis1[x].end(),(ayx){l,0})-dis1[x].begin();
int posr=upper_bound(dis1[x].begin(),dis1[x].end(),(ayx){r,0})-dis1[x].begin();
ans=dis1[x][posl].val-dis1[x][posr].val;
for(int i=x;par[i];i=par[i])
{ int lposl=lower_bound(dis1[par[i]].begin(),dis1[par[i]].end(),(ayx){l,0})-dis1[par[i]].begin(),rposr=upper_bound(dis1[par[i]].begin(),dis1[par[i]].end(),(ayx){r,0})-dis1[par[i]].begin();
int ll=lower_bound(dis2[i].begin(),dis2[i].end(),(ayx){l,0})-dis2[i].begin(),rr=upper_bound(dis2[i].begin(),dis2[i].end(),(ayx){r,0})-dis2[i].begin();
int dist=T.getdis(par[i],x);
ans+=dis1[par[i]][lposl].val-dis1[par[i]][rposr].val-(dis2[i][ll].val-dis2[i][rr].val)+dist*(rposr-lposl-(rr-ll));
}
}
inline short main()
{ freopen("c.in","r",stdin);
innt();
zhong[root=0]=sum=n;
getroot(1,0);
lastroot=root;
work(root,0);
root=lastroot;
for(int i=1;i<=n;++i)
{ dis1[i].push_back((ayx){1000000009,0});
dis2[i].push_back((ayx){1000000009,0});
dis1[i].push_back((ayx){-1,0});
dis2[i].push_back((ayx){-1,0});
sort(dis1[i].begin(),dis1[i].end());
sort(dis2[i].begin(),dis2[i].end());
for(int j=dis1[i].size()-2;j>=0;--j)dis1[i][j].val+=dis1[i][j+1].val;
for(int j=dis2[i].size()-2;j>=0;--j)dis2[i][j].val+=dis2[i][j+1].val;
}
for(int i=1;i<=Q;++i)
{ int u,L,R;
scanf("%lld%lld%lld",&u,&L,&R);
int a=(ans+L)%A,b=(ans+R)%A;
L=min(a,b);
R=max(a,b);
query(u,L,R);
printf("%lld\n",ans);
}
return 0;
}
}
signed main()
{return AYX::main();
}
![POJ 1284 Primitive Roots (欧拉函数&原根定理)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)