题解
莫队+值域分块
把询问储存起来,然后套莫队的板子
然后每次加和减这里如果采取线段树/树状数组进行操作会T
可以改用值域分块
代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; struct Node { int l,r; int x; int id; }q[N]; int n,m,a[N]; int block,block2; int res[N]; int *cnt; int cnt2[N]; bool cmp(const Node &a,const Node &b) { return (a.l/block)^(b.l/block)?a.l<b.l:(((b.l/block)&1)?a.r<b.r:a.r>b.r); } inline void add(int x) { cnt[a[x]/block2]++; cnt2[a[x]]++; } inline void del(int x) { cnt[a[x]/block2]--; cnt2[a[x]]--; } inline int ask(int x) { int bk=x/block2; int ans=0; for(int i=0;i<bk;i++) ans+=cnt[i]; for(int i=bk*block2;i<=x;i++) ans+=cnt2[i]; return ans; } int main() { block2=sqrt(N); int num=N/block2+5; cnt=new int[num]; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",a+i); } for(int i=1;i<=m;i++) { scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].x); q[i].id=i; } block=n/sqrt(m*2/3*1.0); sort(q+1,q+m+1,cmp); int l=1,r=0; for(int i=1;i<=m;i++) { int ql=q[i].l,qr=q[i].r; while(l>ql) add(--l); while(l<ql) del(l++); while(r<qr) add(++r); while(r>qr) del(r--); res[q[i].id]=ask(q[i].x); } for(int i=1;i<=m;i++) printf("%d\n",res[i]); return 0; }