- 独立做出了银牌题~
- 线段树划分区间其实无须左闭右开
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int tot,id;
vector<int>a[1005],c[1005];
int t[1005][2];
void add(int u,int v,int w)
{
a[u].push_back(v);
c[u].push_back(w);
}
void ask(int l,int r,int u,int v,int dep)
{
if(u<=l&&v>=r-1)
{
bool f=false;
int cur=1;
for(int i=19;i>dep;i--)
{
if((l>>i)&1)
{
f=true;
}
if(f==true)
{
if(!t[cur][(l>>i)&1])
{
add(cur,++tot,(l>>i)&1);
t[cur][(l>>i)&1]=tot;
}
cur=t[cur][(l>>i)&1];
}
}
add(cur,21-dep,(l>>dep)&1);
id=min(id,21-dep);
return;
}
int mid=(l+r)>>1;
if(u<mid)
{
ask(l,mid,u,v,dep-1);
}
if(v>=mid)
{
ask(mid,r,u,v,dep-1);
}
}
int main()
{
int l,r;
cin>>l>>r;
for(int i=2;i<21;i++)
{
add(i,i+1,0);
add(i,i+1,1);
}
tot=21;
id=21;
ask(0,(1<<20),l,r,20);
cout<<tot-(id-2)<<endl;
for(int i=1;i<=tot;i++)
{
if(i!=1&&i<id)
{
continue;
}
cout<<a[i].size();
for(int j=0;j<a[i].size();j++)
{
cout<<' '<<a[i][j]-(id-2)<<' '<<c[i][j];
}
cout<<endl;
}
return 0;
}