[GDSOI 2017] [JZOJ 5107] 중 학생 데이터 구조 문제

8351 단어 나무 사슬 분할정식 경기밸 런 스 트 리
Description
나무 에 있 는 경로 구간 에 2 를 추가 합 니 다. 나무 에 있 는 경로 구간 조회 와 3. 나무 에 있 는 경 로 를 전체적으로 한 자리 회전 합 니 다. (예 를 들 어 원래 경로 의 가중치 는 다음 과 같 습 니 다. 1, 2, 3, 4, 조작 이 끝 난 후에 4, 1, 2, 3)
시간: 2S
Solution
이것 은 분명히 체인 절개 세트 Splay 잖 아 요. 회전 은 마지막 하 나 를 지우 고 앞으로 가 는 것 과 같 아 요.
엘 시 티 가 더 쉽다 고 들 었 어 요.
복잡 도: O (nlog (n))
Code 
#include 
#include 
#include 
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define efo(i,q) for(int i=A[q];i;i=B[i][0])
using namespace std;
typedef long long LL;
const int N=100500;
int read(int &n)
{
    char ch=' ';int q=0,w=1;
    for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
    if(ch=='-')w=-1,ch=getchar();
    for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;
}
int m,n,ans;
int B[2*N][2],A[N],B0;
struct qqww
{
    int fa,lt,zx,si,c;
}a[N];
struct qwqw
{
    int l,r,fa,si,la;
    LL v,sum;
}b[N];
int root,b0;
void link(int q,int w)
{
    B[++B0][0]=A[q];A[q]=B0,B[B0][1]=w;
    B[++B0][0]=A[w];A[w]=B0,B[B0][1]=q;
}
int dfsf(int q,int fa,int c)
{
    a[q].fa=fa,a[q].si=1;a[q].c=c;
    efo(i,q)if(B[i][1]!=fa)a[q].si+=dfsf(B[i][1],q,c+1);
    return a[q].si;
}
void dfs(int q,int fa,int lt)
{
    a[q].lt=(lt?lt:lt=q);
    a[q].zx=++b0;
    int mx=0;
    efo(i,q)if(B[i][1]!=fa)if(a[mx].si1]].si)mx=B[i][1];
