bzoj 2038 小z的袜子 莫队

时间:2022-09-09 11:29:49

莫队大法好,入坑保平安

只要能O(1)或O(log)转移,离线莫队貌似真的无敌。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 50005
using namespace std;
int n,m,nn,tot,c[N],be[N],num[N];
struct Query{
int id,l,r;
long long son,mom;
}qr[N];
bool cmp(Query a,Query b){
if(be[a.l]==be[b.l]&&a.r==b.r)
return a.l<b.l;
if(be[a.l]==be[b.l]) return a.r<b.r;
return be[a.l]<be[b.l];
}
bool com(Query a,Query b){
return a.id<b.id;
}
long long ans;
void work(int x,int y){
ans-=num[c[x]]*num[c[x]];
num[c[x]]+=y;
ans+=num[c[x]]*num[c[x]];
}
long long gcd(long long x,long long y){
return y==0?x:gcd(y,x%y);
}
int main()
{
scanf("%d%d",&n,&m);
nn=(int)sqrt(n);
for(int i=1;i<=n;i++){
scanf("%d",&c[i]);
be[i]=(i-1)/nn+1;
} tot=be[n];
for(int i=1;i<=m;i++){
qr[i].id=i;
scanf("%d%d",&qr[i].l,&qr[i].r);
}
sort(qr+1,qr+m+1,cmp);
int l=1,r=0;
for(int i=1;i<=m;i++){
qr[i].mom=(long long)(qr[i].r-qr[i].l+1)*(qr[i].r-qr[i].l);
while(l<qr[i].l) work(l++,-1);
while(l>qr[i].l) work(--l,1);
while(r<qr[i].r) work(++r,1);
while(r>qr[i].r) work(r--,-1);
qr[i].son=(long long)ans-(qr[i].r-qr[i].l+1);
if(qr[i].son==0) qr[i].mom=1;
else{
long long gg=gcd(qr[i].son,qr[i].mom);
qr[i].son/=gg; qr[i].mom/=gg;
}
}
sort(qr+1,qr+m+1,com);
for(int i=1;i<=m;i++)
printf("%lld/%lld\n",qr[i].son,qr[i].mom);
return 0;
}

bzoj 2038 小z的袜子 莫队的更多相关文章

  1. BZOJ 2038 小z的袜子 &amp&semi; 莫队算法&lpar;不就是个暴力么&period;&period;&rpar;

    题意: 给一段序列,询问一个区间,求出区间中.....woc! 贴原题! 作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿.终于有一天,小Z再也无法忍受这恼人的找袜子过 ...

  2. bzoj 2038 小z的袜子 莫队例题

    莫队,利用可以快速地通过一个问题的答案得到另一问题的答案这一特性,合理地组织问题的求解顺序,将已解决的问题帮助解决当前问题,来优化时间复杂度. 典型用法:处理静态(无修改)离线区间查询问题. 线段树也 ...

  3. bzoj 2038 小Z的袜子 莫队算法

    题意 给你一个长度序列,有多组询问,每次询问(l,r)任选两个数相同的概率.n <= 50000,数小于等于n. 莫队算法裸题. 莫队算法:将序列分为根号n段,将询问排序,以L所在的块为第一关键 ...

  4. bzoj 2308 小Z的袜子&lpar;莫队算法&rpar;

    小Z的袜子 [题目链接]小Z的袜子 [题目类型]莫队算法 &题解: 莫队算法第一题吧,建议先看这个理解算法,之后在参考这个就可以写出简洁的代码 我的比第2个少了一次sort,他的跑了1600m ...

  5. 小Z的袜子 &amp&semi; 莫队

    莫队学习 & 小Z的袜子 引入 莫队 由莫涛巨佬提出,是一种离线算法 运用广泛 可以解决广大的离线区间询问题 莫队的历史 早在mt巨佬提出莫队之前 类似莫队的算法和莫队的思想已在Codefor ...

  6. BZOJ 2038 &lbrack;2009国家集训队&rsqb;小Z的袜子 莫队

    2038: [2009国家集训队]小Z的袜子(hose) 题目连接: http://www.lydsy.com/JudgeOnline/problem.php?id=2038 Descriptionw ...

  7. (原创)BZOJ 2038 小Z的袜子&lpar;hose&rpar; 莫队入门题&plus;分块

    I - 小Z的袜子(hose) 作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿.终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命…… 具体来说,小Z ...

  8. BZOJ - 2038 小Z的袜子&lpar;普通莫队&rpar;

    题目链接:小Z的袜子 题意:$n$只袜子,$m$个询问,每次回答有多大概率在$[L,R]$区间内抽到两只颜色相同的袜子 思路:普通莫队,如果两个询问左端点在一个块内,则按询问右端点排序,否则按照所在块 ...

  9. bzoj 2038 小Z的袜子&lpar;hose&rpar;(莫队算法)

    2038: [2009国家集训队]小Z的袜子(hose) Time Limit: 20 Sec  Memory Limit: 259 MBSubmit: 11542  Solved: 5166[Sub ...

随机推荐

  1. JSON相关(一):JSON&period;parse&lpar;&rpar;和JSON&period;stringify&lpar;&rpar;

    parse用于从一个字符串中解析出json对象,如 var str = '{"name":"huangxiaojian","age":&qu ...

  2. spark与storm的对比

    对比点 Storm Spark Streaming 实时计算模型 纯实时,来一条数据,处理一条数据 准实时,对一个时间段内的数据收集起来,作为一个RDD,再处理 实时计算延迟度 毫秒级 秒级 吞吐量 ...

  3. 【ASP&period;NET MVC 学习笔记】- 20 ASP&period;NET Web API

    本文参考:http://www.cnblogs.com/willick/p/3441432.html 1.ASP.NET Web API(本文简称Web API),是基于ASP.NET平台构建REST ...

  4. &lbrack;再寄小读者之数学篇&rsqb;&lpar;2014-11-02 Herglotz&&num;39&semi; trick&rpar;

    设 $f$ 是 $\bbR$ 上周期为 $1$ 的连续可微函数, 满足 $$\bee\label{141102_f} f(x)+f\sex{x+\frac{1}{2}}=f(2x),\quad\for ...

  5. MessengerJS

    跨文档通信解决方案 Since modern browsers have native cross-document communication method(the PostMeessage API ...

  6. RAMDISK 内存盘工具推荐

    好了直接推荐, 1.魔方内存盘  使用方便 ,但是关机后消失.绿色 2.Primo Ramdisk Ultimate Edition5.5 3.GiliSoft RAMDisk 4.QSoft RAM ...

  7. Express框架之Jade模板引擎使用

    日期:2018-7-8  十月梦想  node.js  浏览:2952次  评论:0条 前段时间讲说了ejs模板引擎,提到了jade的效率等等问题!今天在这里简单提一下jade的使用方式!结合expr ...

  8. C&num;中saveFileDialog&lpar;另存为&rpar;保存图片文件

    弹出另存为提示框保存图片文件: //用户*选择指定路径保存文件            SaveFileDialog savedialog = new SaveFileDialog();        ...

  9. vb&period;net 水晶報表CrystalReport 動態設定資料庫來源

    沒有出現CrystalReportViewer時,須安裝CRforVS_13_0. 新增1個數據集,新增1個數據表,添加二列,列名要和資料庫名一樣. 修改目標Framework 修改app.confi ...

  10. 11&sol;1&sol;2018模拟 Max

    题面 也就是说, 随机序列RMQ.(\(n \le 8388608\), \(m \le 8*10^6\)) 解法 我写了笛卡尔树+tarjan 然而听神仙说, 因为数据随机, 建完树暴力找lca就行 ...