5 条题解
-
2
1：纯暴力
45分
#include<bits/stdc++.h> using namespace std; int n,q,a[500010]; int main() { scanf("%d%d",&n,&q); for(int i=0;i<n;i++)scanf("%d",&a[i]); for(int i=1,l,r,x;i<=q;i++) { int ans=0; scanf("%d%d%d",&l,&r,&x); for(int j=l;j<r;j++)if(a[j]==x)ans++; printf("%d\n",ans); } return 0; }2：用map前缀和优化一下
54分
#include<bits/stdc++.h> using namespace std; map<pair<int,int>,int>mp; map<int,bool>v; int n,q,a[500010],b[500010],id=0; bool cmp(int a,int b){return a>b;} int main() { scanf("%d%d",&n,&q); for(int i=0;i<n;i++) { scanf("%d",&a[i]),mp[{i,a[i]}]++; if(!v[a[i]])b[++id]=a[i]; v[a[i]]=1; } sort(b+1,b+id+1,cmp); for(int i=1;i<=id;i++)for(int j=1;j<=n;j++)mp[{j,b[i]}]+=mp[{j-1,b[i]}]; for(int i=1,l,r,x;i<=q;i++) { scanf("%d%d%d",&l,&r,&x); printf("%d\n",mp[{r-1,x}]-mp[{l-1,x}]); } return 0; }3：100分，二分法解决
将每个数出现的下标按从小到大的顺序存到一个vector数组中，后在查询时查找第一个的下标 和第一个的下标，题目中是求到中的出现次数，所以刚好是(就是它们中间差了几个下标，相当于出现了几次)
AC!
#include<bits/stdc++.h> using namespace std; const int N=5e5+10; vector<int>G[N];set<int>s; int a[N],b[N],k,n,q; int getid(int x){return lower_bound(b+1,b+k+1,x)-b;} int main() { scanf("%d%d",&n,&q); for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i],s.insert(a[i]); sort(b+1,b+n+1);k=unique(b+1,b+n+1)-b-1; for(int i=1;i<=n;i++)a[i]=getid(a[i]); for(int i=1;i<=n;i++)G[a[i]].push_back(i); for(int i=1,l,r,x;i<=q;i++) { scanf("%d%d%d",&l,&r,&x);l++;r++; if(!s.count(x)){puts("0");continue;}//特判，原数组中就没有出现这个数 x=getid(x); auto lt=lower_bound(G[x].begin(),G[x].end(),l); auto rt=lower_bound(G[x].begin(),G[x].end(),r); printf("%d\n",rt-lt); } return 0; } -
0
fuxuanyuan
LV 9
@ 2026-8-24 9:02:31
神秘做法：开Q个pb_ds+离散化+mp，直接解决
#include<bits/stdc++.h> #include<bits/extc++.h> using namespace std; using namespace __gnu_pbds; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; const int N=5e5+10; ordered_set se[N]; int a[N],b[N]; map<int,int>mp; int main() { int n,q; scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=a[i]; } sort(b+1,b+n+1); int nn=unique(b+1,b+n+1)-b-1; for(int i=1;i<=nn;i++) { mp[b[i]]=i; } for(int i=1;i<=n;i++) { se[mp[a[i]]].insert(i); } while(q--) { int l,r,x; scanf("%d%d%d",&l,&r,&x); l++; if(!mp[x]) { printf("0\n"); continue; } x=mp[x]; int ll=se[x].order_of_key(l)+1,rr=se[x].order_of_key(r+1); printf("%d\n",max(0,rr-ll+1)); } return 0; } -
0
#include<bits/stdc++.h> using namespace std; typedef long long ll; int n,q,a[500010]; struct Q{ int op,x,y,v,id; }c[2000010]; bool cmp(Q a,Q b){ if(a.v!=b.v)return a.v<b.v; return a.op<b.op; } int ans[500010]; int lowbit(int x){ return x&(-x); } struct BIT{ int tr[500010]; void add(int x,int v){ for(int i=x;i<=n;i+=lowbit(i)){ tr[i]+=v; } } int find(int x){ int ans=0; for(int i=x;i;i-=lowbit(i)){ ans+=tr[i]; } return ans; } }tr; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n>>q; int id=0; for(int i=1;i<=n;i++){ cin>>a[i]; c[++id]={0,i,1,a[i],0}; c[++id]={0,i,-1,a[i]+1,0}; } for(int i=1;i<=q;i++){ int l,r,x; cin>>l>>r>>x;l++; c[++id]={1,l,r,x,i}; } sort(c+1,c+1+id,cmp); for(int i=1;i<=id;i++){ if(c[i].op==0){ tr.add(c[i].x,c[i].y); } else{ ans[c[i].id]=tr.find(c[i].y)-tr.find(c[i].x-1); } } for(int i=1;i<=q;i++){ cout<<ans[i]<<'\n'; } return 0; } -
0
yanchengyi2024
LV 9
@ 2026-8-4 9:11:14
发一篇莫队的题解（是不是小题大做了）
感兴趣的可以去做一下后缀题目
还不会莫队的出门左转思路
题目有个区间查询，每次查询一个固定数出现次数，这不就莫队吗？
（为啥一道普及的题要用莫队）但是有一个大问题，每一个高达，数组都开不下。但是注意到一共就个数，离散化即可。
AC代码？
#include<bits/stdc++.h> using namespace std; const int N=5e5+10; struct node{int l,r,x,id;}q[N]; int a[N],b[N],v[N],n,Q,ans[N],B; void add(int x){v[b[x]]++;} void del(int x){v[b[x]]--;} bool cmp(node n1,node n2) { if(n1.l/B!=n2.l/B)return n1.l<n2.l; if((n1.l/B)&1)return n1.r<n2.r; return n1.r>n2.r; } int main() { scanf("%d%d",&n,&Q); B=sqrt(n); for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i]; sort(a+1,a+n+1); int m=unique(a+1,a+n+1)-a-1; for(int i=1;i<=Q;i++) { scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].x); q[i].l++;q[i].id=i; int id=lower_bound(a+1,a+m+1,q[i].x)-a; q[i].x=(id<=m&&a[id]==q[i].x)?id:0; } for(int i=1;i<=n;i++)b[i]=lower_bound(a+1,a+m+1,b[i])-a; sort(q+1,q+Q+1,cmp); int l=1,r=0; for(int i=1;i<=Q;i++) { if(q[i].l>q[i].r||q[i].x==0){ans[q[i].id]=0;continue;} while(r<q[i].r)add(++r); while(r>q[i].r)del(r--); while(l<q[i].l)del(l++); while(l>q[i].l)add(--l); ans[q[i].id]=v[q[i].x]; } for(int i=1;i<=Q;i++)printf("%d\n",ans[i]); return 0; }不对，为什么91分？
再仔细审一下题，注意到，这个很关键，直接会出幺蛾子，因此需要另加特判，
真AC代码
#include<bits/stdc++.h> using namespace std; const int N=5e5+10; struct node{int l,r,x,id;}q[N]; int a[N],b[N],v[N],n,Q,ans[N],B; void add(int x){v[b[x]]++;} void del(int x){v[b[x]]--;} bool cmp(node n1,node n2) { if(n1.l/B!=n2.l/B)return n1.l<n2.l; if((n1.l/B)&1)return n1.r<n2.r; return n1.r>n2.r; } int main() { scanf("%d%d",&n,&Q); B=sqrt(max(1,n)); for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i]; sort(a+1,a+n+1); int m=unique(a+1,a+n+1)-a-1; for(int i=1;i<=Q;i++) { scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].x); q[i].l++;q[i].id=i; int id=lower_bound(a+1,a+m+1,q[i].x)-a; q[i].x=(id<=m&&a[id]==q[i].x)?id:0; } for(int i=1;i<=n;i++)b[i]=lower_bound(a+1,a+m+1,b[i])-a; sort(q+1,q+Q+1,cmp); int l=1,r=0; for(int i=1;i<=Q;i++) { if(q[i].l>q[i].r||q[i].x==0){ans[q[i].id]=0;continue;} while(r<q[i].r)add(++r); while(r>q[i].r)del(r--); while(l<q[i].l)del(l++); while(l>q[i].l)add(--l); ans[q[i].id]=v[q[i].x]; } for(int i=1;i<=Q;i++)printf("%d\n",ans[i]); return 0; }出题人的恶趣味……
-
0
#include<bits/stdc++.h> using namespace std; const int N=5e5+10; vector<int>G[N]; int a[N],b[N],k; int getid(int x){return lower_bound(b+1,b+k+1,x)-b;} int main() { int n,q;cin>>n>>q;set<int>s; for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i],s.insert(a[i]); sort(b+1,b+n+1);k=unique(b+1,b+n+1)-b-1; for(int i=1;i<=n;i++)a[i]=getid(a[i]); for(int i=1;i<=n;i++)G[a[i]].push_back(i); for(int i=1;i<=q;i++) { int l,r,x;cin>>l>>r>>x;l++;r++; if(!s.count(x)){cout<<0<<'\n';continue;} x=getid(x); auto lt=lower_bound(G[x].begin(),G[x].end(),l); auto rt=lower_bound(G[x].begin(),G[x].end(),r); cout<<rt-lt<<'\n'; } return 0; }
taojinghua
LV 9
@ 2026-8-2 14:39:24
- 1