P2709 小B的询问 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
12345678910111213141516171819202122232425262728293031323334353637383940414243444546
#include <iostream> #include <cmath> #include <algorithm> using namespace std; const int maxn = 5e4+5; int a[maxn],pos[maxn],cnt[maxn]; long long ans[maxn]; long long res; struct Q { int l,r,k; }q[maxn]; bool cmp(Q x,Q y){ return pos[x.l]==pos[y.l]?x.r<y.r:pos[x.l]<pos[y.l]; } void Add(int n) { cnt[a[n]]++; res+=cnt[a[n]]*cnt[a[n]]-(cnt[a[n]]-1)*(cnt[a[n]]-1); } void Sub(int n) { cnt[a[n]]--; res-=(cnt[a[n]]+1)*(cnt[a[n]]+1)-cnt[a[n]]*cnt[a[n]]; } int main() { int n,m,k; cin>>n>>m>>k; int siz=sqrt(n); for(int i=1;i<=n;i++)//注意!!! 数组是从1开始 { cin>>a[i]; pos[i]=i/siz;//分块,这也是必要的 } for(int i=0;i<m;i++) { cin>>q[i].l>>q[i].r; q[i].k=i; } sort(q,q+m,cmp); int l=1,r=0;//注意!!!一定要l>r不然会导致结果出错,血的教训!!!! for(int i=0;i<m;i++) { while(q[i].l<l) Add(--l); while(q[i].r>r) Add(++r); while(q[i].l>l) Sub(l++); while(q[i].r<r) Sub(r--); ans[q[i].k]=res; } for(int i=0;i<m;i++) cout<<ans[i]<<endl; return 0; }
例题 1.重复的数 - 蓝桥云课 (lanqiao.cn)
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
#include <iostream> #include <cstring> #include <cmath> #include <map> #include <algorithm> using namespace std; const int maxn=1e5+5; struct node { int l,r,k,i; }; node mp[maxn]; int num[maxn];//i出现的次数 int vis[maxn];//出现i次的数有几个 int cnt[maxn];//记录答案 int pos[maxn]; int a[maxn]; int siz=maxn; bool cmp(node x,node y){ return pos[x.l]==pos[y.l]?x.r<y.r:pos[x.l]<pos[y.l]; } void add(int i){ vis[num[a[i]]]--; num[a[i]]++; vis[num[a[i]]]++; } void sub (int i){ vis[num[a[i]]]--; num[a[i]]--; vis[num[a[i]]]++; } int main () { memset (vis,0,sizeof (vis)); memset (num,0,sizeof (num)); int n,m; cin>>n; int siz=sqrt(n); for (int i=1;i<=n;i++){ cin>>a[i]; pos[i]=i/siz; } cin>>m; for (int i=1;i<=m;i++){ cin>>mp[i].l>>mp[i].r>>mp[i].k; mp[i].i=i; } sort (mp+1,mp+1+m,cmp); int l=1,r=0; for (int i=1;i<=m;i++){ while (mp[i].l<l) add(--l); while (mp[i].r>r) add(++r); while (mp[i].l>l) sub(l++); while (mp[i].r<r) sub(r--); cnt[mp[i].i]=vis[mp[i].k]; } for (int i=1;i<=m;i++){ cout<<cnt[i]<<endl; } return 0; }