题面

$n$个数，$q$次询问，询问$[i,j]$区间大于$k$的数的个数，输入时，输入$a,b,c$

  • i = a xor last_ans
  • j = b xor last_ans
  • k = c xor last_ans

一开始last_ans为$0$

思路：

主席树

其实是一道模板题

离散化后直接硬上模板

要注意的地方就是——

最后查询的时候$k$不要离散化，而是在查询函数中改变判断条件

Code：

#include<bits/stdc++.h>
#define N 30010
using namespace std;
struct node{
    int l,r,sum;
}T[N*30];
int a[N],b[N],root[N],t,n,m,res;
int x,y,k,ans;
int read(){
    int s=0;
    char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
    {
        s=(s<<1)+(s<<3)+c-'0';
        c=getchar();
    }
    return s;
}
void built(int l,int r,int &x,int y,int pos)
{
    T[++res]=T[y];T[res].sum++;x=res;
    if(l==r)
        return;
    int mid=(l+r)>>1;
    if(pos<=mid)
        built(l,mid,T[x].l,T[y].l,pos);
    else
        built(mid+1,r,T[x].r,T[y].r,pos);
}
void query(int l,int r,int x,int y)
{
    if(l==r)
    {
        if(b[l]<=k)
            ans+=T[y].sum-T[x].sum;
        return;
    }
    int mid=(l+r)>>1;
    int sum=T[T[y].l].sum-T[T[x].l].sum;
    if(k<=b[mid])//就是在这里加判断
        query(l,mid,T[x].l,T[y].l);
    else
        ans+=sum,query(mid+1,r,T[x].r,T[y].r);//ans加上左子树的大小，表示有多少个数比k小
}//但是实际上可以把条件改一改，然后加上右子树的大小，这里为了方便理解，就不改了
int main()
{
    int i;
    n=read();
    for(i=1;i<=n;i++)
        b[i]=a[i]=read();
    sort(b+1,b+1+n);t=unique(b+1,b+1+n)-b-1;
    for(i=1;i<=n;i++)
    {
        a[i]=lower_bound(b+1,b+1+t,a[i])-b;
        built(1,t,root[i],root[i-1],a[i]);
    }
    m=read();
    for(i=1;i<=m;i++)
    {
        x=read()^ans;y=read()^ans;k=read()^ans;ans=0;
        if(x<1)    x=1;
        if(y>n) y=n;
        if(x>y) { printf("%d\n",ans); continue; }
        query(1,t,root[x-1],root[y]);
        ans=y-x+1-ans;
        printf("%d\n",ans);
    }
    return 0;
}

devil.