题面:
给定一个序列,有多次询问,每次查询区间里小于等于某个数的元素的个数
即对于询问 (l,r,x),你需要输出 \sum_{i=l}^{r}[a_i \le x]∑ i=lr [a i ≤x] 的值
其中 [exp] 是一个函数,它返回 1 当且仅当 exp 成立,其中 exp 表示某个表达式
题解:
离线后树状数组OR主席树
我这里使用的是主席树的方法::
相当于预处理出,每个点的权值线段树。那么每次查询的时候直接查询r时刻前缀小于x的数量减去l-1时刻前缀小于x的数量就可以啦!
代码:
#include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define fi first #define se second #define mp make_pair #define pb push_back using namespace std; typedef long long ll; typedef vector<int> VI; const ll inf = 0x3f3f3f3f3f3f3f3f; const int mod = 998244353; const int maxn = 1e5 + 6; ll qpow(ll x,ll y){ll ans=1;x%=mod; while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;} struct node{ int l,r,sum; }T[maxn*40]; int cnt=0; void update(int l,int r,int &x,int y,int z){ T[++cnt]=T[y];x=cnt;T[cnt].sum++; if(l==r) return ; int mid=l+r>>1; if(z<=mid) update(l,mid,T[x].l,T[y].l,z); else update(mid+1,r,T[x].r,T[y].r,z); } int ask(int l,int r,int x,int ql,int qr){ if(ql<=l&&r<=qr){return T[x].sum;} int mid=l+r>>1,ans=0; if(ql<=mid) ans+=ask(l,mid,T[x].l,ql,qr); if(qr>mid) ans+=ask(mid+1,r,T[x].r,ql,qr); return ans; } int n,m,l,r,x,a[maxn],root[maxn]; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=1;i<=n;i++){ update(1,1e5,root[i],root[i-1],a[i]); } while(m--){ scanf("%d%d%d",&l,&r,&x); printf("%d\n",ask(1,1e5,root[r],1,x)-ask(1,1e5,root[l-1],1,x)); } }