[CF 555D] Case of a Top Secret

作法：

首先看要如何模擬，可以把繩子的動作分成兩種，第一種是當前繩子往下垂並且物體正在往右邊移，另一種則是當前繩子是往上的並且物體正在往左邊移。把輸入的座標排序就可以用 lower_bound / upper_bound 找出繩子接下來會繞誰轉，就可以模擬了。但直接做會TLE，首先觀察到我們可以先把繩子的長度縮減到比$a[n]-a[1]$還短，其中$a[1],...,a[n]$代表已排序後的釘子座標。接下來考慮模擬時要如何優化，設當前繩子繞著$a[i]$轉，並且是前面所述的第一種狀態，如果他是由第二種狀態轉移過來的，那麼顯然會滿足$a[i]-a[i-1]>L$，其中$L$為當前繩子長度。首先求出他之後會繞著$a[x]$轉，那麼他的長度就會變為$L-(a[x]-a[i])$。如果每次長度都減少了一半以上，那麼模擬的次數就會變成$O(logL)$，會是好的。但如果在這次$L$的長度沒有減少一半以上，那麼不難發現再繞完$x$旋轉的下一步會再去繞$i$旋轉，重複繞這兩個點旋轉直到$L$小於他們之間的距離為止，因此我們可以直接把$L$的長度縮減成$L\% (a[x]-a[i])$，並由他們的商來判斷此時是繞$i$轉還是繞$x$轉。由於此時$(a[x]-a[i])<\frac{L}{2}$，所以$L$也會至少砍半，而對於第二種狀態作法也幾乎一樣，因此這樣就得到了單次詢問$O(lognlogL)$的算法了。

code :

#include<bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
#define LL long long
using namespace std;
const int maxn=200000+10 ;
 
pii p[maxn] ;
int a[maxn],idx[maxn],mp[maxn] ;
main()
{
    int n,Q ; scanf("%d%d",&n,&Q) ;
    for(int i=1;i<=n;i++) scanf("%d",&p[i].F) , p[i].S=i ;
    sort(p+1,p+n+1) ;
    for(int i=1;i<=n;i++) a[i]=p[i].F , idx[i]=p[i].S , mp[p[i].S]=i ;
    while(Q--)
    {
        int x,l,type=1 ; scanf("%d%d",&x,&l) ;
        if(n==1){printf("1\n") ; continue ;}
        x=mp[x] ;
 
        int id=upper_bound(a+1,a+n+1,a[x]+l)-a-1 ;
        l-=a[id]-a[x] ;
        x=id ; type=2 ;
 
        if(l>=a[n]-a[1])
        {
            int q=l/(a[n]-a[1]) ;
            if(q%2) x=1 , type=1 ;
            else x=n , type=2 ;
            l-=q*(a[n]-a[1]) ;
        }
        while(l)
        {
            if(type==1)
            {
                id=upper_bound(a+1,a+n+1,a[x]+l)-a-1 ;
                if(id==x || a[id]==a[x]+l){x=id ; break ;}
                if(a[id]-a[x]>=l/2)
                {
                    l-=(a[id]-a[x]) ;
                    x=id ; type=2 ;
                    continue ;
                }
                int tmp=a[id]-a[x] , q=l/tmp ;
                if(q%2) x=id , type=2 , l-=q*tmp ;
                else l-=q*tmp ;
            }
            else
            {
                id=lower_bound(a+1,a+n+1,a[x]-l)-a ;
                if(id==x || a[id]==a[x]-l){x=id ; break ;}
                if(a[x]-a[id]>=l/2)
                {
                    l-=(a[x]-a[id]) ;
                    x=id ; type=1 ;
                    continue ;
                }
                int tmp=(a[x]-a[id]) , q=l/tmp ;
                if(q%2) x=id , type=1 , l-=q*tmp ;
                else l-=q*tmp ;
            }
        }
        printf("%d\n",idx[x]) ;
    }
}