首页 > 其他分享 >P2709 小B的询问

P2709 小B的询问

时间:2024-04-16 15:11:05浏览次数:32  
标签:int 询问 id num P2709 kuai 排序 sum

原题链接

题解

莫队算法是局限性非常大的优化,离线+无修改,它通过邻近区间修改复杂度为 \(O(1)\) 的特性让区间排序,然后再做修改,排序的规则是按块排序,然后左端点 \(l\) 在一个块里的按右端点排序

code

#include<bits/stdc++.h>
using namespace std;

int a[50005];

struct node
{
    int l,r,id,kuai;
}q[50004];

int ans[50004];
int num[50004]={0};

bool cmp(node b,node c)
{
    if(b.kuai!=c.kuai) return b.kuai<c.kuai;
    else if(b.kuai&1) return b.r<c.r;
    else return b.r>c.r;
}

int main()
{
    int n,m,k;
    cin>>n>>m>>k;

    int sizes=sqrt(n);
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=m;i++)
    {
        cin>>q[i].l>>q[i].r;
        q[i].id=i;
        q[i].kuai=(q[i].l-1)/sizes+1;
    }

    sort(q+1,q+m+1,cmp);

    int sum=0;
    for(int i=q[1].l;i<=q[1].r;i++) num[a[i]]++;// 预处理第一个区间
    for(int i=1;i<=k;i++) sum+=num[i]*num[i];
    ans[q[1].id]=sum;

    int l=q[1].l,r=q[1].r;
    for(int i=2;i<=m;i++)
    {
        while(r<q[i].r){r++;sum+=2*num[a[r]]+1;num[a[r]]++;}//挪步
        while(l>q[i].l){l--;sum+=2*num[a[l]]+1;num[a[l]]++;}
        while(l<q[i].l){sum-=2*num[a[l]]-1;num[a[l]]--;l++;}
        while(r>q[i].r){sum-=2*num[a[r]]-1;num[a[r]]--;r--;}
        ans[q[i].id]=sum;
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
    return 0;
}

标签:int,询问,id,num,P2709,kuai,排序,sum
From: https://www.cnblogs.com/pure4knowledge/p/18138206

相关文章

  • 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];......
  • 小美的排列询问(美团2024届秋招笔试第一场编程真题)
    题面核心思想模拟需要注意的是1~n只会出现一次所有nums[i]如果等于x(或y),下一位等不等于y(或x),就可以直接判断出结果了。代码importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){finallongMOD=(long)(1e9+7);......
  • Visual Studio Code 重置“不再询问”选项
    有一次使用VSCode重命名一个Python文件时,VSCode询问“扩展‘Python’希望通过移动此文件来进行重构更改”。当时没有多想,选中“不再提问”之后就点了“确定”。结果后来后悔,觉得在进行更改之前应该先检查一下更改的内容。于是想要重置这个“不再询问”的选项。结果始终没有......
  • 询问ChatGPT4,改造TodoList:把本地存储的localStorage修改成PHP+Redis
    这里照搬的是:免费极简设计网页版Todo  https://www.ricocc.com/todo/非常感谢原作者Rico。我很喜欢这个设计和风格,但是可惜只能本地存储,我又不想使用微软的TODO,登录倒无所谓,但是数据同步问题很大,实在头痛,所以放弃。我是菜鸟,只是刚好前段时间安装了Apache、PHP的一键安装包和......
  • php多进程引发mysql查询问题
    1、报错:Packetsoutoforder.Expected1received56.Packetsize=3159346开始配置my.cnf的max_allowed_packet=2G可是没什么卵用原因:个人判断是因在laravelmysql的连接是随着php销毁而销毁;所以会保持数据库的连接会话能重复使用所以要配置database.php  配置文件opt......
  • 洛谷题单指南-线性表-P3156 【深基15.例1】询问学号
    原题链接:https://www.luogu.com.cn/problem/P3156解题思路:简单的数组题,唯一需要注意的是读写的数据量比较大,输入输出最好用scanf、printf100分代码:#include<bits/stdc++.h>usingnamespacestd;constintN=2e6+5;inta[N],n,m;intmain(){scanf("%d%d",&......
  • Mybatis慢查询问题
    一、问题使用Mybatis查询数据库数据时发现,时间跨度大且数据量多的情况下,查询速度变得十分慢,120s以上然而将sql语句放至数据库中去查询时速度很快,只在10s左右带两个时间条件的情况下,最慢任意一个时间或者不带时间次之二、Mybatis中的sqlselecth.SBDW_ID,h.SBDW,count(dist......
  • 查询问题的语句使用
    排查问题关联查询太多SELECTt.idASnews_id,t.app_ids,t.rid,t.ds_code,t.ds_news_columns,t.media_source,t.title,t.src_publish_date,t.news_url,p.handle_status,t.publish_date,t.similar_news_id,p1.handle_statusAS's......
  • 列队中对询问离线排序后如何建立树状数组
    假设\(m=5\)(注意值存储前\(m-1\)个人)注意我们并没有在方框里面填上具体编号,因为从下文就可以知道这是无关紧要的假设我们删除了第二个人绿色方框是新进来的一个人,红色斜杠表示被删除掉的(但是在代码中我们不会真正的删除这一个位置)那么如果要删除这行中的第二个人,等价于删除......
  • 2023南海区区赛模拟(初中组)T1询问"好数"
    第1题   询问"好数" 查看测评数据信息如果整数a=b^2或者a =b^3,其中正整数b>=1,那么a就是"好数"。即:如果a是平方数或者立方数,那么a就是"好数"。现在有n个询问,第i个询问给出一个整数x[i],表示询问1至x[i]范围内有多少个"好数"。输入格式 第一行,一个整数n。1<=......