首页 > 其他分享 >莫队

莫队

时间:2024-04-15 22:22:06浏览次数:21  
标签:cnt int sum add include 莫队 block

查询区间每个数出现的个数,离线算法,O(nsqrt(n))

一、普通莫队

题目链接

https://www.luogu.com.cn/problem/P2709

题目大意

image

题目代码

#include<iostream>
#include<algorithm>
#include<cmath>
#define ll long long
const int N = 5e4 + 5;
using namespace std;
int n,m,k,block;
struct node{
    int l,r,id;
}q[N];
ll a[N],cnt[N],ans[N],sum;
bool cmp(const node& a,const node& b){
    if(a.l / block != b.l / block) return a.l < b.l;
    return a.r < b.r;
}
void add(int x){
    sum -= cnt[x] * cnt[x];
    ++cnt[x];
    sum += cnt[x] * cnt[x];
}
void del(int x){
    sum -= cnt[x] * cnt[x];
    --cnt[x];
    sum += cnt[x] * cnt[x];
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    block = sqrt(n);
    for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
    for(int i = 1;i <= m;++i) scanf("%d%d",&q[i].l,&q[i].r),q[i].id = i;
    sort(q + 1,q + m + 1,cmp);
    for(int i = 1,l = 1,r = 0;i <= m;++i){
        while(l > q[i].l) add(a[--l]);
        while(r < q[i].r) add(a[++r]);
        while(l < q[i].l) del(a[l++]);
        while(r > q[i].r) del(a[r--]);
        ans[q[i].id] = sum;
    }
    for(int i = 1;i <= m;++i){
        printf("%lld\n",ans[i]);
    }
    return 0;
}

标签:cnt,int,sum,add,include,莫队,block
From: https://www.cnblogs.com/gebeng/p/18137048

相关文章

  • 莫队学习笔记
    目录普通莫队初遇——从暴力谈起困境——乱跑的指针优化——顺路而为之带修莫队参考资料普通莫队初遇——从暴力谈起我们通过一道例题来讨论普通莫队。题目链接。观察数据范围,一个很直接的想法是:开一个数组\(cnt\),\(cnt_i\)表示在询问的区间内数字\(i\)出现的次数。对于......
  • #莫队二次离线,根号分治#洛谷 5398 [Ynoi2018] GOSICK
    题目\(m\)组询问求\(\sum_{l\leqi,j\leqr}[a_i\bmoda_j==0],n,m,a_i\leq5\times10^5\)分析设\(f(l,r,x)\)表示\(i或j\in[1,x],i或j\in[l,r]\)时的答案,\(g_x\)表示\([1,x]\)的答案,根号的做法可以通过三秒由于涉及区间内的求值,需要在莫队的基础上二次离线,那......
  • C114 回滚莫队 歴史の研究
    视频链接:C114回滚莫队歴史の研究_哔哩哔哩_bilibili   LuoguAT_joisc2014_c歴史の研究//回滚莫队O(n^(3/2))#include<iostream>#include<cstring>#include<algorithm>#include<cmath>usingnamespacestd;#defineLLlonglongconstintN=1000005;......
  • 分块与莫队
    不沾树的博客变短了好多。分块例题这道题显然可以使用线段树乱搞过去,不过为了给主角面子我们假设我们不会做。对于一些难以使用数据结构维护答案的序列问题,我们考虑暴力。但是暴力太慢了,于是人们提出了分块。分块,就是把序列分成许多的小段,通过一些神秘的处理实现优化暴力。......
  • C113 带修莫队 P1903 [国家集训队] 数颜色/维护队列
    视频链接:   LuoguP1903[国家集训队]数颜色/维护队列//带修莫队O(n^(5/3))#include<iostream>#include<cstring>#include<algorithm>#include<cmath>usingnamespacestd;constintN=1000005;intn,m,B,mq,mr,a[N];intsum,cnt[N],ans[N];st......
  • C112 莫队算法 P1494 [国家集训队] 小 Z 的袜子
    视频链接:  LuoguP1494[国家集训队]小Z的袜子//普通莫队O(n*sqrt(n))#include<iostream>#include<cstring>#include<algorithm>#include<cmath>usingnamespacestd;constintN=50005;intn,m,B,a[N];intsum,cnt[N],ans1[N],ans2[N];str......
  • C111【模板】莫队算法 P2709 小B的询问
    视频链接:C111【模板】莫队算法P2709小B的询问_哔哩哔哩_bilibili   LuoguP2709小B的询问//普通莫队O(n*sqrt(n))#include<iostream>#include<cstring>#include<algorithm>#include<cmath>usingnamespacestd;constintN=50005;intn,m,k,B,a[N];......
  • 莫队算法学习笔记
    Part.1引入当你遇到一个区间询问但是难以用线段树等log算法维护的时候怎么办?那就是——莫队!莫队这个东西能支持区间修改、区间查询的操作,但是这种算法要求离线。莫队有很多种,详细请看下文。Part.2普通莫队我们先来看一道例题(P1972的削弱版):给你一个长度为\(n\)的序列......
  • 初识莫队
    莫队个人理解:这是一种较为暴力的算法,适用于解决维护序列区间操作的问题。主要思想:把所有的操作离线,按某种方式重新排序。操作过程中不断转移当前区间的答案。(\([L,R]\Rightarrow[L\pm1,R\pm1]\))希望转移的复杂度尽量的小(\(O(n\sqrt{m})\))01-普通的莫队(无修改......
  • 莫队
    以为自己一辈子接触不到的算法,本来以为很高深,没想到是优雅的暴力,太绝妙了对于多个区间查询,例如区间最大值等,我们考虑暴力,枚举区间$[L,R]$,取最大值即可,时间复杂度$O(m*(R-L))$,跑不起,所以我们借用数据结构,单调队列,树状数组等等,但是如果此时我们考虑优化暴露首先我......