记录编号	325278	评测结果	AAAAAAAAAA
题目名称	[HNOI 2010] 弹飞绵羊	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	1.616 s
提交时间	2016-10-19 13:38:09	内存使用	1.07 MiB

#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <list>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
struct node
{
    node *ch[2];
    #define LC ch[0]    
    #define RC ch[1]
    node *f;
    int size, rev;
    node():size(1), rev(0)
    {
        f = LC = RC = NULL;
    }
    void pushup()
    {
        size = 1;
        for(int i = 0; i <= 1; i++)if(ch[i])size += ch[i]->size;
    }
    void pushdown()
    {
        if(rev)
        {
            for(int i = 0; i <= 1; i++)if(ch[i])ch[i]->rev ^= 1;
            rev = 0;
            swap(LC, RC);
        }
    }
}soilder, *null = &soilder;

node *new_node()
{
    node *t = new node();
    t -> LC = t -> RC = t -> f = null;
}
class lct
{
public:
    inline bool is_root(node *t)
    {
        return t == null || (t->f->LC != t && t->f->RC != t);
    }
    
    void rotate(node *t) //把t往上旋
    {
        if(is_root(t))return;
        node *m = t->f;   //它的父节点
        if(!is_root(m))
        {
            if(m == m->f->LC) //是左孩子
                m->f->LC = t;
            else m->f->RC = t;  
        }
        t->f = m->f;
        //以上 用t替代了m的位置
        //-----------------------
        
        //这是一个单旋转
        int d = (t == m->RC);
        m->ch[d] = t->ch[d^1];
        if(t->ch[d^1])t->ch[d^1]->f = m;  //注意多维护了一个"父节点"信息。
        t->ch[d^1] = m;  
        m->f = t;    //m成了t的子节点
        m->pushup();
        //-------------------------
        
        //t成为了新的(这个子树的)根
        t->pushup();
    }
    
    /*
    void recalc(node *t)
    {
        stack<node *> s; //用一个栈，模拟递归顺序
        s.push(t);
        for(node *p = t; !is_root(p); p = p -> f)
            s.push(p -> f);
        while(s.size())
        {
            s.top() -> pushdown();
            s.pop();
        }
    }
    */
    void splay(node *t)
    {
        //recalc(t);   //太慢了...
        t -> pushdown();
        while(!is_root(t))
        {
            node *m = t->f;
            m -> f -> pushdown();  //从上往下的顺序pushdown
            m -> pushdown();
            t -> pushdown();
            if(is_root(m))   //m已经是根了
                rotate(t);   //t向上单旋一次，到根
            else
            {
                if(t == m->f->LC->LC || t == m->f->RC->RC) //t,m,m->f在一条线上
                    rotate(m); //也就是
                    //              m->f               m
                    //              /                 / \
                   //              m         ->      t  m->f(呸，它已经不是m的父节点了)
                   //             /
                   //            t               
                else
                    rotate(t);  //自行脑补
                rotate(t);
            }
        }
        t -> pushup();
    }
    node *access(node *t)
    {
        node *m = null;
        while(t != null)
        {
            splay(t);
            t -> RC = m;  //最开始一次t的RC变成了null，就是断开了...
            m -> f = t;
            t -> pushup();
            
            m = t;
            t = t -> f;
        }
        return m;
    }
    inline void makeroot(node *t)
    {
        access(t);
        splay(t);
        t -> rev ^= 1;
    }
    inline void link(node *t, node *m) //连接后t是m的孩子节点
    {
        makeroot(t);
        t -> f = m;
        access(t);
    }
    inline void cut(node *t)
    {
        access(t);
        splay(t);
        t -> LC = t -> LC -> f = null;
        t -> pushup();
    }
    bool is_connected(node *t, node *m)
    {
        while(t -> f != null)t = t -> f;
        while(m -> f != null)m = m -> f;
        return t == m;
    }
}t;

int fast_read()
{
    int r;
    char c;
    bool sig = false;
    while(c = getchar())    
    {
        if(c >= '0' && c <= '9')
        {
            r = c^0x30;
            break;
        }else if(c == '-')sig = true;
    }
    while(isdigit(c = getchar()))
        r = (r<<3)+(r<<1)+(c^0x30);
    return sig? -r:r;
}
void clear(int t)
{
    while(t--)getchar();
}
#define MAXN 200001
node *ns[MAXN];
int main()
{
    freopen("bzoj_2002.in", "r", stdin);
    freopen("bzoj_2002.out", "w", stdout);
    int n, m;
    n = fast_read();
    null -> size = 0;
    null -> LC = null -> RC = null -> f = null;
    for(int i = 0; i <= n; i++)
        ns[i] = new_node();
    for(int i = 0; i < n; i++)
        t.link(ns[i], ns[min(n, i+fast_read())]);
    m = fast_read();
    while(m--)
    {
        int op = fast_read();
        if(op == 1)
        {
            int a = fast_read();
            t.makeroot(ns[n]);
            t.access(ns[a]);
            t.splay(ns[a]);
            printf("%d\n", ns[a]->LC->size);
        }else
        {
            int a = fast_read();
            int b = fast_read();
            t.cut(ns[a]);
            t.link(ns[a], ns[min(n, a+b)]);
        }
    }
    return 0;
}