C2. Sheikh (Hard Version)(貪心&雙指針&bit)

C2. Sheikh (Hard Version)(貪心&雙指針&bit)

需要注意到 ，因為是不進位加法，是以 ，也就是說這個內插補點是非負的，會随區間長度增加非遞減。是以我們考慮最開始答案設為。因為要求長度最小，是以考慮删除部分字首和字尾使得答案不變的同時，長度變小。

#include<bits/stdc++.h>
using namespace std;
#define N 100002
int T,n,q,a[N],xorh[N],nx[N],pr[N];
int main(){
    scanf("%d",&T);
    while(T--){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i)scanf("%d",a+i),xorh[i]=xorh[i-1]^a[i];
    pr[0]=0;
    for(int i=1;i<=n;++i)pr[i]=a[i-1]?i-1:pr[i-1];
    nx[n]=n+1;
    for(int i=n-1;i>=1;--i)nx[i]=a[i+1]?i+1:nx[i+1];
    while(q--){
        int l,r,xr,ansl,ansr;scanf("%d%d",&l,&r);xr=xorh[r]^xorh[l-1];ansl=l;ansr=r;
        for(int ll=l;ll<=r;ll=nx[ll]){
        int rr=r;int tmp=xr;
        while(ll<=pr[rr]&&(xr|a[rr])==xr)xr^=a[rr],rr=pr[rr];
        if((xr|a[rr])==xr)rr=ll;
        if(ansr-ansl+1>rr-ll+1){
            ansr=rr;ansl=ll;
        }
        xr=tmp;if((xr|a[ll])!=xr)break;
        xr^=a[ll];
        }
        printf("%d %d\n",ansl,ansr);
    }
    }
    return 0;
}