本文共 1597 字，大约阅读时间需要 5 分钟。
Trie树的应用题目.
在线建立一棵01 Trie树,然后按照要求用询问在上面跑,用单调栈维护答案即可.
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define ll long long#define db double #define up(i,j,n) for(int i=j;i<=n;i++)#define pii pair #define uint unsigned int#define FILE "dealing"int read(){ int x=0,f=1,ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f;}template bool cmax(T& a,T b){return a bool cmin(T& a,T b){return a>b?a=b,true:false;}const int maxn=4010000;int cnt=1,c[maxn][2],id,now,w[maxn],n,k,num=0,l,r,q[maxn],tail=0;vector t[maxn];inline void add(int x){ if(num==k)return; num++; if(!c[now][x])c[now][x]=++cnt; now=c[now][x]; if(num==k)t[now].push_back(id);}char ch;inline void change(int x){ up(i,1,8){ w[i]=x&1; x>>=1; }}inline void query(int x){ now=c[now][x]; for(int i=0;i t[now][i])tail--; if(t[now][i]>=l&&t[now][i]<=r){ while(q[tail]>t[now][i])tail--; q[++tail]=t[now][i]; } }}int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); n=read(); int a[5]; up(s,1,n){ scanf(" %c",&ch); if(ch=='A'){ now=1;num=0;id++; up(i,1,4)a[i]=read(); k=read(); up(i,1,4){ change(a[i]); for(int j=8;j>=1;j--) add(w[j]); } } if(ch=='Q'){ now=1;num=0;tail=0; up(i,1,4)a[i]=read(); l=read(),r=read(); up(i,1,4){ change(a[i]); for(int j=8;j>=1;j--) query(w[j]); } //cout<
转载于:https://www.cnblogs.com/chadinblog/p/6552251.html