1. 题目

传送门= ̄ω ̄=

2. 题解

比较弱智的模板题
听说可以用分块做
然而我们是来做lct的模板题的呀!
不难发现题目中隐藏了一棵树!
如果能从i跳到j,那么就设j为i的父亲(在树上)
设所有出界了的位置的编号都为n+1(就好像在n+1的位置竖了一面墙,你弹上去,pia,就掉下来啦!)
然后这样子对于询问位置i要弹几次弹出也就是询问节点i的深度啦!
因为有连接、断开,因此用lct(雾)
只要实现link和cut就行了,询问深度的话。。。
询问点a,先evert (n+1),让n+1(出界节点)成为根,再access (a),让n+1和a在一个链上(一个splay中),然后splay (a),把a旋到根,最后答案就是a的子树大小

代码:

#include <bits/stdc++.h>
#define NS (200005)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c=getchar();dig=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct N{int f,s[2],r,siz;N(){f=s[0]=s[1]=r=siz=0;}}e[NS];
bool isroot(int a){return e[e[a].f].s[0]!=a&&e[e[a].f].s[1]!=a;}
void update(int a){e[a].siz=e[e[a].s[0]].siz+e[e[a].s[1]].siz+1;}
void pdown(int a)
{
    if(!e[a].r)return;
    e[a].r=0,e[e[a].s[0]].r^=1,e[e[a].s[1]].r^=1,swap(e[a].s[0],e[a].s[1]);
}
bool pos(int a){return e[e[a].f].s[1]==a;}
void rot(int a)
{
    int f=e[a].f,g=e[f].f,p=pos(a);
    if(!isroot(f))e[g].s[pos(f)]=a;
    e[a].f=g,e[f].f=a,e[f].s[p]=e[a].s[!p],e[a].s[!p]=f;
    if(e[f].s[p])e[e[f].s[p]].f=f;
    update(f),update(a);
}
stack<int> st;
void splay(int a)
{
    st.push(a);
    for(int i=a;!isroot(i);i=e[i].f)st.push(e[i].f);
    while(!st.empty())pdown(st.top()),st.pop();
    while(!isroot(a))
        if(isroot(e[a].f))rot(a);
        else if(pos(a)^pos(e[a].f))rot(a),rot(a);
        else rot(e[a].f),rot(a);
}
void acc(int a){int b=0;while(a)splay(a),e[a].s[1]=b,update(a),b=a,a=e[a].f;}
void evert(int a){acc(a),splay(a),e[a].r^=1;}
void link(int a,int b){evert(a),e[a].f=b;}
void cut(int a,int b){evert(b),acc(a),splay(a),e[a].s[0]=e[b].f=0;}
int n,m,nxt[NS];
int main()
{
    IN(n);
    for(int i=1,j;i<=n;i++)IN(j),e[i].f=min(i+j,n+1),nxt[i]=e[i].f;
    IN(m);
    for(int i=1,a,b,c;i<=m;i++)
        if(IN(a),IN(b),b++,a==1)
            evert(n+1),acc(b),splay(b),printf("%d\n",e[e[b].s[0]].siz);
        else IN(c),cut(b,nxt[b]),link(b,min(b+c,n+1)),nxt[b]=min(b+c,n+1);
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *