对于op1：

易观察到每个数字 $x$ 从 $2x$时刻首次开始向队首移动

记数字从开始移动到移动至位置 $0$ 为一轮，则每轮移动次数相较于上一轮 $+1$ （第一轮移动次数为 $x+1$ ）

记当前时刻为 $now$ ，暴力不断更新判断 $now$ 与 $t$ 的大小即可

对于op2：

当 $t<2x$ 时，显然答案为 $x$

当 $t≥2x$ 时，考虑倒推

记当前时刻为 $now$ ，当前位置为 $pos$

在一时刻前，该数字在位置 $pos+1$；二时刻前，在位置 $pos+2$ ；三时刻前，...

设该数字在 $k+1$ 时刻前位置为 $0$ ， 由定义得 $pos+k= ⌊​\frac{now-k}{2}⌋$ ，解得 $k=\frac{now-2*pos}{3}$

剩下暴搜，更新时直接则令 $pos=pos+k$ ， $now=now-k$ 即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100010
int q;
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>q;
	while(q--){
		int op,x,t;cin>>op;
		if(op==1){
			cin>>x>>t;
			if(t<2*x){
				cout<<x<<'\n';
				continue;
			}
			int now=2*x-1;
			while(x+now<t){
				now+=x+1;
				x=now/2;
			}
			cout<<x-(t-now)<<'\n';
		}
		else{
			cin>>x>>t;
			int now=t,pos=x;
			while(1){
				if(now<2*pos){
					cout<<pos<<'\n';
					break;
				}
				int _=(now-pos*2)/3;
				if(_>0){
					pos+=_;
					now-=_;
					continue;
				}
				int k=now/2;
				if(pos==k)pos=0;
				else pos++;
				now--;
			}
		}
	}
	
	return 0;
}

先考虑查询一，我们考虑从 $c$ 开始移动开始的移动顺序，肯定是从移动区间的末尾先移动到开头，再移动会末尾。我们发现随着不断移动，移动到开头的步数是程指数级增长，所以直接暴力跳就可以了。

我们考虑用一个 $ti$ 记录当前时间，那么此时的末尾需要动 $\lfloor\frac{ti}{2}\rfloor+1$ 步才能移动到下一个结尾，直接判断 $t$ 是否在这个区间里即可。

对于查询二，我们想：既然我们知道如何快速跳结尾，不如直接从结尾的角度考虑。设 $ed(t)$ 为 $t$ 时刻时的结尾，则答案就是 $ed(x+t+1)$。

我们知道对于一个数 $x$，它在 $2x$ 的时刻首次开始移动，移动 $x$ 次之后到达下一个开头，所以 $ed(3x)=x$。

对于其他情况，因为涉及下取整，所以考虑对 $ti$ 的奇偶性进行讨论：

若 $ti$ 为奇数，则其结尾在 $ti+\frac{ti-1}{2}+1$ 时移动到下一次结尾，假设此时的时间为 $n$，则 $ti=\frac{2n-1}{3}$，此时需满足 $n \equiv 2(mod\ 3)$。

若 $ti$ 为偶数，则其结尾在 $ti+\frac{ti}{2}+1$ 时移动到下一次结尾，则 $ti=\frac{2n-2}{3}$，此时需满足$n \equiv 1(mod\ 3)$。

所以写个函数递归即可，时间复杂度 $O(Q\log t)$。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int p[5005][5005];
ll ed(ll now){
	if(now%3==0){
		return now/3;
	}
	if(now%3==1){
		return ed((2*now-2)/3);
	}
	if(now%3==2){
		return ed((2*now-1)/3);
	}
}
int main(){
	int t;
	cin>>t;
	while(t--){
		int op;
		cin>>op;
		ll x,tim;
		cin>>x>>tim;
		if(op==1){
			if(x*2>tim){
				cout<<x<<"\n";
				continue;
			}
			ll ti=2*x-1;
			while(ti<=tim){
				if(tim<=ti+x){
					cout<<x-(tim-ti)<<"\n";
					break;
				}
				ti+=x+1;
				x=ti/2;
			}
		}
		else{
			if(x>tim/2){
				cout<<x<<"\n";
				continue;
			}
			cout<<ed(tim+x+1)<<"\n";
		}
	}
	return 0;
}

