lj的锁

lj的锁

这道题二分即可。。二分真是奥妙重重。

#include <cctype>

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long LL;

const LL maxn=2e5+5;

LL n, m;

struct node{

    LL data, id;

}ar[maxn];

LL wentto[maxn], where[maxn], x[maxn], maxl, minr;

bool operator <(const node a, const node b){

    return a.data<b.data;

}

inline LL getLL() {

    register char ch;

    register bool neg=false;

    while(!isdigit(ch=getchar())) if(ch=='-') neg=true;

    register LL x=ch^'0';

    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

    return neg?-x:x;

}

int main(){

    scanf("%lld%lld", &n, &m);

    for (LL i=0; i<n; ++i){

        ar[i].data=getLL();

        ar[i].id=i;

    }

    sort(ar, ar+n);

    for (LL i=0; i<n; ++i){

        wentto[ar[i].id]=i;

        where[i]=ar[i].id;

        x[i]=ar[i].data;

    }

    LL a, lpos, rpos, dis;

    LL l;

    for (LL i=0; i<m; ++i){

        a=getLL(), l=getLL();

        a=wentto[a-1];

        //lrpos存下标.lpos查大于等于它的，rpos小于等于它的

        maxl=0, minr=n;

        rpos=lower_bound(x, x+n, l+x[a])-x;

        if (rpos+1<minr) minr=rpos+1;

        if (x[rpos]!=l+x[a]) --rpos;

        lpos=lower_bound(x, x+n, x[a]-l)-x;

        while (lpos<rpos){

            l-=x[rpos]-x[a];

            a=rpos;

            lpos=lower_bound(x+maxl, x+minr, x[a]-l)-x;

            if (lpos>maxl) maxl=lpos;

            l-=x[a]-x[lpos];

            a=lpos;

            rpos=lower_bound(x+maxl, x+minr, l+x[a])-x;

            if (x[rpos]!=l+x[a]) --rpos;

            dis=x[rpos]-x[lpos];

            if (dis) l=l%(dis*2);

            rpos=lower_bound(x+maxl, x+minr, l+x[a])-x;

            if (x[rpos]!=l+x[a]) --rpos;

            if (rpos+1<minr) minr=rpos+1;

        }

        printf("%lld\n", where[a]+1);

    }

    return 0;

}