求區間每種顏色出現次數平方和

---

?

寫裸題練手

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; typedef long long ll; const int N=5e4+5; inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; }int n,a[N],Q,k, block,m,pos[N]; struct meow{int l,r,id;bool operator <(const meow &x) const {return pos[l]<pos[x.l] || (pos[l]==pos[x.l] && r<x.r);} }q[N];int c[N]; ll now=0,ans[N]; inline void add(int x) {now+=2*c[a[x]]+1; c[a[x]]++;} inline void del(int x) {now-=2*c[a[x]]-1; c[a[x]]--;} void solve(){int l=1,r=0;for(int i=1;i<=Q;i++){while(r<q[i].r) r++, add(r);while(r>q[i].r) del(r), r--;while(l<q[i].l) del(l), l++;while(l>q[i].l) l--, add(l);ans[q[i].id]=now;} } int main(){freopen("in","r",stdin);n=read();Q=read();k=read();block=sqrt(n); m=(n-1)/block+1;for(int i=1;i<=n;i++) a[i]=read(), pos[i]=(i-1)/block+1;for(int i=1;i<=Q;i++) q[i].l=read(), q[i].r=read(), q[i].id=i;sort(q+1, q+1+Q);solve();for(int i=1;i<=Q;i++) printf("%lld\n",ans[i]); }

?

轉載于:https://www.cnblogs.com/candy99/p/6564155.html

總結

以上是生活随笔為你收集整理的BZOJ 3781: 小B的询问 [莫队]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。