洛谷 P2709 BZOJ 3781 小B的询问

题目描述

小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

说明

对于全部的数据,1<=N、M、K<=50000

吐槽

  BZOJ居然把这题设成权限题,我们这种穷人做不起啊,放个题号吧。

  我的代码在洛谷上跑的挺快,刚开始没开O2,跑了1900+ms,然后去大牛分站交了一波,瞬间540毫秒,rank3了啊!估计我的程序最大的耗时处在两个sort上,algorithm里的东西和STL里的东西缺氧,吸了氧就跑得飞快,几乎是缺氧时的四倍速度了。

  后来加快读、乘法换成位运算、另开一个数组$O(m)$记录答案而不是第二次排序,尤其是最后一项,整整少了60ms,终于卡到了473ms,目前的洛谷rank1.

解题思路

  一道裸的莫队。莫队的原理可以看我这篇博文,每个莫队题目最重要的步骤都是推导出区间中减少一个元素或加入一个元素后答案的变化。

  这题推公式不难。设当前区间$[l,r]$的答案为$t$,那么增加(l--或r++)一个元素时,设增加元素的颜色为k (l-1或r+1),$f(k)$为题目中的$c(k)$,那么$t+=(f(k)+1)^2-f^2(k)=2*f(k)+1$,同理,减少一个颜色为k的元素时$t-=f^2(k)-(f(k)+1)^2=2*f(k)-1$,于是就套上莫队的标志“四个while”吧。

源代码

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;

inline int get()
{
    char c;short f = 1; int res = 0;
    while (( (c=getchar())<48||c>57) && c!= ‘-‘);
     if (c==‘-‘) f = -1;
      else res = c- ‘0‘;
    while ( (c = getchar()) >= 48 && c <= 57)
     res = res * 10 + c -‘0‘;
    return f *res;
}

int n,m,k;
int c[50010]={0};
int f[50010]={0};

struct query{
    int id,pos,l,r,ans;
}a[50010];
int aa[50010]={0};
inline int cmp1(const query & a,const query & b)
{
    return a.pos==b.pos?a.r<b.r:a.pos<b.pos;
}
int main()
{
    n=get(),m=get(),k=get();
    for(int i=1;i<=n;i++)
        c[i]=get();
    for(int i=1,l,r,kuai=sqrt(n);i<=m;i++)
    {
        l=get();
        r=get();
        a[i]={i,l/kuai,l,r,0};
    }
    sort(a+1,a+1+m,cmp1);
    for(int i=1,l=0,r=0,t=0;i<=m;i++)
    {
        while(r<a[i].r)
        {
            r+=1;
            t+=(f[c[r]]<<1)+1;
            f[c[r]]+=1;
        }
        while(l<a[i].l)
        {
            t-=(f[c[l]]<<1)-1;
            f[c[l]]--;
            l++;
        }
        while(l>a[i].l)
        {
            l--;
            t+=(f[c[l]]<<1)+1;
            f[c[l]]++;
        }
        while(r>a[i].r)
        {
            t-=(f[c[r]]<<1)-1;
            f[c[r]]--;
            r--;
        }
        a[i].ans=t;
    }
    for(int i=1;i<=m;i++) aa[a[i].id]=a[i].ans-1;
    for(int i=1;i<=m;i++) printf("%d\n",aa[i]);
    return 0;
}
时间: 06-16

洛谷 P2709 BZOJ 3781 小B的询问的相关文章

Bzoj 3781: 小B的询问 莫队,分块,暴力

3781: 小B的询问 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 426  Solved: 284[Submit][Status][Discuss] Description 小B有一个序列,包含N个1~K之间的整数.他一共有M个询问,每个询问给定一个区间[L..R],求Sigma(c(i)^2)的值,其中i的值从1到K,其中c(i)表示数字i在[L..R]中的重复次数.小B请你帮助他回答询问. Input 第一行,三个整数N.M.K. 第二行

bzoj 3781 小B的询问——分块

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3781 非常经典的分块套路.于是时间空间比大家的莫队差了好多-- #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define ll long long using namespace std; const i

BZOJ 3781 小B的询问

