题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3720
题意：给你一个可变的数组A，有两种操作。操作一：shift(i1, i2....in)，将数组中这些元素的值变为(A[i2], A[i3]....A[in], A[i1])，操作二：Query(L, R)，
查询A[i](L<=i <=R)的和。
题中 Each operation is formatted as a string having no more than 30 characters， 暗示每次参与shift操作的元素不多，所以直接可以使用单点更新的方式来解决问题。
#include <iostream>
#include <cstring>
#include <algorithm>
#define maxn 100010
#define maxl 50
#define inf 1000000000
#define LL(x) x<<1
#define RR(x) x<<1|1
using namespace std; typedef long long LL; //variable define struct tree
{
int l, r;
int mi;
}; tree node[maxn<<];
int n, m, arr[maxn], tmp[maxl], tot; //function define void push_up(int x); void build_tree(int left, int right, int x); int query(int left, int right, int x); void update(int left, int right, int x, int val); void solve(); bool is_number(char ch); int main(void)
{
while (scanf("%d %d", &n, &m) != EOF)
{
tot = ;
build_tree( , n, );
solve();
}
return ;
} void build_tree(int left, int right, int x)
{
node[x].l = left;
node[x].r = right; if (left == right)
{
scanf("%d", &node[x].mi);
arr[tot++] = node[x].mi;
return;
} int lx = LL(x);
int rx = RR(x);
int mid = left + (right - left)/;
build_tree(left, mid, lx);
build_tree(mid + , right, rx);
push_up(x);
} void push_up(int x)
{
if (node[x].l >= node[x].r)
return; int lx = LL(x);
int rx = RR(x);
node[x].mi = min( node[lx].mi, node[rx].mi);
} void update(int left, int right, int x, int val)
{
if (node[x].l == left && node[x].r == right)
{
node[x].mi = val;
return;
}
int lx = LL(x);
int rx = RR(x);
int mid = node[x].l + (node[x].r - node[x].l)/;
if (right <= mid)
update(left, right, lx, val);
else if (left > mid)
update(left, right, rx, val);
else
{
update(left, mid, lx, val);
update(mid + , right, rx, val);
}
push_up( x);
} int query(int left, int right, int x)
{
if (node[x].l == left && node[x].r == right)
{
return node[x].mi;
}
int mid = node[x].l + (node[x].r - node[x].l)/;
int lx = LL(x);
int rx = RR(x);
if (right <= mid)
return query(left, right, lx);
else if (left > mid)
return query(left, right, rx);
else
return min( query(left, mid, lx), query(mid + , right, rx));
} void solve()
{
char str[];
while (m--)
{
int x = , y = , ind;
scanf("%s", str);
if (str[] == 'q')
{
ind = ;
while (!is_number(str[ind]))
ind++;
x = ;
while (is_number(str[ind]))
{
x *= ;
x += str[ind] - '';
ind++;
}
while (!is_number(str[ind]))
ind++;
y = ;
while (is_number(str[ind]))
{
y *= ;
y += str[ind] - '';
ind++;
}
printf("%d\n", query( x, y, ));
}
else
{
ind = , tot = ;
while (str[ind] != ')')
{
if (is_number(str[ind]))
{
x = ;
while (is_number(str[ind]))
{
x *= ;
x += str[ind] - '';
ind++;
}
tmp[tot++] = x;
}
else
ind++;
} int swap = arr[tmp[]];
for (int i = ; i < tot - ; ++i)
arr[tmp[i]] = arr[tmp[i+]];
arr[tmp[tot - ]] = swap;
for (int i = ; i < tot; ++i)
{
update( tmp[i], tmp[i], , arr[tmp[i]]);
}
}
}
} bool is_number(char ch)
{
if (ch >= '' && ch <= '')
return true;
return false;
}