【做題記錄】貪心--提高組
A. Monotone Subsequence
有點 Ad-hoc。
第 \(i\) 次查詢，直接詢問當前未被刪去的所有點。如果回答 \(\ge n+1\)，那么直接輸出；否則將回答的這些點標一個級別 \(i\)。最后一次詢問之后還剩下的標為 \(n+1\)。根據鴿籠原理，如果最后沒剩下，那么中間必然有一次回答 \(\ge n+1\)。
可以發現，對于每個級別為 \(i\) 的位置，在其之前必然有一個級別為 \(i-1\) 的位置 \(j\)，且 \(p_j\) 是必然比 \(p_i\) 大的。于是我們連邊，跑一個 DAG 上 DP 即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=1e4+5;
int T,n,a[maxn],f[maxn],g[maxn];
set<int> st;
vector<int> e[maxn];
queue<int> q;
il void print(int u){
if(!u){
printf("! ");
return ;
}
print(g[u]);
printf("%d ",u);
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
st.clear();
for(int i=1;i<=n*n+1;i++){
st.insert(i),e[i].clear();
}
for(int i=1;i<=n;i++){
printf("? %d ",(int)st.size());
for(int j:st){
printf("%d ",j);
}
puts(""),fflush(stdout);
int c;
scanf("%d",&c);
if(c>=n+1){
printf("! ");
for(int j=1,x;j<=c;j++){
scanf("%d",&x);
if(j<=n+1){
printf("%d ",x);
}
}
puts(""),fflush(stdout);
goto togo;
}
for(int j=1,x;j<=c;j++){
scanf("%d",&x);
a[x]=i,st.erase(x);
}
}
for(int i:st){
a[i]=n+1;
}
for(int i=1;i<=n*n+1;i++){
if(a[i]==1){
q.push(i),f[i]=1,g[i]=0;
}else{
for(int j=i-1;j;j--){
if(a[j]==a[i]-1){
e[j].pb(i);
break;
}
}
}
}
while(q.size()){
int u=q.front();
q.pop();
for(int v:e[u]){
q.push(v);
f[v]=f[u]+1,g[v]=u;
}
}
for(int i=1;i<=n*n+1;i++){
if(f[i]==n+1){
print(i);
puts(""),fflush(stdout);
break;
}
}
togo:;
}
return 0;
}
}
int main(){return asbt::main();}
B. Yet Another MEX Problem
重要結論：\(\sum[a_i>\operatorname{mex}(a)]=\max\limits_{x\notin a}\sum[a_i>x]\)。證明顯然。
于是我們考慮在移動 \(r\) 時對每個 \(x\) 維護右面那個式子。設最后出現 \(x\) 的位置為 \(p_x\)，我們維護的就是 \([p_x+1,r]\) 中大于 \(x\) 的數的個數，這是方便用線段樹維護的。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
const int maxn=3e5+5;
int T,n,a[maxn],tr[maxn<<2],tag[maxn<<2];
il void pushup(int id){
tr[id]=max(tr[lid],tr[rid]);
}
il void pushtag(int id,int v){
tr[id]+=v,tag[id]+=v;
}
il void pushdown(int id){
if(tag[id]){
pushtag(lid,tag[id]);
pushtag(rid,tag[id]);
tag[id]=0;
}
}
il void build(int id,int l,int r){
tr[id]=tag[id]=0;
if(l==r){
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
}
il void upd(int id,int l,int r,int p){
if(l==r){
tr[id]=0;
return ;
}
pushdown(id);
int mid=(l+r)>>1;
if(p<=mid){
upd(lid,l,mid,p);
}else{
pushtag(lid,1);
upd(rid,mid+1,r,p);
}
pushup(id);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n;
build(1,0,n);
for(int i=1;i<=n;i++){
cin>>a[i];
upd(1,0,n,a[i]);
cout<<tr[1]<<' ';
}
cout<<'\n';
}
return 0;
}
}
int main(){return asbt::main();}
C. Make Good
Ad-hoc。
先把 \(n\) 為奇數判掉。然后開始對腦電波尋找性質：
首先，所有的 (( 和 )) 都是可以隨意移動的。比如 ((：
(()\(\to\))))\(\to\))(()((\(\to\))))\(\to\)(()(((\(\to\)(((（沒變但等于是動了）
所以我們先用棧把所有的 (( 和 )) 找出來，設有 \(cnt\) 個。剩下的字符串有以下三種可能：
()()()...())()()()...()(- 空串
那么如果 \(cnt\) 為奇數則必然無解，如果為偶數那么可以在這個串左右各加 \(\frac{cnt}{2}\) 個 (( 和 ))。當然如果 \(cnt=0\) 那么第二種情況就不成立。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=2e5+5;
int T,n,top,cnt;
char stk[maxn];
string s;
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n>>s;
if(n&1){
cout<<-1<<'\n';
continue;
}
cnt=top=0;
for(int i=0;i<n;i++){
if(!top){
stk[++top]=s[i];
}else if(stk[top]==s[i]){
cnt++,top--;
}else{
stk[++top]=s[i];
}
}
if(cnt&1){
cout<<-1<<'\n';
}else if(!cnt&&stk[1]==')'){
cout<<-1<<'\n';
}else{
for(int i=1;i<=cnt>>1;i++){
cout<<"((";
}
for(int i=1;i<=top;i++){
cout<<stk[i];
}
for(int i=1;i<=cnt>>1;i++){
cout<<"))";
}
cout<<'\n';
}
}
return 0;
}
}
int main(){return asbt::main();}
D. Long Journey
設 \(len=\operatorname{lcm}(a)\)。顯然 \(len\le2520\)。稱走 \(len\) 格為走了一個周期。
考慮整個過程，就是走 \(\lfloor\frac{m}{len}\rfloor\) 個周期，然后再走 \(m\bmod len\) 步。考慮壓縮前面那些周期的過程。枚舉進入這個周期前的時刻模 \(n\) 的值 \(i\)，我們希望求出此狀態下走一個周期的用時。模擬一遍這個周期的過程即可。
模擬的過程是一個貪心：如果下一格在下一秒是陷阱，那就等一秒，否則就走過去。如果在一格等待了 \(n\) 秒還是沒走，那么無解。貪心的正確性在于不會出現兩個相鄰的格子同時是陷阱的情況。在每個格子都最多等待 \(n\) 次，所以單次模擬的時間復雜度是 \(O(n\times len)\) 的。這個預處理的總時間是 \(O(n^2\times len)\)。
于是我們就可以快速計算了。走周期這個過程顯然可合并，于是我們對走周期這個過程做快速冪。合并兩個過程是 \(O(n)\) 的，這一部分時間復雜度 \(O(n\log\lfloor\frac{m}{len}\rfloor)\)。然后再類似上面的方式模擬最后一小段即可。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define gcd __gcd
using namespace std;
namespace asbt{
const int inf=1e18;
int T,n,m,a[12],b[12];
struct juz{
int a[12];
il int&operator[](int x){
return a[x];
}
il juz operator*(juz b)const{
juz c;
for(int i=0;i<n;i++){
c[i]=min(a[i]+b[(i+a[i])%n],inf);
}
return c;
}
}bas;
il int calc(int t,int len){
int p=0,res=0;
while(p<len){
p++;
int cnt=0;
t=t%n+1,res++;
while(p%a[t]==b[t]){
if(cnt==n){
return inf;
}
t=t%n+1,cnt++,res++;
}
}
return res;
}
il juz qpow(juz x,int y){
juz res;
for(int i=0;i<n;i++){
res[i]=0;
}
while(y){
if(y&1){
res=res*x;
}
x=x*x,y>>=1;
}
return res;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n>>m;
int len=1;
for(int i=1;i<=n;i++){
cin>>a[i];
len=len/gcd(len,a[i])*a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
if(m<len){
int ans=calc(0,m);
cout<<(ans>=inf?-1:ans)<<'\n';
continue;
}
for(int i=0;i<n;i++){
bas[i]=calc(i,len);
// cout<<bas[i]<<' ';
}
// cout<<'\n';
int ans=qpow(bas,m/len)[0];
ans=ans+calc(ans%n,m%len);
cout<<(ans>=inf?-1:ans)<<'\n';
}
return 0;
}
}
signed main(){return asbt::main();}
E. I Yearned For The Mines
考慮如果是一條鏈，我們從一頭查到另一頭就行了。否則就必須短邊。也就是說我們要在 \(\lfloor\frac{n}{4}\rfloor\) 次內將樹斷成若干條鏈。這是必然可行的，因為任意三個點就是鏈，所以最壞情況每四個點就要斷一個點。鏈分為一直往上和先上后下（跨過 lca）兩種，于是我們從下往上貪心即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=2e5+5;
int T,n,fa[maxn],son[maxn],tot;
bool f[maxn],vis[maxn];
vector<int> e[maxn];
struct{
int d1,d2,dd;
}a[maxn];
il void dfs(int u,int fth){
fa[u]=fth;
int cnt=0;
for(int v:e[u]){
if(v==fth){
continue;
}
dfs(v,u);
if(!f[v]){
cnt++;
}
}
if(f[u]){
for(int v:e[u]){
if(v!=fth&&!vis[v]&&!f[v]){
a[++tot]={son[v],son[v],v};
}
}
return ;
}
if(cnt==0){
son[u]=u;
return ;
}else if(cnt==1){
for(int v:e[u]){
if(v!=fth&&!f[v]){
son[u]=son[v];
return ;
}
}
}else if(cnt==2){
if(fth&&!f[fth]){
f[fth]=1;
}
a[++tot].dd=u,vis[u]=1;
for(int v:e[u]){
if(v==fth||f[v]){
continue;
}
if(a[tot].d1){
a[tot].d2=son[v];
}else{
a[tot].d1=son[v];
}
}
}else{
f[u]=1;
for(int v:e[u]){
if(v!=fth&&!f[v]){
a[++tot]={son[v],son[v],v};
}
}
}
// if(tot>n){
// exit(114514);
// }
}
il void print(int u,int v){
// if(v<1||v>n){
// exit(v?v:998244353);
// }
// if(u<1||u>n){
// exit(514);
// }
if(u==v){
return ;
}
print(fa[u],v);
cout<<1<<' '<<u<<'\n';
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n;
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
e[u].pb(v),e[v].pb(u);
}
dfs(1,0);
if(!vis[1]&&!f[1]){
a[++tot]={son[1],son[1],1};
}
int cnt=0;
for(int i=1;i<=n;i++){
if(f[i]){
cnt++;
}
}
cout<<n+cnt<<'\n';
for(int i=1;i<=n;i++){
if(f[i]){
cout<<1<<' '<<i<<'\n'<<2<<' '<<i<<'\n';
}
}
for(int i=1;i<=tot;i++){
if(a[i].d1==a[i].d2){
int u=a[i].d1;
cout<<1<<' '<<u<<'\n';
if(u==a[i].dd){
continue;
}
do{
u=fa[u];
cout<<1<<' '<<u<<'\n';
}while(u!=a[i].dd);
}else{
int u=a[i].d1;
cout<<1<<' '<<u<<'\n';
do{
u=fa[u];
cout<<1<<' '<<u<<'\n';
}while(u!=a[i].dd);
print(a[i].d2,a[i].dd);
}
}
for(int i=1;i<=n;i++){
fa[i]=son[i]=f[i]=vis[i]=0;
e[i].clear();
}
for(int i=1;i<=tot;i++){
a[i]={0,0,0};
}
tot=0;
}
return 0;
}
}
int main(){return asbt::main();}
//
F. Traffic Lights
猜結論題，證明 AAAAAd-hoooooc。
結論：最短的總時間不會超過 \(3n\)。
Proof：對于一條路徑，總的時間不會超過 \(\sum deg\)，因為最多在一個點等一圈后走出去。設 \(\sum deg=d\)。考慮從 \(1\) 到 \(n\) 的最短路，首先在路徑上的不相鄰的點之間不會有邊；其次，對于不在路徑上的點，因為無重邊，所以不可能鏈接路徑上的 \(4\) 個及以上的點。那么設路徑上的點數為 \(k\)，則 \(d=3(n-k)+2k=3n-k<3n\)。
于是可以 DP，設 \(f_{i,j}\) 表示 \(i\) 時刻在 \(j\) 的最小等待次數即可。需要滾動數組。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=5e3+5,inf=1e9;
int T,n,m,f[2][maxn],d[maxn];
vector<int> e[maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
e[u].pb(v),e[v].pb(u);
d[u]++,d[v]++;
}
for(int i=1;i<=n;i++){
f[0][i]=inf;
}
f[0][1]=0;
for(int i=0,p=0,q=1;i<n*3;i++,p^=1,q^=1){
for(int i=1;i<=n;i++){
f[q][i]=inf;
}
for(int j=1;j<=n;j++){
f[q][j]=min(f[q][j],f[p][j]+1);
int k=e[j][i%d[j]];
f[q][k]=min(f[q][k],f[p][j]);
}
if(f[q][n]<inf){
cout<<i+1<<' '<<f[q][n]<<'\n';
break;
}
}
for(int i=1;i<=n;i++){
d[i]=0,e[i].clear();
}
}
return 0;
}
}
int main(){return asbt::main();}
G. Puzzle
對于一個確定的矩形，設長、寬為 \(x,y\)，在其變為一個 L 形圖案的過程中它的周長是不變的。而整個過程中的面積范圍是確定的，即為 \(x+y-1\) 到 \(x\times y\)。
于是考慮枚舉所有可能的周長 \(n\)。對于確定的周長 \(n\)，L 形圖案的面積為固定的 \(\frac{n}{2}-1\)。我們希望能覆蓋盡可能大的面積范圍，于是取 \(x=\lfloor\frac{n}{4}\rfloor,y=\lceil\frac{n}{4}\rceil\)，考察此時的面積范圍是否覆蓋了我們需要的面積即可。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define gcd __gcd
using namespace std;
namespace asbt{
int T,n,m;
il bool solve(int n,int m){
if(n&1){
return 0;
}
int x=n/4,y=n/2-x;
if(m<x+y-1||m>x*y){
return 0;
}
cout<<m<<'\n';
for(int i=0;i<x;i++){
cout<<0<<' '<<i<<'\n';
}
for(int i=1;i<y;i++){
cout<<i<<' '<<0<<'\n';
}
if(y==1){
return 1;
}
m-=x+y-1;
for(int i=1;i<=m/(y-1);i++){
for(int j=1;j<y;j++){
cout<<j<<' '<<i<<'\n';
}
}
for(int i=1;i<=m%(y-1);i++){
cout<<i<<' '<<m/(y-1)+1<<'\n';
}
return 1;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n>>m;
int gg=gcd(n,m);
n/=gg,m/=gg;
for(int i=1;m*i<=5e4;i++){
if(solve(n*i,m*i)){
goto togo;
}
}
cout<<-1<<'\n';
togo:;
}
return 0;
}
}
signed main(){return asbt::main();}
H. Cycling (Easy Version)
如果 \(p\) 是 \(1\sim p\) 中最小的且第一次出現，那么我們可以一路帶著 \(p\) 超，顯然一定是最優的。于是可以 DP：設 \(dp_i\) 表示到 \(i\) 后面的最小花費。記 \(p\) 是 \(i\) 后面第一個最小值的位置，于是有轉移：
答案即為 \(dp_0\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=5e3+5,inf=1e18;
int T,n,a[maxn],dp[maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dp[n]=0;
for(int i=n-1;~i;i--){
int p=i+1;
for(int j=i+1;j<=n;j++){
if(a[j]<a[p]){
p=j;
}
}
dp[i]=inf;
for(int j=p;j<=n;j++){
dp[i]=min(dp[i],dp[j]+2*(j-p)+(p-i-1)+a[p]*(j-i));
}
}
cout<<dp[0]<<'\n';
}
return 0;
}
}
signed main(){return asbt::main();}
I. 23 Kingdom
最優的 \(b\) 序列一定是前面一些位置填了 \(1\sim k\)，后面一些位置填了 \(1\sim k\)，中間亂填的一個狀態。于是我們只要從前面和后面分別貪心地選擇一些位置就好了。不妨只考慮前面那些位置，設它們組成的集合為 \(S\)，其合法的充要條件為 \(\forall i\in[1,n],\sum_{x\in S}[a_x\le i]\le i\)，因為若不滿足則根據鴿巢原理必然有相同的 \(b_x\)，若滿足則顯然可以構造。于是用線段樹維護 \(i-\sum_{x\in S}[a_x\le i]\) 的最小值即可。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
const int maxn=2e5+5;
int T,n,a[maxn],tr[maxn<<2],tag[maxn<<2];
int b[maxn],c[maxn];
il void pushup(int id){
tr[id]=min(tr[lid],tr[rid]);
}
il void pushtag(int id,int v){
tr[id]+=v,tag[id]+=v;
}
il void pushdown(int id){
if(tag[id]){
pushtag(lid,tag[id]);
pushtag(rid,tag[id]);
tag[id]=0;
}
}
il void build(int id,int l,int r){
tag[id]=0;
if(l==r){
tr[id]=l;
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
pushup(id);
}
il void add(int id,int L,int R,int l,int r,int v){
if(L>=l&&R<=r){
pushtag(id,v);
return ;
}
pushdown(id);
int mid=(L+R)>>1;
if(l<=mid){
add(lid,L,mid,l,r,v);
}
if(r>mid){
add(rid,mid+1,R,l,r,v);
}
pushup(id);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
int cb=0;
for(int i=n;i;i--){
add(1,1,n,a[i],n,-1);
if(tr[1]>=0){
b[++cb]=i;
}else{
add(1,1,n,a[i],n,1);
}
}
build(1,1,n);
int cc=0;
for(int i=1;i<=n;i++){
add(1,1,n,a[i],n,-1);
if(tr[1]>=0){
c[++cc]=i;
}else{
add(1,1,n,a[i],n,1);
}
}
int ans=0;
for(int i=1;i<=min(cb,cc)&&c[i]<b[i];i++){
ans+=b[i]-c[i];
}
cout<<ans<<'\n';
}
return 0;
}
}
signed main(){return asbt::main();}
J. Wonderful Teddy Bears
所有操作的過程就是將逆序對數減少到 \(0\) 的過程。考慮能使逆序對減少最多的操作，即為 \(\texttt{PBB}\to\texttt{BBP}\) 或 \(\texttt{PBB}\to\texttt{BBP}\)，能使逆序對減少兩個。但它的操作次數是不好算的，考慮盡可能地進行了這個操作之后序列的形態，即為 \(\texttt{BBBBBB}\dots\texttt{BPBPBP}\dots\texttt{BPBP}\dots\texttt{PPPPP}\)，于是我們還需要進行一部分 \(\texttt{BPB}\to\texttt{BBP}\)、\(\texttt{PBP}\to\texttt{BPP}\) 的操作，會使逆序對減一。考慮這類操作的數量，發現 \(\texttt{PBB}\to\texttt{BBP}\) 操作不會改變偶數位上 \(\texttt{B}\) 的數量，而 \(\texttt{BPB}\to\texttt{BBP}\) 會改變。設總共有 \(a\) 個 \(\texttt{B}\)，偶數位上有 \(b\) 個 \(\texttt{B}\)，于是第二類操作就一共有 \(|\lfloor\frac{a}{2}\rfloor-b|\) 次，于是第一類操作就有 \(\frac{tot-|\lfloor\frac{a}{2}\rfloor-b|}{2}\) 次，其中 \(tot\) 是逆序對的數量。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
int T,n;
string s;
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n>>s;
ll cnt=0,tot=0,ctt=0,cev=0;
for(int i=0;i<n;i++){
if(s[i]=='B'){
tot+=cnt,ctt++;
if(i&1){
cev++;
}
}else{
cnt++;
}
}
cout<<(tot-abs(ctt/2-cev))/2+abs(ctt/2-cev)<<'\n';
}
return 0;
}
}
int main(){return asbt::main();}
K. Zebra-like Numbers
首先考慮如何求一個數的斑馬值。考慮貪心，即不停地選擇最大的斑馬數減去。考慮正確性。
假設 \(x\) 是最小的不能使用上面那個貪心求出斑馬值的數，記小于它的最大的斑馬數為 \(z_i\)，故 \(x\) 的分解中必然沒有 \(z_i\) 并且有 \(z_{i-1}\)。由于 \(z_i=4z_{i-1}+1\)，所以 \(x\) 中含有 \(4\) 個 \(z_{i-1}\)，和至少一個其它斑馬數。如果第 \(5\) 個數是 \(1\)，那么我們就能湊出一個 \(z_i\)，否則就能湊出一個 \(z_i\) 和另外四個更小的數，這樣得到的斑馬值是不劣的。故 \(x\) 不存在。
那么我們考慮用一種奇怪的進制表示 \(x=\sum t_iz_i\)，于是有 \(t_i\le4\)，并且如果 \(t_i=4\) 那么 \(\forall j<i,t_j=0\)。數位 DP 即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
int T,dig[39];
ll l,r,k,bas[39],f[39][97][2][2];
il ll dfs(int pos,int sum,bool limit,bool four){
// cout<<pos<<' '<<sum<<' '<<limit<<' '<<four<<'\n';
if(sum>k){
return 0;
}
if(!pos){
return sum==k;
}
if(~f[pos][sum][limit][four]){
return f[pos][sum][limit][four];
}
ll &res=f[pos][sum][limit][four];
if(four){
return res=dfs(pos-1,sum,limit,four);
}
res=0;
// cout<<(limit?dig[pos]:4)<<'\n';
for(int i=0;i<=(limit?dig[pos]:4);i++){
res+=dfs(pos-1,sum+i,limit&&i==dig[pos],i==4);
}
return res;
}
il ll solve(ll x){
// cout<<x<<":\n";
memset(f,-1,sizeof(f));
for(int i=30;i;i--){
dig[i]=x/bas[i];
x%=bas[i];
}
// for(int i=1;i<=30;i++){
// cout<<dig[i]<<' ';
// }
// cout<<'\n';
return dfs(30,0,1,0);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
bas[1]=1;
for(int i=2;i<=30;i++){
bas[i]=bas[i-1]<<2|1;
}
cin>>T;
// ofstream cout("my.out");
while(T--){
cin>>l>>r>>k;
solve(r),solve(l-1);
cout<<solve(r)-solve(l-1)<<'\n';
}
return 0;
}
}
int main(){return asbt::main();}
浙公網安備 33010602011771號