pushup操作:求一段区间的和，递归到儿子分别求
pushdown操作(懒标记/延迟标记)：给一段区间加上一个数c，递归到每一个儿子去加

线段树函数

1、pushup(u)、pushdown()
2、build()
3、modify()修改
(1)单点修改
(2)区间修改pushdown
4、query()

区间划分

中点求解：mid = l + r >> 1
儿子：[l, mid],[mid + 1, r]

存储方式

利用堆的存储方式
对于编号是x的一个点
1、父节点是 x/2  (x >> 1)
2、左儿子是 2x   (x << 1)
3、右儿子是 2x+1  (x << 1 | 1)

空间

假设倒数第二层有n个点
从第一层到倒数第二层有sum0 = 1*(1 - 2^n)/(1 - 2) = 2^n - 1 = 2n - 1个点(等比数列求和)
最后一层最多有2n个点，所以整棵树最多有4n-1个点
所以一般开4倍的空间即4n

建立函数build()

void build(int u,int l,int r)
{
    tr[u] = {l,r};
    if(l == r)return;
    int mid = l + r >> 1;
    build(u << 1,l,mid),build(u << 1 || 1,mid + 1, r);
}

例如：划分区间[0,1],mid = (l + r) / 2 = 0
递归到下一层(0,0),(1,1),这时候刚好发现他们相等，但是还没有加到线段树里面，
所以tr[u] = {l,r}要在if(l == r)前面

查询

假设我们要查询的区间是[l,r],树中区间是[Tl,Tr](也就是我们的划分区间)
1、[Tl,Tr]在[l,r]内部,直接返回
2、[Tl,Tr]与[l,r]有交集,如果和左边有交集递归左儿子，和右边有交集递归右儿子
3、不可能出现没有交集的情况
我们访问到的区间在logn级别内

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 2e5 + 10;

struct node
{
    int l,r;
    int v;
}tr[N * 4];

void pushup(int u)//由子节点的信息来更新父节点
{
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

void build(int u,int l,int r)
{
    tr[u] = {l,r};
    if(tr[u].l == tr[u].r)return;
    int mid = l + r >> 1;
    build(u << 1, l, mid),build(u << 1 | 1, mid + 1, r);
}

int query(int u,int l,int r)//这里的l,r是我们询问的区间,u是根节点
{
    //注意我们询问的区间一定会与树中区间有交集，所以不会有越界的情况
    if(tr[u].l >= l && tr[u].r <= r)return tr[u].v;//如果说树中区间在询问区间的内部，那么直接返回

    int v = 0;
    int mid = tr[u].l + tr[u].r >> 1;
    //注意我们此位置不需要考虑区间是否横跨mid,那并不影响得到答案
    //而下一题则需要判断是否有交集，因为如果有交集则不能直接得到答案
    if(l <= mid)v = query(u << 1, l, r);
    if(r > mid)v = max(v, query(u << 1 | 1, l, r));
    return v;
}

void modify(int u,int x,int v)//单点修改，将x位置的数改成v
{
    if(tr[u].l == x && tr[u].r == x)tr[u].v = v;//如果找到叶子结点那么就直接改
    else//否则递归找
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid)modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);//每次更改后要同时更新父节点的值
    }
}

int main()
{
    int last = 0,n = 0;//分别表示上次询问的答案，加了多少个数
    int m,p;cin >> m >> p;
    build(1,1,m);//最会情况下最多加入m个点

    while (m -- )
    {
        int x;char op[2];
        scanf("%s%d",op,&x);
        if(*op == 'Q')
        {
            last = query(1, n - x + 1, n);
            cout << last << endl;
        }
        else 
        {
            //第n + 1个位置没有被使用过,于是将他修改为题目中要求的值
            modify(1,n + 1, ((LL)last + x) % p);
            n ++;
        }
    }
    return 0;
}

/*
    RMQ算法(st表)：
    离线算法
    时间复杂度:O(nlogn)
    适用于询问区间最大值，数组不会产生变化，询问数量很多的情况
*/

/*
    k = log2(len) = log(len) / log(2),c++里面的log是以e为底
    可以选择预处理来加快时间
*/

// 因为是下取整
// k = log2(x):返回的就是满足2^k <= x的最大的k

// lgx是满足2^k <= x的最大的k，以2为底，下取整
// lgx = lg(x/2) + 1 等价变形


#include <iostream>
#include <cstring>
#include <algorithm>
#include<cmath>
using namespace std;

//这个18是log2(2e5)的值
const int N = 2e5 + 10,M = 18;
int a[N];
int f[N][M];
//int lg[N];
int n,m;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

void init()//初始化加预处理
{
    //for(int i = 2; i <= N; i ++)lg[i] = lg[i / 2] + 1;

    for(int j = 0; j < M; j ++)//枚举长度(1 << j)
        for(int i = 1; i + (1 << j) - 1 <= n; i ++)//枚举起点
            if(!j)f[i][j] = a[i];
            else f[i][j] = max(f[i][j - 1],f[i + (1 << (j - 1))][j - 1]);
}

int query(int l,int r)
{
    int len = r - l + 1;
    //int k = lg[len];
    int k = log(len) / log(2);
    return max(f[l][k],f[r - (1 << k) + 1][k]);
}

int main()
{
    n = read();

    for(int i = 1; i <= n; i ++)scanf("%d",&a[i]);

    init();
    m = read();

    while(m --)
    {
        int l,r;l = read(),r = read();
        printf("%d\n",query(l,r));
    }
    return 0;
}

/*
    观察我们的序列，从前往后看的话，我们得不到任何有价值的信息，但是从后往前看的话
    就会发现是让我们找到自身及之前数中第k+1小的数
    1、剩余序列中第k+1小的数
    2、删除这个数
    用树状数组来维护1~n中哪个数被用过了，初始值都是1，如果被使用，直接add(x,-1)即可
    对于第一个操作，我们可以发现从1~n,sum()是单调递增的，我们要找第k+1小的数，所以
    只要从前往后找到第一个sum=k+1的x就好了
*/
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int h[N];
int n;
int ans[N];
int tr[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int x,int c)
{
    for(int i = x; i <= n; i += lowbit(i))tr[i] += c;
}

int sum(int x)
{
    int res = 0;
    for(int i = x; i; i -= lowbit(i))res += tr[i];
    return res;
}

int main()
{
    cin >> n;
    for(int i = 2; i <= n; i ++)cin >> h[i];
    for(int i = 1; i <= n; i ++)add(i,1);

    for(int i = n; i; i --)
    {
        int k = h[i] + 1;//剩下数中第k+1小的
        //二分找到第一个大于等于k的下标
        int l = 1,r = n;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(sum(mid) >= k)r = mid;
            else l = mid + 1;
        }
        ans[i] = r;
        add(r,-1);
    }
    for(int i = 1; i <= n; i ++)cout << ans[i] << endl;
    return 0;
}

/*
    变差分
    修改操作:tr[l] += c,tr[r+1] -= c,
    查询操作：由于我们要求的是a1 + a2 + ... + ax,但是我们的数组存的是a的差分数组，
    所以我们要求二次前缀和，第一次得到ai，第二次得到a的前缀和
    二维表示：
1    b1        a1的值
2    b1 b2     a2的值
3    b1 b2 b3  a3的值
4    ..
5    ..
x    b1 b2 b3 b4... bx
    将图形补全得到：
1    b1 b2 b3 b4...bx
2    b1 b2 b3 b4...bx
3    b1 b2 ...
4    b1 b2 b3...
    .....
    .....
x    b1 b2 b3 b4... bx
    观察得到公式(b1 + b2 + ... + bx)*(x + 1) - (b1 - 2b2 - 3b3 - ... -xbx) = a1 + a2 + ... + ax
    所以我们要维护b的前缀和，i*bi的前缀和
*/

#include<iostream>
using namespace std;
typedef long long LL;

const int N = 1e5 + 10;
int a[N];
int n,m;
LL tr1[N],tr2[N];//tr1维护的是b的前缀和，tr2维护的是i*b的前缀和

int lowbit(int x)
{
    return x & -x;
}

void add(LL tr[],int x, LL c)//在x这个位置上加上c
{
    for(int i = x; i <= n; i += lowbit(i))tr[i] += c;
}

LL sum(LL tr[], int x)//返回x位置子树的和
{
    LL res = 0;
    for(int i = x; i; i -= lowbit(i))res += tr[i];
    return res;
}