if(mx)dfs(mx,q,lt);
efo(i,q)if(B[i][1]!=fa&&B[i][1]!=mx)dfs(B[i][1],q,0);
}
bool SD(int q){return q==b[b[q].fa].r;}
void merge(int q)
{
b[q].si=b[b[q].l].si+1+b[b[q].r].si;
b[q].sum=b[b[q].l].sum+b[q].v+b[b[q].r].sum;
}
void doit(int q)
{
if(!b[q].la)return;
b[q].v+=b[q].la;
b[q].sum+=(LL)b[q].si*(LL)b[q].la;
if(b[q].l)b[b[q].l].la+=b[q].la;
if(b[q].r)b[b[q].r].la+=b[q].la;
b[q].la=0;
}
void rotate(int q)
{
int t=b[q].fa;
if(!SD(q))
{
b[t].l=b[q].r;
b[b[q].r].fa=t;
b[q].r=t;
}else
{
b[t].r=b[q].l;
b[b[q].l].fa=t;
b[q].l=t;
}
if(SD(t))b[b[t].fa].r=q;
else b[b[t].fa].l=q;
b[q].fa=b[t].fa;
b[t].fa=q;
merge(t);
merge(q);
b[0].l=b[0].r=b[0].fa=0;
}
int Splay(int q,int T)
{
while(b[q].fa!=T)
{
if(b[b[q].fa].fa!=T)
if(SD(q)==SD(b[q].fa))rotate(b[q].fa);
else rotate(q);
rotate(q);
}
if(!T)root=q;
}
int search(int q,int w)
{
doit(b[q].l),doit(b[q].r);
if(b[b[q].l].si>=w)return search(b[q].l,w);
w-=b[b[q].l].si+1;
if(!w)return q;
return search(b[q].r,w);
}
void changea(int q,int w,int e)
{
Splay(search(root,q-1),0);
Splay(w=search(root,w+1),root);
b[b[w].l].la+=e;
doit(b[w].l);
merge(w),merge(root);
}
LL Gsum(int q,int w)
{
Splay(search(root,q-1),0);
Splay(w=search(root,w+1),root);
return b[b[w].l].sum;
}
int DLT(int q)
{
Splay(search(root,q-1),0);
Splay(q=search(root,q+1),root);
int ans=b[q].l;
b[b[q].l].fa=0;b[q].l=0;
merge(q),merge(root);
return ans;
}
void IST(int q,int w)
{
Splay(search(root,q),0);
b[w].l=0;b[w].r=b[root].r;b[w].fa=root;
b[root].r=w;if(b[w].r)b[b[w].r].fa=w;
merge(w),merge(root);
}
void SWAP_v(int q,int w)
{
if(q>w)swap(q,w);
Splay(q=search(root,q),0);
Splay(w=search(root,w),root);
swap(b[q].v,b[w].v);
merge(w),merge(q);
}
void modifya(int q,int w,int e)
{
while(a[q].lt!=a[w].lt)
{
if(a[a[q].lt].clt].c)swap(q,w);
int t=a[q].lt;
changea(a[t].zx,a[q].zx,e);
q=a[t].fa;
}
if(a[q].cq,w);
changea(a[w].zx,a[q].zx,e);
}
LL find(int q,int w)
{
LL ans=0;
while(a[q].lt!=a[w].lt)
{
if(a[a[q].lt].clt].c)swap(q,w);
int t=a[q].lt;
ans+=Gsum(a[t].zx,a[q].zx);
q=a[t].fa;
}
if(a[q].cq,w);
return ans+Gsum(a[w].zx,a[q].zx);
}
int c1[N][2],c2[N][2],c10,c20;
void change_shift(int q,int w)
{
if(q==w)return;
swap(q,w);c10=c20=0;
while(a[q].lt!=a[w].lt)
{
if(a[a[q].lt].c>a[a[w].lt].c)c1[++c10][0]=q,c1[c10][1]=a[q].lt,q=a[a[q].lt].fa;
else c2[++c20][1]=w,c2[c20][0]=a[w].lt,w=a[a[w].lt].fa;
}
if(a[q].c>a[w].c)c1[++c10][0]=q,c1[c10][1]=w;
else c2[++c20][1]=w,c2[c20][0]=q;
q=w=0;
fo(i,1,c10)
{
q=c1[i][0],w=c1[i][1];
int q1=DLT(a[q].zx);
IST(a[w].zx-1,q1);
if(i!=c10)SWAP_v(a[w].zx,a[c1[i+1][0]].zx);
}
int t=w;
for(;c20;c20--)
{
q=c2[c20][0],w=c2[c20][1];
if(t)SWAP_v(a[t].zx,a[q].zx);
int q1=DLT(a[q].zx);
IST(a[w].zx-1,q1);
t=w;
}
}
int main()
{
freopen("shift.in","r",stdin);
freopen("shift.out","w",stdout);
int q,w,e;
read(n);
fo(i,1,n-1)read(q),read(w),link(q,w);
dfsf(1,0,1);
b0=root=1;
dfs(1,0,0);
fo(i,1,n+1)b[i].r=i+1,b[i+1].fa=i,b[i].si=n+2-i+1;
b[n+2].si=1;b0++;
read(m);
fo(i,1,m)
{
char ch=' ';
while(ch<'A'||ch>'Z')ch=getchar();
if(ch=='A')
{
read(q),read(w),read(e);
modifya(q,w,e);
}else if(ch=='S')
{
read(q),read(w);
change_shift(q,w);
}else
{
read(q),read(w);
printf("%lld",find(q,w));
}
}
return 0;
}
[2118] 데이터 구조 실험의 링크 3: 링크 의 역 치
STL queue && priority_queue

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage