题目描述

Umi在暑假里学习线段树，线段树是一种树，根节点代表一段区间 \([l,r]\) ，每个长度大于1的区间会有两个子节点，分别代表\([l,floor(l+r)/2]\),\([floor(l+r)/2+1,r]\)

现在Umi想问你，如果根节点代表的区间是 \([1,n]\),那么区间长度第 \(k\) 长的区间是多长。

Umi要去参加夏日岛可梦，所以这个简单的问题就交给你了。

而且还是多组数据。

（所以猜一猜Umi的真名是啥呀）

输入格式

第一行一个正整数 \(T\)，表示数据的组数。

接下来 \(T\) 行，每行\(n,k\)

输出格式

共 \(T\) 行，表示答案。

样例数据

input

4
5 1
5 4
10 19
4396 443

output

5
2
1
17

数据规模与约定

50%的数据中， \(n\leq 10^{18},T\leq 10^4\)。

100%的数据中, \(n\leq 2^{62},T\leq 10^6\)

时间限制：\(2\text{s}\)

空间限制：\(512\text{MB}\)

Solution

可以证明线段树每一层内区间长度最大值与最小值相差最多为1，所以用这个结论乱搞一下就好了。

一个是直接log的模拟

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
#define lowbit(x) ((x)&(-(x)))
#define REP(i,a,n) for(register int i=(a);i<=(n);++i)
#define PER(i,a,n) for(register int i=(a);i>=(n);--i)
#define FEC(i,x) for(register int i=head[x];i;i=g[i].ne)
template<typename A>inline void read(A&a){a=0;char c=0;int f=1;while(c<'0'||c>'9')(c=getchar())=='-'?f=-1:0;while(c>='0'&&c<='9')a=(a<<3)+(a<<1)+c-'0',c=getchar();f==-1?a=-a:0;}
char buf[30];template<typename A>inline void write(A a){if(a<0)putchar('-'),a=-a;int top=0;if(!a)buf[top=1]='0';while(a)buf[++top]=a%10+'0',a/=10;while(top)putchar(buf[top--]);}
typedef long long ll;typedef unsigned long long ull;
template<typename A,typename B>inline bool SMAX(A&x,const B&y){return y>x?x=y,1:0;}
template<typename A,typename B>inline bool SMIN(A&x,const B&y){return y<x?x=y,1:0;}

ll T,n,k,mind,maxd,now,cnt,flag,lg,fst;

ll getlog(ll x){return x==1?0:getlog(x/2)+1;}

int main(){
//  freopen("segment.in","r",stdin);freopen("segment.out","w",stdout);
    read(T);
    while(T--){
        read(n),read(k);
        mind=maxd=n;now=1;cnt=0;flag=0;lg=getlog(n);if((1ll<<lg)==n)fst=(1ll<<lg);else fst=(1ll<<(lg+1));
        ll c1=0,c2=1;
        while(maxd){
            if(cnt+now>=k){
                if(cnt+c1>=k){write(maxd),putchar('\n'),flag=1;break;}
                else{write(mind),putchar('\n'),flag=1;break;}
            }
            ll maxd1=(1+maxd)/2,mind1=mind-(1+mind)/2,c11=0,c22=0;cnt+=now;now<<=1;
            if(maxd1*2==maxd)c11+=(c1<<1);else c11+=c1,c22+=c1;if(mind1&&mind1*2==mind)c22+=(c2<<1);else if(mind1)c11+=c2,c22+=c2;
            c1=c11,c2=c22;mind=mind1,maxd=maxd1;
        }
    }
    fclose(stdin);fclose(stdout);return 0;  
}

一个是直接O(1)的算法。可以直接用__log()这个函数计算所在层数\(t\)，则这一层有\(x=2^t\)个节点，那么长度少的点的长度就是$\lfloor \frac{n}{k} \rfloor \(，长的\)+1\(即可。那么长的区间的个数就是\)n-x \times \lfloor \frac{n}{k} \rfloor$。

下面引用了来自本校以为很强的大爷的代码。

#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T&w){char c,p=0;
    while(!isdigit(c=getchar()))if(c=='-')p=1;
    for(w=c&15;isdigit(c=getchar());w=w*10+(c&15));if(p)w=-w;
}
typedef long long ll;
ll n,k;
int main(){
    int T;read(T);
    while(T--){
        read(n),read(k);
        ll x=1ll<<__lg(k),u=n/x,d=n-u*x;
        printf("%lld\n",k-x<d?u+1:u);
    }
    return 0;
}

[校内NOIP2018模拟20181020] wph会做所有的线段树

原文：https://www.cnblogs.com/hankeke/p/20181020-segment.html