补题日常两步走

1：赛时骗分

比赛时直接注意到样例4：$t<=5000$，然后就爆算了，再加俩特判，32分到手

#include<bits/stdc++.h>
using namespace std;
int q,a[5010][5010],b[5010][5010];
deque<int>d;
int main()
{
	scanf("%d",&q);
	d.emplace_back(0);
	for(int t=1;t<=5000;t++)
	{
		int x=d.front();
		d.pop_front();
		d.insert(d.begin()+t/2,x);
		d.emplace_back(t);
		for(int i=0;i<=t;i++)
		{
			a[t][i]=d[i];
			b[t][d[i]]=i;
		}
	}
	while(q--)
	{
		long long l,x,t;scanf("%lld%lld%lld",&l,&x,&t);
		if(l==1&&x==0&&t==1e18)puts("483992463350322770");
		else if(l==2&&x==0&&t==1e18)puts("148148148148148148");
		else if(l==1)
		{
			if(t<x*2)printf("%lld\n",x);
			else printf("%lld\n",b[t][x]);
		}
		else
		{
			if(t<x*2)printf("%lld\n",x);
			else printf("%lld\n",a[t][x]);
		}
	}
	return 0;
}

2：事后诸葛亮

首先我们查询1和查询2的第一个判断是不用变的，$t<x*2$时，开头的数移动到$t/2$并不会让它向前移动，所以此时$x$这个位置上的数就是$x$

然后我们直接上题解教我的思路

查询1

看查询1的其余情况，第x头奶牛肯定是先从一个区间的末尾移动到开头，再移动到另一个区间的末尾。我们可以发现它移动到开头的步数是指数级规律增长的，约是$n*(n+1)/2$往上地增长，所以暴力跳$log(t)$并不会超时

我们就可以多用一个$ti$来记录现在位于末尾时的时间，那现在想移动到下一个结尾就需要动$[ti/2]+1$步，所以就找出$t$在哪个区间就能解决问题了

查询2

我们也能用跳结尾的方式来找答案，就设置一个函数，$solve(t)$表示时刻$t$时结尾的奶牛编号，那答案也就成了$solve(x+t+1)$，相当于你从结尾再跑回来，时间自然就是$x+t+1$

接着就开始分类讨论了：

1： 对于一个数$x$，它在$2x$的时候进行首次移动，移动$x$步后到达开头，再挪一步就到结尾去了，所以$solve(3x)=x$

因为前面的查询1中移动到结尾需要$[ti/2]+1$步，涉及到向下取整，又要对奇偶性进行分类

2： $ti$为奇数时，那移动到下一次结尾就要$ti+(ti-1)/2(即[ti/2])+1$次，我们再用$x$来表示现在的时间，那$ti=(2n-1)/3$，满足$n=2(mod3)$

3： 那$ti$为偶数也就推出来了，与$ti$为奇数时相似，$ti=(2n-2)/3$，满足$n=1(mod3)$，所以写出solve这个函数递归，最后AC即可......

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll solve(ll x)
{
	if(x%3==0)return x/3;
	if(x%3==1)return solve((2*x-2)/3);
	if(x%3==2)return solve((2*x-1)/3);
}
int main()
{
	int t;scanf("%d",&t);
	while(t--)
	{
		ll op,x,t;scanf("%lld%lld%lld",&op,&x,&t);
		if(op==1)
		{
			if(t<x*2)printf("%lld\n",x);
			else
			{
				ll ti=2*x-1;
				while(ti<=t)
				{
					if(t<=ti+x)
					{
						printf("%lld\n",x-(t-ti));
						break;
					}
					ti+=x+1;x=ti/2;
				}
			}
		}
		else
		{
			if(t<x*2)printf("%lld\n",x);
			else printf("%lld\n",solve(t+x+1));
		}
	}
	return 0;
}

$op=1$

考虑从时刻 $c$ 和位置 $c$ 正推。记当前时刻为 $t$，当前位置为 $p$，则初始时 $t=p=c$。根据题意，有

