前置知识：分块
莫队是非常好的数据结构，可以离线解决很多序列问题
当对于一个查询\([l,r]\)可以\(O(1)\)转移到\([l-1,r],[l+1,r],[l,r-1],[l,r+1]\)时可以考虑用(普通)莫队
莫队先读入所有的询问,接着离线对于所有询问区间 \([l,r]\) , 用 \(l\) 所在块的编号为第一关键字， \(r\) 为第二关键字从小到大进行排序
inline bool cmp(const blo &a,const blo &b){
if(bl[a.l]<bl[b.l])return 1;
if(bl[a.l]>bl[b.l])return 0;
if(bl[a.l]&1)return a.r<b.r;
return a.r>b.r;
}
上面的代码运用了奇偶化排序来优化莫队
奇偶化排序不会优化莫队的复杂度却能减少大量常数
奇偶化排序即对于属于奇数块的询问，\(r\)按从小到大排序;对于属于偶数块的排序，\(r\) 从大到小排序。
\(r\) 指针在处理完这个奇数块的问题后，在返回的途中处理偶数块的问题，再向 \(n\) 移动处理下一个奇数块的问题，优化 \(r\) 指针的移动次数。
根据OI-wiki，这样一般可以让程序快 30% 左右
实现
inline void Solve(){
sort(q+1,q+m+1,cmp);
int l=1,r=0;
for(int i=1;i<=m;i++){
if(q[i].l==q[i].r){
ans[q[i].id][0]=0;
ans[q[i].id][1]=1;
continue;
}
while(l>q[i].l) Add(--l);
while(r<q[i].r) Add(++r);
while(l<q[i].l) Del(l++);
while(r>q[i].r) Del(r--);
//注意上面的顺序
ans[q[i].id][0]=sum;
ans[q[i].id][1]=(r-l+1)*(r-l)/2;
}
}
然后Add和Del看情况写就行
普通莫队这样就没了
先搞几道例题练练手
莫队板子题直接做就行
点击查看代码
#include<bits/stdc++.h>
#define _for(i, a, b) for (int i = a; i <= b; ++i)
#define for_(i, a, b) for (int i = a; i >= b; --i)
#define int long long
/* --------------- fast io --------------- */
using namespace std;
namespace Fread{const int SIZE = (1 << 18);char buf[SIZE],*S,*T;inline char getchar() {if(S==T){T = (S = buf) + fread(buf,1,SIZE,stdin); if(S==T) return '\n';} return *S++;}}
namespace Fwrite {const int SIZE = (1 << 18);char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout), S=buf;}inline void putchar(char c){*S++=c;if(S==T)flush();}struct NTR{ ~NTR() { flush(); }}ztr;}
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
namespace Fastio{
struct Reader{
template <typename T>
Reader&operator>>(T&x){char c=getchar();bool f=false;while (c<'0'||c>'9') { if(c == '-')f = true;c=getchar();}x=0;while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}if(f)x=-x;return *this;}
Reader&operator>>(double & x) {char c=getchar();short f=1,s=0;x=0;double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}
Reader&operator>>(long double&x){char c=getchar();short f=1,s=0;x=0;long double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}
Reader&operator>>(__float128&x){char c=getchar();short f=1,s=0;x=0;__float128 t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.') c = getchar();else return x*=f, *this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return *this;}
Reader&operator>>(char&c){c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}
Reader&operator>>(char*str){int len=0;char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return *this;}
Reader&operator>>(string&str){char c=getchar();str.clear();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str.push_back(c),c=getchar();return *this;}
template<class _Tp>
Reader&operator>>(vector<_Tp>&vec){for(unsigned i=0;i<vec.size();i++)cin>>vec[i];return *this;}
template<class _Tp,class _tp>
Reader&operator>>(pair<_Tp,_tp>&a){cin>>a.first>>a.second;return *this;}
Reader(){}
}cin;
inline int read(){int n;cin>>n;return n;}
const char endl='\n';
struct Writer{
static const int set_precision = 6;
typedef int mxdouble;
template<typename T>
Writer&operator<<(T x){if(x==0)return putchar('0'),*this;if(x<0)putchar('-'),x=-x;static int sta[45];int top=0;while(x)sta[++top]=x%10,x/=10;while(top)putchar(sta[top]+'0'),--top;return*this;}
Writer&operator<<(double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(double)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
Writer&operator<<(long double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(long double)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
Writer&operator<<(__float128 x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(__float128)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
Writer&operator<<(char c){putchar(c);return*this;}
Writer& operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}
Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}
Writer&operator<<(string str){int st=0,ed=str.size();while(st<ed) putchar(str[st++]);return *this;}
template<class _Tp>
Writer&operator<<(vector<_Tp>vec){for(unsigned i=0;i<vec.size()-1;i++)cout<<vec[i]<<" ";cout<<vec[vec.size()-1];return *this;}
template<class _Tp,class _tp>
Writer&operator<<(pair<_Tp,_tp>a){cout<<a.first<<" "<<a.second;return *this;}Writer(){}
}cout;
}
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define read Fastio::read
/* --------------- fast io --------------- */
int n,m,k,sqrtn,a[1000001],ans[1000001];
class Mobius{
public:
int sum,bl[1000001];
class block{
public:
int l,r,id,k;
inline void Join(int li,int ri,int i){
l=li,r=ri,
id=i,k=(li-1)/sqrtn+1;
return;
}
inline bool operator<(block p){
if(k!=p.k)return l<p.l;
if(k&1)return r<p.r;
return r>p.r;
}
}blo[100001];
inline void Join(int l,int r,int i){
blo[i].Join(l,r,i);
return;
}
inline void Add(int i){
sum-=bl[i]*bl[i],
++bl[i],
sum+=bl[i]*bl[i];
}
inline void Del(int i){
sum-=bl[i]*bl[i],
--bl[i],
sum+=bl[i]*bl[i];
}
inline void Solve(){
sort(blo+1,blo+m+1);
int l=1,r=0;
for(int i=1;i<=m;++i){
while(l>blo[i].l)
Add(a[--l]);
while(r<blo[i].r)
Add(a[++r]);
while(l<blo[i].l)
Del(a[l++]);
while(r>blo[i].r)
Del(a[r--]);
ans[blo[i].id]=sum;
}
}
}bl;
signed main(){
freopen("1.in","r",stdin);
n=read(),m=read(),k=read();
sqrtn=sqrt(n);
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<=m;++i){
int l=read(),r=read();
bl.Join(l,r,i);
//不知道为啥这里写bl.Join(read(),read(),i)就WA了
}
bl.Solve();
for(int i=1;i<=m;i++){
cout<<ans[i]<<endl;
}
}