hihocoder 1342 二分

#include<bits/stdc++.h>
#define Mem(a,b) memset(a,b,sizeof(a))
#define eps 1e-6
#define ll long long
#define l(x) (x<<1)
#define r(x) (x>>1)
#define lson root<<1
#define rson root<<1|1
#define Mid int mid=(l+r)>>1
#define FREI freopen("in.txt","r",stdin)
#define FREO freopen("out.txt","w",stdout)
#define N 500100
#define Maxn 1010
#define inf 0x3f3f3f3f
using namespace std;
int y[2000000]= {0},n,m,x[2000000]= {0};
int marky[2000000],markx[2000000];
void init() {
    x[1]=0;
    int flag[30]= {0},p=0;
    int maxn=0;
    int cnt=1,num=1<<(n-1),tmp=1,pre=-1,now=0;
    while(cnt<num) {
        cnt*=2;
        flag[++p]=now+pre-1;
        now=flag[p];
        pre=now;
        maxn=-now;
    }
    cnt=1;
    p--;
    while(cnt<num) {
        cnt*=2;
        for(int i=0; i<cnt; i++) {
            x[++tmp]=flag[p]+maxn;
        }
        p--;
    }
    for(int i=1; i<=tmp; i++) {
        (i&1)?y[i]=y[i/2]+(x[i]-x[i/2]):y[i]=y[i/2]-(x[i]-x[i/2]);
    }
    for(int i=1; i<=tmp; i++) markx[i]=x[i],marky[i]=y[i];

}
int Y(int mid,int l,int r){
    if(mid==l) return -inf;
    if(mid==r) return inf;
    return y[mid];
}
void work(int tmp,int lx,int ly,int rx,int ry) {
    int ans=0;
    x[0]=-inf,x[tmp+1]=inf;
    int l=0,r=tmp+1;
    int ansxl,ansxr,ansyup,ansydown;
    while(r>l+1) {
        int mid=(l+r)>>1;
        if(x[mid]>=lx) r=mid;
        else l=mid;
    }
    ansxl=r;
    l=0,r=tmp+1;
    while(r>l+1) {
        int mid=(l+r)>>1;
        if(x[mid]>rx) r=mid;
        else l=mid;
    }
    ansxr=l;
    queue<int>q;
    int cnt1=ansxl;
    while(cnt1<=ansxr) {
        q.push(cnt1);
        cnt1<<=1;
    }
    while(!q.empty()) {
        int id=q.front();
        q.pop();
        l=id-1,r=id<<1;
        while(r>l+1) {
            int mid=(l+r)>>1;
            if(Y(mid,id-1,id<<1)>=ly) r=mid;
            else l=mid;
        }
        ansyup=r;
        l=id-1,r=id<<1;
        while(r>l+1) {
            int mid=(l+r)>>1;
            if(Y(mid,id-1,id<<1)>ry) r=mid;
            else l=mid;
        }
        ansydown=l;
        ans+=ansydown-ansyup+1;
    }
    cout<<ans<<endl;
}
void solve(int tmp,int lx,int ly,int rx,int ry) {
    int cnt=0;
    for(int i=1; i<=tmp; i++) {
        if(x[i]>=lx&&x[i]<=rx&&y[i]<=ry&&y[i]>=ly) cnt++;
    }
    cout<<cnt<<endl;
}
int main() {
    //FREI;
    //FREO;
    while(scanf("%d%d",&n,&m)!=EOF) {
        init();
        while(m--) {
            int lx,ly,rx,ry;
            scanf("%d%d%d%d",&lx,&ly,&rx,&ry);
            solve((1<<n)-1,lx,ly,rx,ry);
            //work((1<<n)-1,lx,ly,rx,ry);
            //cout<<endl;
        }
    }
}
           

暴力也可以過