• 若 $p=0$，则下一时刻 $p'=\lfloor \frac{t+1}{2} \rfloor$；
• 若 $p>\lfloor \frac{t+1}{2} \rfloor$，则下一时刻 $p'=p$；
• 若 $0<p \le \frac{t+1}{2}$，则下一时刻 $p'=p-1$。

对于上面的第三种情况，显然 $p$ 会一直减 $1$ 直到变为 $0$。跳过这个过程即可。

$op=2$

考虑从时刻 $t$ 和位置 $x$ 反推。记当前时刻为 $t$，当前位置为 $p$，则初始时 $t$ 为输入的时刻，$p=x$。根据题意，有

• 若 $p>\lfloor\frac{t}{2}\rfloor$，则前一时刻 $p'=p$；
• 若 $p=\lfloor\frac{t}{2}\rfloor$，则前一时刻 $p'=0$；
• 若 $p<\lfloor\frac{t}{2}\rfloor$，则前一时刻 $p'=p+1$。

对于上面的第一种情况，显然 $p$ 永远不会再改变，直接终止循环即可。

对于上面的第三种情况，设 $p$ 接下来加 $1$ 的次数为 $k$，则根据题意有 $p+k=\lfloor\frac{t-k}{2}\rfloor$，解得 $k=\frac{t-2p}{3}$。故令 $p'=p+k$，$t'=t-k$ 即可。注意特判 $k=1$。

总复杂度 $O(\log t)$。

:::success[赛时代码]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int q;
	cin >> q;
	while (q--){
		int op;
		cin >> op;
		if (op == 1){
			ll c, t;
			cin >> c >> t;
			ll pos = c, cur = c;
			while (cur < t){
				if (pos == 0){
					cur++;
					pos = cur / 2;
				}
				else if (pos > (cur + 1) / 2){
					cur = pos * 2 - 1;
				}
				else{
					if (cur + pos <= t){
						cur += pos;
						pos = 0;
					}
					else{
						pos -= t - cur;
						cur = t;
					}
				}
			}
			cout << pos << endl;
		}
		else{
			ll x, t;
			cin >> x >> t;
			ll pos = x, cur = t;
			while (cur > 0){
				if (pos > cur / 2){
					cur = 0;
				}
				else if (pos == cur / 2){
					pos = 0;
					cur--;
				}
				else{
					ll k = max(1ll, (cur - 2 * pos) / 3);
					pos += k;
					cur -= k;
				}
			}
			cout << pos << endl;
		}
	}
	return 0;
}

:::

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int p[5005][5005];
ll ed(ll now){//分类讨论递归 
	if(now%3==0){
		return now/3;
	}
	if(now%3==1){
		return ed((2*now-2)/3);
	}
	if(now%3==2){
		return ed((2*now-1)/3);
	}
}
int main(){
	int t;
	cin>>t;
	while(t--){
		int op;
		cin>>op;
		ll x,tim;
		cin>>x>>tim;
		if(op==1){
			if(x*2>tim){//直接处理未参与变换的数（只有前t/2个数移动过） 
				cout<<x<<"\n";
				continue;
			}
//				t = 0 | 0
//				t = 1 | 0 1
//				t = 2 | 1 0 2
//				t = 3 | 0 1 2 3
//							^ 
//				t = 4 | 1 2 0 3 4
//						  ^
//				t = 5 | 2 0 1 3 4 5
//						^
//				t = 6 | 0 1 3 2 4 5 6
//							  ^
//				我们发现数字x的起始移动时间为 2*x-1 ，并在 t+t/2+1 时再次移动到结尾 

			//以t/2为结尾 
			ll ti=2*x-1;//当前数字开始移动的时间 
			while(ti<=tim){
				if(tim<=ti+x){
					cout<<x-(tim-ti)<<"\n";
					break;
				}
				//直接从当前数字在结尾时跳到下一次该数在结尾的情况 
				ti+=x+1;
				x=ti/2;
			}
		}
		else{
			if(x>tim/2){//直接处理未参与变换的数（只有前t/2个数移动过） 
				cout<<x<<"\n";
				continue;
			}
			cout<<ed(tim+x+1)<<"\n";
		}
	}
	return 0;
}