对于每一条询问，我们可以通过一个数组维护第一次匹配长度为i时的插入时间来计算在[l,r]中改变了多少遍

由于现在长度已经单调，选择会发生变化当且仅当时间也单调，

于是我们可以通过单调栈计算[1,x]中改变了多少遍

ans=solve(r)-solve(l-1)

对于多个询问，我们可以把询问插入trie树中，实现多个询问共用一个维护数组

1 #include
      
        2 using namespace std; 3 typedef long long ll; 4 #define maxn 1000005 5 #define maxnd 15000000 6 struct node{ ll x; int l,r; }A[maxn],Q[maxn]; 7 int n,aa,qq; 8 int trie[maxnd][2],nd,mark[maxnd],sta[40]; 9 int read(){10     int tmp=0; char ch=0;11     while(ch<'0'||ch>'9')ch=getchar();12     while(ch>='0'&&ch<='9')tmp=tmp*10+ch-'0',ch=getchar();13     return tmp;14 }15 void insert(ll x){16     int p=0;17     for(int i=32;i;i--){18         int t=x>>(i-1)&1;19         if(!trie[p][t])trie[p][t]=++nd;20         p=trie[p][t];21     }22 }23 void init(){24     n=read();25     char op[3];26     for(int i=1;i<=n;i++){27         scanf("%s",op);28         if(op[0]=='A'){29             aa++;30             for(int j=0;j<4;j++)31                 A[aa].x=(A[aa].x<<8)|read();32             A[aa].l=read();33         }34         else{35             qq++;36             for(int j=0;j<4;j++)37                 Q[qq].x=(Q[qq].x<<8)|read();38             Q[qq].l=read(),Q[qq].r=read();39             insert(Q[qq].x);40         }41     }42 }43 void getmark(int pos){44     int p=0;45     for(int i=32;i>32-A[pos].l;i--){46         int t=A[pos].x>>(i-1)&1;47         if(!trie[p][t])return;48         p=trie[p][t];49     }50     if(!mark[p])mark[p]=pos;51 }52 int getans(ll x,int rng){53     int p=0,top=0;54     for(int i=32;i;i--){55         int t=x>>(i-1)&1;56         p=trie[p][t];57         if(mark[p]&&mark[p]<=rng){58             while(top&&mark[p]