cco网站素材,wordpress页面调用文章列表,350模板网,线上阿类电商平台题目描述 小B有一个序列#xff0c;包含N个1~K之间的整数。他一共有M个询问#xff0c;每个询问给定一个区间[L..R]#xff0c;求Sigma(c(i)^2)的值,其中i的值从1到K#xff0c;其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。 输入输出格式 输入格式包含N个1~K之间的整数。他一共有M个询问每个询问给定一个区间[L..R]求Sigma(c(i)^2)的值,其中i的值从1到K其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。 输入输出格式 输入格式 第一行三个整数N、M、K。 第二行N个整数表示小B的序列。 接下来的M行每行两个整数L、R。 输出格式 M行每行一个整数其中第i行的整数表示第i个询问的答案。 输入输出样例 输入样例#1 6 4 3 1 3 2 1 1 3 1 4 2 6 3 5 5 6 输出样例#1 6 9 5 2 说明 对于全部的数据1N、M、K50000 题解 练习一道莫队水题 加数删数的时候先把之前的贡献从当前答案里减掉完成加删数操作后再往答案里加个新的贡献就行了 #includebits/stdc.h
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN5000010;
int n,m,k,cnt[MAXN],A[MAXN],Be[MAXN],unit;
ll ans[MAXN],sum;
struct node{int l,r,id;inline bool operator (const node A) const {return Be[l]Be[A.l]?rA.r:lA.l;};
};
node query[MAXN];
templatetypename T inline void read(T x)
{T data0,w1;char ch0;while(ch!-(ch0||ch9))chgetchar();if(ch-)w-1,chgetchar();while(ch0ch9)data((T)data3)((T)data1)(ch^0),chgetchar();xdata*w;
}
templatetypename T inline void write(T x,char ch\0)
{if(x0)putchar(-),x-x;if(x9)write(x/10);putchar(x%100);if(ch!\0)putchar(ch);
}
templatetypename T inline void chkmin(T x,T y){x(yx?y:x);}
templatetypename T inline void chkmax(T x,T y){x(yx?y:x);}
templatetypename T inline T min(T x,T y){return xy?x:y;}
templatetypename T inline T max(T x,T y){return xy?x:y;}
inline void modify(int x,int k)
{sum-1ll*cnt[x]*cnt[x];cnt[x]k;sum1ll*cnt[x]*cnt[x];
}
int main()
{read(n);read(m);read(k);unitstd::sqrt(k);for(register int i1;in;i)read(A[i]);for(register int i1;ik;i)Be[i]i/unit1;for(register int i1;im;i){read(query[i].l),read(query[i].r);query[i].idi;}std::sort(query1,querym1);int l1,r0;for(register int i1;im;i){while(lquery[i].l)modify(A[l],-1);while(lquery[i].l)modify(A[--l],1);while(rquery[i].r)modify(A[r],1);while(rquery[i].r)modify(A[r--],-1);ans[query[i].id]sum;}for(register int i1;im;i)write(ans[i],\n);return 0;
} 转载于:https://www.cnblogs.com/hongyj/p/9066398.html