上一道题的双倍经验. #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define maxn 50050 using namespace std; long long n,m,k,col[maxn],cnt[maxn],ret=0,pos[maxn],block; struct query { long long

BZOJ 3781 小B的询问 莫队算法

题目大意:一共有M个询问,每个询问给定一个区间[L..R],求Sigma(c(i)^2)的值,其中i的值从1到K,其中c(i)表示数字i在[L..R]中的重复次数. 思路:莫队走起. CODE: #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 50010 using namespac

洛谷 P2827 BZOJ 4721 UOJ #264 蚯蚓

题目描述 本题中,我们将用符号表示对c向下取整,例如:. 蛐蛐国最近蚯蚓成灾了!隔壁跳蚤国的跳蚤也拿蚯蚓们没办法,蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓. 蛐蛐国里现在共有n只蚯蚓(n为正整数).每只蚯蚓拥有长度,我们设第i只蚯蚓的长度为,并保证所有的长度都是非负整数(即:可能存在长度为0的蚯蚓). 每一秒,神刀手会在所有的蚯蚓中,准确地找到最长的那一只(如有多个则任选一个)将其切成两半.神刀手切开蚯蚓的位置由常数p(是满足0<p<1的有理数)决定,设这只蚯蚓长度为x,神刀手会将其切成两只长度

洛谷 P3227 BZOJ 3144 [HNOI2013]切糕

题目描述 经过千辛万苦小 A 得到了一块切糕,切糕的形状是长方体,小 A 打算拦腰将切糕切成两半分给小 B.出于美观考虑,小 A 希望切面能尽量光滑且和谐.于是她找到你,希望你能帮她找出最好的切割方案. 出于简便考虑,我们将切糕视作一个长 P.宽 Q.高 R 的长方体点阵.我们将位于第 z层中第 x 行.第 y 列上(1≤x≤P, 1≤y≤Q, 1≤z≤R)的点称为(x,y,z),它有一个非负的不和谐值 v(x,y,z).一个合法的切面满足以下两个条件: 与每个纵轴(一共有 P*Q 个纵轴)有且

洛谷 P2486 BZOJ 2243 [SDOI2011]染色

题目描述 给定一棵有n个节点的无根树和m个操作,操作有2类: 1.将节点a到节点b路径上所有点都染成颜色c: 2.询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“112221”由3段组成:“11”.“222”和“1”. 请你写一个程序依次完成这m个操作. 输入输出格式 输入格式: 第一行包含2个整数n和m,分别表示节点数和操作数: 第二行包含n个正整数表示n个节点的初始颜色 下面 行每行包含两个整数x和y,表示x和y之间有一条无向边. 下面 行每行描述一个操作: “C a

洛谷 P3178 BZOJ 4034 [HAOI2015]树上操作

题目描述 有一棵点数为 N 的树,以点 1 为根,且树点有边权.然后有 M 个操作,分为三种:操作 1 :把某个节点 x 的点权增加 a .操作 2 :把某个节点 x 为根的子树中所有点的点权都增加 a .操作 3 :询问某个节点 x 到根的路径中所有点的点权和. 输入输出格式 输入格式: 第一行包含两个整数 N, M .表示点数和操作数.接下来一行 N 个整数,表示树中节点的初始权值.接下来 N-1 行每行三个正整数 fr, to , 表示该树中存在一条边 (fr, to) .再接下来 M 行

洛谷 P2056 BZOJ 2743 [HEOI2012]采花

//表示真的更喜欢洛谷的题面 题目描述 萧芸斓是 Z国的公主,平时的一大爱好是采花. 今天天气晴朗,阳光明媚,公主清晨便去了皇宫中新建的花园采花.花园足够大,容纳了 n 朵花,花有 c 种颜色(用整数 1-c 表示) ,且花是排成一排的,以便于公主采花. 公主每次采花后会统计采到的花的颜色数, 颜色数越多她会越高兴! 同时, 她有一癖好,她不允许最后自己采到的花中,某一颜色的花只有一朵.为此,公主每采一朵花,要么此前已采到此颜色的花,要么有相当正确的直觉告诉她,她必能再次采到此颜色的花. 由于时