86D - Powerful array

本文主要是介绍86D - Powerful array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在重载运算符那里，注释掉的写法在某组测试数据上re。

然后我一行行代码找，找了很久很久。。。。。很久。。。。。。。很久。。。。。。很久。。。。。。。。很久，最后把括号加上就ac。不知道是codeforces编译器特殊？

累觉不爱。。。。。。。。。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define LL long long
#define maxn 1100000
LL n,m;
struct Query
{LL pos,l,r;LL ans;LL k;void getData(int i){scanf("%I64d%I64d",&l,&r);k=l/((int)sqrt(n)+1);pos=i;}friend bool operator<(Query x,Query y){return (x.k==y.k)?(x.r<y.r):(x.k<y.k);//return x.k==y.k?x.r<y.r:x.k<y.k);累觉不爱}
}query[maxn];
LL num[maxn];
LL vis[1100000];
LL ans;
void insert(LL x)
{x=num[x];ans+=(vis[x]*2*x+x);vis[x]++;
}
void erase(LL x)
{x=num[x];ans+=(x-vis[x]*2*x);vis[x]--;
}
bool cmp(Query x,Query y)
{return x.pos<y.pos;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)scanf("%I64d",num+i);        for(int i=1;i<=m;i++)query[i].getData(i);sort(query+1,query+1+m);ans=0;LL l=query[1].l,r=query[1].r;for (LL i=l;i<=r;i++) {  ans+=((vis[num[i]]<<1)+1)*num[i];  vis[num[i]]++;  }query[1].ans=ans;for(int i=2;i<=m;i++){while(r<query[i].r)insert(++r);while(l<query[i].l)erase(l++);while(r>query[i].r)erase(r--);while(l>query[i].l)insert(--l);query[i].ans=ans;}sort(query+1,query+1+m,cmp);for(int i=1;i<=m;i++)printf("%I64d\n",query[i].ans);return 0;
}

这篇关于86D - Powerful array的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---