LL Fsum(int x)//公式：求a[x]的前缀和
{
    return sum(tr1, x) * (x + 1) - sum(tr2, x);
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)scanf("%d",&a[i]);

    for(int i = 1; i <= n; i++)
    {
        int b = a[i] - a[i - 1];
        add(tr1, i, b),add(tr2, i, (LL)i * b);
    }

    while (m -- )
    {
        char op[2];scanf("%s",op);
        int l,r;scanf("%d%d",&l,&r);
        if(*op == 'Q')
        {
            printf("%lld\n",Fsum(r) - Fsum(l - 1));
        }
        else 
        {
            int c;scanf("%d",&c);
            //a[l] += c
            add(tr1, l, c),add(tr2, l, (LL)c * l);
            //a[r + 1] -= c
            add(tr1, r + 1, -c),add(tr2, r + 1, (LL)(r + 1) * -c);
        }
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include<queue>

using namespace std;
const int N = 20;
int n,m,T;
char g[2][N][N];
bool st[2][N][N];
int ex,ey,ec;//终点坐标
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

struct node
{
    //层数，坐标，距离
    int x,y,c,d;
};

bool check(int c,int x,int y)
{
    return x >= 0 && x < n && y >= 0 && y < m && g[c][x][y] != '*';
}

int bfs()
{
    queue<node>q;
    //初始点始终为(0,0,0)
    st[0][0][0] = true;
    q.push({0,0,0,0});

    while(!q.empty())
    {
        auto t = q.front();//扩展也一定会在t这一层里，不会直接到另一层，因为只是平动
        q.pop();

        if(t.d > T)continue;
        if(t.x == ex && t.y == ey && t.c == ec)return t.d;

        for(int i = 0; i < 4; i ++)
        {
            node s;//扩展变量
            s.x = t.x + dx[i],s.y = t.y + dy[i],s.c = t.c,s.d = t.d;
            if(check(s.c,s.x,s.y) && !st[s.c][s.x][s.y])
            {
                if(g[s.c][s.x][s.y] == '#')
                {
                    //分类讨论
                    if(s.c == 0 && g[1][s.x][s.y] != '*' && g[1][s.x][s.y] != '#')
                    {
                        //传送不消耗距离,故直接将c变化即可
                        s.c = 1,s.d = t.d + 1;
                        st[s.c][s.x][s.y] = true;
                        q.push(s);
                    }
                    else if(s.c == 1 && g[0][s.x][s.y] != '*' && g[0][s.x][s.y] != '#')
                    {
                        s.c = 0,s.d = t.d + 1;
                        st[s.c][s.x][s.y] = true;
                        q.push(s);
                    }
                }
                else 
                {
                    //平动
                    s.d = t.d + 1;
                    st[s.c][s.x][s.y] = true;
                    q.push(s);
                }
            }
        }
    }
    //无解
    return -1;
}

int main()
{
    int q;cin >> q;
    while(q --)
    {
        memset(st, 0, sizeof st);
        cin >> n >> m >> T;
        for(int i = 0; i < n; i ++)scanf("%s",g[0][i]);
        for(int i = 0; i < n; i ++)scanf("%s",g[1][i]);

        for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
        if(g[0][i][j] == 'P')
        {
            ex = i, ey = j, ec = 0;
            break;
        }
        else if(g[1][i][j] == 'P')
        {
            ex = i,ey = j,ec = 1;
            break;
        }


        int x = bfs();
        if(x != -1)cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

//IDA*,启发函数为当前最多的距离结尾的差距
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 10;
int n;
int pos[N];//每一个posi都指向第i个字符串
int len[N];//用来存每个串的长度
char g[N][N];
string s = "ACGT";//我们构造的一个母串

bool dfs(int depth,int max_depth,int pos[])
{
    int maxx = 0;
    //找到最靠前的指针，即为最不符合条件的串的pos到末尾的距离，启发函数
    for(int i = 0; i < n; i++)maxx = max(maxx,len[i] - pos[i]);

    if(maxx + depth > max_depth)return false;//IDA*
    if(maxx == 0 && depth <= max_depth)return true;

    int temp[N];//记录每一层的指针情况(注意不能直接改pos，因为我们会回溯，要恢复现场)
    for(int i = 0; i < 4; i++)
    {
        for(int j = 0; j < n; j ++)
        {
            //首先要明白，选一个字母可能会使序列中的某个字母的指针后移
            //选这个字母对于这个字符串"成功"
            if(g[j][pos[j]] == s[i])
            {
                temp[j] = pos[j] + 1;
            }
            else temp[j] = pos[j];
        }

        if(dfs(depth + 1,max_depth,temp))return true;
    }
    return false;
}

int main()
{
    int t;cin >> t;
    while(t --)
    {
        cin >> n;
        for(int i = 0; i < n; i ++)
        {
            scanf("%s",g[i]);
            len[i] = strlen(g[i]);//存一下每个字符串的长度
        }

        //迭代加深
        int depth = 0;
        memset(pos,0,sizeof pos);//将指针全部指向开头
        while(!dfs(0,depth,pos))depth ++;//当前搜索的深度，最大限度，每一层的指针
        cout << depth << endl;
    }
    return 0;
}

下面是对pos的解释

所以当每一层的pos都指向末尾时即为答案
思考：我们用一个数组来模拟对每一个字符串的指针，也减少了回溯的麻烦，巧妙！

TLE

#include <iostream>
#include <cstring>
#include <algorithm>
#include<queue>

using namespace std;
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
string st,ed;

int f(string s)//启发函数
{
    int cnt = 0;
    for(int i = 0; i < s.size(); i ++)
    if(s[i] != '*' && s[i] != ed[i])cnt ++;
    return cnt;
}

bool check(string s)
{
    for(int i = 0; i < s.size(); i ++)
        if(s[i] != ed[i])return false;
    return true;
}

bool dfs(int u,int max_depth,string s)
{
    if(u + f(s) > max_depth)return false;

    if(check(s))return true;

    int k = s.find('*');
    for(int i = 0; i < 8; i ++)
    {
        //二维坐标变换，一维移动
        int x = k / 5 + dx[i],y = k % 5 + dy[i];
        if(x < 0 || x >= 5 || y < 0 || y >= 5)continue;
        swap(s[x * 5 + y],s[k]);

        if(dfs(u + 1,max_depth,s)) return true;

        swap(s[x * 5 + y],s[k]);
    }
    //无解
    return false;
}

int main()
{
    int t;cin >> t;
    while(t --)
    {
        st = "";
        for(int i = 0; i < 5; i ++)
        for(int j = 0; j < 5; j ++)
        {
            char c;cin >> c;
            st += c;
        }

        ed = "111110111100*110000100000";
        int depth = 0;
        while(depth <= 15 && !dfs(0,depth,st))depth ++;
        if(depth > 15)cout << -1 << endl;
        else cout << depth << endl;
    }
    return 0;
}

数组模拟

#include <iostream>
#include <cstring>
#include <algorithm>
#include<queue>

using namespace std;
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int a[6][6];
int b[6][6] = 
{
    {1,1,1,1,1},
    {0,1,1,1,1},
    {0,0,-1,1,1},
    {0,0,0,0,1},
    {0,0,0,0,0}
};

int f()//启发函数
{
    int cnt = 0;
    for(int i = 0; i < 5; i ++)
    for(int j = 0; j < 5; j ++)
    {
        if(a[i][j] != -1 && a[i][j] != b[i][j])
        cnt ++;
    }
    return cnt;
}

bool check()
{
    for(int i = 0; i < 5;i ++)
    {
        for(int j =0; j < 5; j ++)
        {
            if(a[i][j] != b[i][j])
            return false;
        }
    }
    return true;
}

bool dfs(int u,int max_depth,int sx,int sy)
{
    if(u + f() > max_depth)return false;

    if(check())return true;


    for(int i = 0; i < 8; i ++)
    {
        int x = sx + dx[i],y = sy + dy[i];
        if(x < 0 || x >= 5 || y < 0 || y >= 5)continue;

        swap(a[x][y],a[sx][sy]);
        if(dfs(u + 1,max_depth,x,y))return true;
        swap(a[x][y],a[sx][sy]);
    }
    //无解
    return false;
}

int main()
{
    int t;cin >> t;
    while(t --)
    {
        int sx,sy;
        for(int i = 0; i < 5; i ++)
        for(int j = 0; j < 5; j ++)
        {
            char c;cin >> c;
            if(c == '1')a[i][j] = 1;
            else if(c == '0')a[i][j] = 0;
            else 
            {
                a[i][j] = -1;
                sx = i,sy = j;
            }
        }

        int depth = 0;
        while(depth <= 15 && !dfs(0,depth,sx,sy))depth ++;
        if(depth > 15)cout << -1 << endl;
        else cout << depth << endl;
    }
    return 0;
}

//最短路问题上加了一些特殊的限制
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110;
int g[N][N];
bool st[N][N];
int dist[N][N];
int n,m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int ans = 2e9;

void dfs(int x,int y,int lc,int res)
{
    if(res > ans)return;//最优性剪枝
    if(x == m && y == m)
    {
        ans = res;
        return;
    }

    if(res >= dist[x][y])return;
    dist[x][y] = res;


    for(int i = 0; i < 4; i ++)
    {
        int sx = x + dx[i],sy = y + dy[i],nowc = g[sx][sy];
        if(sx <= 0 || sx > m || sy <= 0 || sy > m || st[sx][sy])continue;

        st[sx][sy] = true;
        if(lc >= 3 && nowc > 0 && nowc < 3)//上次使用了魔法,这次一定不能使用魔法
        {
            //判断颜色
            if((nowc + lc) % 2 == 0)dfs(sx,sy,nowc,res);//颜色相同
            else dfs(sx,sy,nowc,res + 1);
        }

        else if(lc == 1 || lc == 2)//上次没有使用魔法
        {
            //这次使用魔法变成和上次一样的颜色是代价最小的选择(由于不知道下个格子的颜色)
            if(nowc == 0)dfs(sx,sy,lc + 2,res + 2);
            //这次不使用魔法
            else 
            {
                //判断颜色
                if(nowc == lc)dfs(sx,sy,nowc,res);
                if(nowc != lc)dfs(sx,sy,nowc,res + 1);
            }
        }
        //回溯
        st[sx][sy] = false;
    }
}

int main()
{
    memset(dist,0x3f,sizeof dist);
    cin >> m >> n;//m是棋盘大小，n是颜色格点的数量
    for(int i = 0; i < n; i ++)
    {
        int a,b,c;cin >> a >> b >> c;
        g[a][b] = c + 1;
    }

    st[1][1] = true;
    dfs(1,1,g[1][1],0);//当前点的坐标，上一次格点的颜色，当前的代价

    if(ans == 2e9)cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}

如果直接爆搜会MLE，所以要用A*优化，但是A*算法要求有解才能做，否则效率不如普通的bfs
八数码的估价函数：
当前状态中每个数与它目标位置的曼哈顿距离

对于八数码问题而言有一个有解的充要条件:
将八数码按行读出来,如果逆序对为偶数有解，反过来同样成立
例:
1 3 6
4 2 8
7   5

读出来应该是1 3 6 4 2 8 7 5，逆序对为8，则一定有解

#include<iostream>
#include<unordered_map>
#include <queue>
#include<algorithm>
using namespace std;

typedef pair<int, string> PIS;
typedef pair<string, char> PSC;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
#define x first
#define y second
char op[5] = "urdl";//与偏移量数组相对应
string st,ed;

int f(string s)
{
    int res = 0;//求一下所有点到正确位置的曼哈顿距离
    for(int i = 0; i < s.size(); i ++)
    {
        if(s[i] != 'x')
        {
            int t = s[i] - '1';//当前位置所对应的的数的正确位置,下标从0开始的
            res += abs(t / 3 - i / 3) + abs(t % 3 - i % 3);
        }
    }
    return res;
}

string bfs(string st,string ed)
{
    priority_queue<PIS,vector<PIS>,greater<PIS> >q;
    unordered_map<string,int>dist;
    unordered_map<string,PSC>pre;
    q.push({f(st),st});
    dist[st] = 0;

    while(!q.empty())
    {
        auto t = q.top();
        q.pop();

        string state = t.y;
        if(state == ed)break;//找到终点退出搜索

        string source = state;//存一下初始状态，后面更新距离的时候会用
        int k = state.find('x');//对x进行扩展
        for(int i = 0; i < 4; i ++)
        {
            int x = k / 3 + dx[i],y = k % 3 + dy[i];//找到扩展点
            if(x < 0 || x >= 3 || y < 0 || y >= 3)continue;
            swap(state[x * 3 + y],state[k]);
            //A*算法要将所有的分支都加到队列里面，然后根据启发函数去判断最近的一条路
            //但是对于某些一定不合适的点我们可以适当剪枝减少状态数
            //和bfs不同的是，由于我们的搜索顺序不再是一层一层扩展，而是不断向最优解方向扩展
            //所以可能有的点被更新过了但不是最短的路径更新，此时只保证第一次更新是不能保证他是最优解的
            if(!dist[state] || dist[state] > dist[source] + 1)//暂时理解为剪枝
            {
                dist[state] = dist[source] + 1;
                pre[state] = {source,op[i]};//存当前点的前驱节点
                q.push({f(state) + dist[state],state});
            }
            swap(state[x * 3 + y],state[k]);
        }
    }

    string res;
    while(ed != st)//从起点搜，一定要从终点回去，否则，从起点开始找的可能不是到终点的那条路线
    {
        res += pre[ed].y;
        ed = pre[ed].x;
    }
    reverse(res.begin(),res.end());
    return res;
}

int main()
{
    ed = "12345678x";
    for(int i = 0; i < 9; i ++)
    {
        char c;cin >> c;
        st += c;
    }

    int cnt = 0;
    for(int i = 0; i < 9; i ++)
    {
        if(st[i] != 'x')
        {
            for(int j = i + 1; j < 9; j ++)
            {
                if(st[j] != 'x' && st[i] > st[j])cnt ++;
            }
        }
    }

    //逆序对数量为奇数，一定无解，这是充要条件
    if(cnt & 1)cout << "unsolvable" << endl;
    else cout << bfs(st,ed) << endl;
    return 0;
}

#include<iostream>
#include<unordered_map>
#include <queue>
#include<algorithm>
using namespace std;

typedef pair<int, string> PIS;
typedef pair<string, char> PSC;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
#define x first
#define y second
char op[5] = "urdl";//与偏移量数组相对应
string st,ed;

int f(string s)
{
    int res = 0;//求一下所有点到正确位置的曼哈顿距离
    for(int i = 0; i < s.size(); i ++)
    {
        if(s[i] != 'x')
        {
            int t = s[i] - '1';//当前位置所对应的的数的正确位置,下标从0开始的
            res += abs(t / 3 - i / 3) + abs(t % 3 - i % 3);
        }
    }
    return res;
}

string bfs(string st,string ed)
{
    priority_queue<PIS,vector<PIS>,greater<PIS> >q;
    unordered_map<string,int>dist;
    unordered_map<string,PSC>pre;
    q.push({f(st),st});
    dist[st] = 0;

    while(!q.empty())
    {
        auto t = q.top();
        q.pop();

        string state = t.y;
        if(state == ed)break;//找到终点退出搜索

        string source = state;//存一下初始状态，后面更新距离的时候会用
        int k = state.find('x');//对x进行扩展
        for(int i = 0; i < 4; i ++)
        {
            int x = k / 3 + dx[i],y = k % 3 + dy[i];//找到扩展点
            if(x < 0 || x >= 3 || y < 0 || y >= 3)continue;
            swap(state[x * 3 + y],state[k]);
            //A*算法要将所有的分支都加到队列里面，然后根据启发函数去判断最近的一条路
            //但是对于某些一定不合适的点我们可以适当剪枝减少状态数
            if(!dist[state] || dist[state] > dist[source] + 1)//暂时理解为剪枝
            {
                dist[state] = dist[source] + 1;
                pre[state] = {source,op[i]};//存当前点的前驱节点
                q.push({f(state) + dist[state],state});
            }
            swap(state[x * 3 + y],state[k]);
        }
    }

    string res;
    while(ed != st)//从起点搜，一定要从终点回去，否则，从起点开始找的可能不是到终点的那条路线
    {
        res += pre[ed].y;
        ed = pre[ed].x;
    }
    reverse(res.begin(),res.end());
    return res;
}

int main()
{
    ed = "12345678x";
    for(int i = 0; i < 9; i ++)
    {
        char c;cin >> c;
        st += c;
    }

    int cnt = 0;
    for(int i = 0; i < 9; i ++)
    {
        if(st[i] != 'x')
        {
            for(int j = i + 1; j < 9; j ++)
            {
                if(st[j] != 'x' && st[i] > st[j])cnt ++;
            }
        }
    }

    //逆序对数量为奇数，一定无解，这是充要条件
    if(cnt & 1)cout << "unsolvable" << endl;
    else cout << bfs(st,ed) << endl;
    return 0;
}