[GDSOI2017]中学生数据结构题(树链剖分+fhq treap)
题面
给出一棵树,支持三种操作
- ADD:路径加
- QUERY:路径求和
- SHIFT:树上路径整体循环移动一位(如：原路径上的权值依次是：1,4,5,3，操作完后变成：3,1,4,5)
分析
考验数据结构功底和代码能力的好题。似乎有个实现难度更低的LCT解法但没看懂。
考虑序列上的问题,整体循环移动显然很简单,Split出那个跑到前面的数,然后再交换顺序Merge回去。
那么可以树剖,把路径分成\(O(\log n)\)个区间。先考虑从\(x\)到\(lca(x,y)\)的路径,对于每个区间,我们要把区间内的数向左移一位(因为向上走DFS序更小),然后要弹出原来最左边的数,还要把上一个区间弹出来的数插到区间右边。从\(y\)到\(lca(x,y)\)的路径相反。于是可以在非旋Treap里写一个函数进行这些操作,Shift时先跳一遍求出这些区间,然后按路径顺序逐个操作即可。
说起来很简单，但代码有很多细节。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define maxn 100000
#define maxlogn 20
using namespace std;
template<typename T> void qread(T &x){
x=0;
T sign=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') sign=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
x=x*sign;
}
template<typename T> void qprint(T x){
if(x<0){
putchar('-');
qprint(-x);
}else if(x==0){
putchar('0');
return;
}else{
if(x>=10) qprint(x/10);
putchar('0'+x%10);
}
}
typedef long long ll;
int n,m;
struct fhq_treap {
#define lson(x) (tree[x].ls)
#define rson(x) (tree[x].rs)
struct node {
int ls;
int rs;
ll val;
int dat;
int sz;
ll sum;
ll mark;
node() {
}
node(ll _val) {
ls=rs=0;
val=sum=_val;
dat=rand();
sz=1;
mark=0;
}
} tree[maxn*maxlogn+5];
int ptr;
int root=0;
int New(ll val) {
tree[++ptr]=node(val);
return ptr;
}
void push_up(int x) {
tree[x].sz=tree[lson(x)].sz+1+tree[rson(x)].sz;
tree[x].sum=tree[lson(x)].sum+tree[x].val+tree[rson(x)].sum;
}
void add_tag(int x,ll val) {
tree[x].val+=val;
tree[x].sum+=val*tree[x].sz;
tree[x].mark+=val;
}
void push_down(int x) {
if(tree[x].mark) {
if(lson(x)) add_tag(lson(x),tree[x].mark);
if(rson(x)) add_tag(rson(x),tree[x].mark);
tree[x].mark=0;
}
}
int merge(int x,int y) {
push_down(x);
push_down(y);
if(!x||!y) return x+y;
if(tree[x].dat<tree[y].dat) {
lson(y)=merge(x,lson(y));
push_up(y);
return y;
} else {
rson(x)=merge(rson(x),y);
push_up(x);
return x;
}
}
void split(int now,int k,int &x,int &y) {
if(!now) {
x=y=0;
return;
}
push_down(now);
if(k<=tree[lson(now)].sz) {
y=now;
split(lson(now),k,x,lson(y));
} else {
x=now;
split(rson(now),k-tree[lson(now)].sz-1,rson(x),y);
}
push_up(now);
}
void update(int l,int r,ll v) {
int x,y,z;
split(root,r,y,z);
split(y,l-1,x,y);
add_tag(y,v);
root=merge(merge(x,y),z);
}
ll query(int l,int r) {
int x,y,z;
split(root,r,y,z);
split(y,l-1,x,y);
ll ans=tree[y].sum;
root=merge(merge(x,y),z);
return ans;
}
ll lshift(int l,int r,ll v){
//把[l+1,r]向左移一格,把a[r]设成v,并返回被弹出的a[l] 用于路径上升段(x->lca)
int x/*[1,l-1]]*/,y/*l*/,z/*[l+1,r]*/,w/*[r+1,n]*/;
split(root,r,z,w);
split(z,l-1,x,z);
split(z,1,y,z);//注意这里z存的是[l+1,r],所以传参是1而不是l
ll ans=tree[y].val;
root=merge(merge(x,z),merge(New(v),w));
return ans;
}
ll rshift(int l,int r,ll v) {
//把[l,r-1]向右移一格,把a[l]设成v,并返回被弹出的a[r] 用于路径下降段(lca->y)
int x/*[1,l-1]]*/,y/*[l,r-1]*/,z/*r*/,w/*[r+1,n]*/;
split(root,r,z,w);
split(z,r-1,y,z);
split(y,l-1,x,y);
ll ans=tree[z].val;
root=merge(merge(x,New(v)),merge(y,w));
return ans;
}
void push_back(ll v){
root=merge(root,New(v));
}
} T;
struct edge{
int from;
int to;
int next;
}E[maxn*2+5];
int esz=1;
int head[maxn+5];
void add_edge(int u,int v){
esz++;
E[esz].from=u;
E[esz].to=v;
E[esz].next=head[u];
head[u]=esz;
}
int tim;
int deep[maxn+5],sz[maxn+5],fa[maxn+5],son[maxn+5],top[maxn+5],dfn[maxn+5];
void dfs1(int x,int f){
fa[x]=f;
deep[x]=deep[f]+1;
sz[x]=1;
for(int i=head[x];i;i=E[i].next){
int y=E[i].to;
if(y!=f){
dfs1(y,x);
sz[x]+=sz[y];
if(sz[y]>sz[son[x]]) son[x]=y;
}
}
}
void dfs2(int x,int t){
top[x]=t;
dfn[x]=++tim;
if(son[x]) dfs2(son[x],t);
for(int i=head[x];i;i=E[i].next){
int y=E[i].to;
if(y!=fa[x]&&y!=son[x]) dfs2(y,y);
}
}
ll query(int x,int y){
ll ans=0;
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]) swap(x,y);
ans+=T.query(dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
ans+=T.query(dfn[x],dfn[y]);
return ans;
}
void update(int x,int y,int v){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]) swap(x,y);
T.update(dfn[top[x]],dfn[x],v);
x=fa[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
T.update(dfn[x],dfn[y],v);
}
void shift(int x,int y){
static int cnt[2],st[2][maxn+5];//暂存分成的每段区间
int now=0;//当前处理的重链在哪一段 0:x->lca 1:lca->y
int last=T.query(dfn[y],dfn[y]);//把a[y]给路径起点x
cnt[0]=cnt[1]=0;
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]){
swap(x,y);
now^=1;
}
st[now][++cnt[now]]=x;
x=fa[top[x]];
}
if(deep[x]>deep[y]){
swap(x,y);
now^=1;
}
for(int i=1;i<=cnt[0];i++){
int u=st[0][i];
last=T.lshift(dfn[top[u]],dfn[u],last);
}
//处理lca那一段
if(now==0) last=T.rshift(dfn[x],dfn[y],last);
else last=T.lshift(dfn[x],dfn[y],last);
for(int i=cnt[1];i>=1;i--){//因为是从下往上跳,而路径是从上往下，要倒序
int u=st[1][i];
last=T.rshift(dfn[top[u]],dfn[u],last);
}
}
int main() {
int u,v,w;
char cmd[10];
qread(n);
for(int i=1;i<n;i++){
qread(u);
qread(v);
add_edge(u,v);
add_edge(v,u);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=n;i++) T.push_back(0);
qread(m);
for(int i=1;i<=m;i++){
scanf("%s",cmd);
if(cmd[0]=='A'){
qread(u);
qread(v);
qread(w);
update(u,v,w);
}else if(cmd[0]=='Q'){
qread(u);
qread(v);
qprint(query(u,v));
putchar('\n');
}else{
qread(u);
qread(v);
shift(u,v);
}
}
}
/*
5
1 2
1 3
3 4
3 5
6
ADD 1 5 2
ADD 3 4 1
QUERY 1 4
SHIFT 1 4
QUERY 3 4
*/