首页
登录 | 注册

【题解】Luogu CF86D Powerful array

原题传送门

裸的莫队啊,我博客里有对莫队较详细的介绍

这道题很简单,可以说是裸的模板

但是如何在已有的值上进行操作?

小学生应该都知道【题解】Luogu CF86D Powerful array

那么转移就超级简单了qaq

inline void add(register int c)
{
    sum+=(num[c]+num[c]+1)*c;
    ++num[c];
}
inline void del(register int c)
{
    --num[c];
    sum-=(num[c]+num[c]+1)*c;
}

要开long long(虽说我没试过int,但我觉得会炸int)

#include <bits/stdc++.h>
#define N 200005
using namespace std;
inline int read()
{
    register int x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
}
inline void write(register long long x)
{
    if(!x)putchar('0');if(x<0)x=-x,putchar('-');
    static int sta[25];int tot=0;
    while(x)sta[tot++]=x%10,x/=10;
    while(tot)putchar(sta[--tot]+48);
}
struct query{
    int l,r,id,bl;
}q[N];
int a[N],blocksize=0,num[1000005];
long long ans[N],sum=0;
inline void add(register int c)
{
    sum+=(num[c]+num[c]+1)*c;
    ++num[c];
}
inline void del(register int c)
{
    --num[c];
    sum-=(num[c]+num[c]+1)*c;
}
inline bool cmp(register query a,register query b)
{
    return a.bl!=b.bl?a.l<b.l:(a.bl&1?a.r<b.r:a.r>b.r);
}
int main()
{
    int n=read(),m=read();
    blocksize=sqrt(n);
    for(register int i=1;i<=n;++i)
        a[i]=read();
    for(register int i=1;i<=m;++i)
    {
        int l=read(),r=read();
        q[i]=(query){l,r,i,(l-1)/blocksize+1};
    }
    sort(q+1,q+1+m,cmp);
    int l=1,r=0;
    for(register int i=1;i<=m;++i)
    {
        int ll=q[i].l,rr=q[i].r;
        while(ll<l)
            add(a[--l]);
        while(ll>l)
            del(a[l++]);
        while(rr>r)
            add(a[++r]);
        while(rr<r)
            del(a[r--]);
        ans[q[i].id]=sum;
    }
    for(register int i=1;i<=m;++i)
        write(ans[i]),printf("\n");
    return 0;
 } 

相关文章

  • 页面性能优化-原生JS实现图片懒加载
         在项目开发中,我们往往会遇到一个页面需要加载很多图片的情况.我们可以一次性加载全部的图片,但是考虑到用户有可能只浏览部分图片.所以我们需要对图片加载进行优化,只加载浏览器窗口内的图片,当用户滚动时,再加载更多的图片.这种加载图片的 ...
  • Windbg分析高内存占用问题
    1. 问题简介 最近产品发布大版本补丁更新,一商超客户升级后,反馈系统经常奔溃,导致超市的收银系统无法正常收银,现场排队付款的顾客更是抱怨声声.为了缓解现场的情况, 客户都是手动回收IIS应用程序池才能解决. 这样的后果是很严重的,接到反馈 ...
  • More Effective C++
    More Effective C++ 35个改善编程与设计的有效方法 只有深入了解C++编译器如何解释代码, 才有可能用C++语言写出健壮的软件. C++的难学, 不仅在其广博的语法, 语法背后的语义, 语义背后的深层思维, 深层思维背后的 ...
  • MongoDB【快速入门】
    1.MongDB 简介 MongoDB(来自于英文单词"Humongous",中文含义为"庞大")是可以应用于各种规模的企业.各个行业以及各类应用程序的开源数据库.作为一个适用于敏捷开发的数据库,Mo ...
  • foreach绑定对于数组中的每一个元素复制一节标记语言,也就是html,并且将这节标记语言和数组里面的每一个元素绑定.当我们呈现一组list数据,或者一个表格的时候,十分有用. 如果你绑定的数组是一个"监控数组" ,o ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.077 s.
京ICP备10005923号