开始交了一发 \(\rm STL-List\) 想水掉,结果给 \(\verb!RE!\) 飞了。
于是老老实实手打结构体链表。
题目大意
你有 \(n\) 个盒子在桌子上的一条线上从左到右编号为 \(1\cdots n\)。你的任务是模拟四种操作:
-
1 X Y
:移动盒子编号 \(X\) 到盒子编号 \(Y\) 的左边(如果 \(X\) 已经在 \(Y\) 的左边了就忽略)。 -
2 X Y
:移动盒子编号 \(X\) 到盒子编号 \(Y\) 的右边(如果 \(X\) 已经在 \(Y\) 的右边了就忽略)。 -
3 X Y
:交换盒子编号 \(X\) 与盒子编号 \(Y\) 的位置。 -
4
:将整条线反转。
对于每组数据,输出他们奇数位置的编号的和。
题目分析
\(1,2,3\) 操作显然可以用链表 \(\operatorname{O}(1)\) 处理掉,我们重点考虑操作 \(4\)。
我们如果手动掉头的话,\(\rm STL\) 可以来,但是链表显然会 \(\verb!T!\) 飞。
有因为我们只求最后的答案,中间的形态不需要去管,想到打标记。
\(rev\) 表示该链表处于掉头状态下,当且仅当 \(rev=1\)。
注意到 \(\operatorname{xor}\) 运算一个有趣的性质:
\(1\operatorname{xor}1=0,0\operatorname{xor}1=1\)。
所以如果当前是 \(4\) 操作,那么令 \(rev\gets rev~\operatorname{xor}1\)。
如果当前链表倒过来了,并且操作为 \(1\) 或 \(2\),那么————
我们再来观察一个有趣的性质:
\(2\operatorname{xor}3=1,1\operatorname{xor}3=2\)。
(异或狂人了属于是)
于是令 \(opt\gets opt~\operatorname{xor}3\),\(opt\) 表示指令序号。
进行操作就好了,这很好理解,毕竟序列翻过来了嘛。
最后暴力求解,答案 \(ans=List[i].val\{i\in 2\times k+1,k\in \mathcal{N}\}\)。
注意特判:
\(ans\gets \dfrac{n\times(n+1)}{2}-ans\),当且仅当 \(n=2\times k(k\in \mathcal{N})\) 且 \(rev=1\)。
表示当前序列长度为偶数,并且被翻转了过来。
举个例子:
1 -> 2 -> 3 -> 4 -> 5 -> 6
=>
6 -> 5 -> 4 -> 3 -> 2 -> 1
此时 \(ans=\sum\limits_{i=1}^{\tfrac{n}{2}-1}(2\times i+1)-ans\),就是上面那个式子。
代码
这里给出的代码并没有考虑本题的多种情况,请读者 \(\rm Coding\) 时注意初始化问题。
______ 见祖宗
const int MA=100005;
struct List
{
int val;
int pre;
int nxt;
};
List lst[MA];
int n,m;
inline void add(int u,int v)//u -> v
{
lst[u].nxt=v;
lst[v].pre=u;
}
#undef int
int main(void)
{
#define int long long
n=read(),m=read();
lst[0].nxt=1;
for(register int i=1;i<=n;i++)
{
lst[i].val=i;
lst[i].pre=i-1,lst[i].nxt=i+1;
}
lst[n].nxt=0;
int rev=0;
for(register int i=1;i<=m;i++)
{
int opt=read();
if(rev==1 && opt<=2)
{
opt^=3;
}
if(opt==1)//x 移到 y 的左边
{
int x=read(),y=read();
if(lst[y].pre!=x)
{
add(lst[x].pre,lst[x].nxt);
int t=lst[y].pre;
add(x,y);
add(t,x);
}
}
else if(opt==2)//x 移到 y 的右边
{
int x=read(),y=read();
if(lst[y].nxt!=x)
{
add(lst[x].pre,lst[x].nxt);
int t=lst[y].nxt;
add(y,x);
add(x,t);
}
}
else if(opt==3)
{
int x=read(),y=read();
if(lst[y].nxt==x)
{
swap(x,y);
}
if(lst[x].nxt==y)
{
int t=lst[x].pre;
add(x,lst[y].nxt);
add(y,x);
add(t,y);
}
else
{
int ta=lst[x].pre,tb=lst[x].nxt;
add(lst[y].pre,x);
add(x,lst[y].nxt);
add(ta,y);
add(y,tb);
}
}
else
{
rev^=1;
}
}
int ans(0),idx(0);
for(register int i=lst[0].nxt;i;i=lst[i].nxt)
{
idx++;
if(idx%2==1)
{
ans+=lst[i].val;
}
}
if(rev==1 && n%2==0)
{
printf("%lld\n",(n*(n+1)>>1ll)-ans);
return 0;
}
printf("%lld\n",ans);
return 0;
}