「国家集训队」小Z的袜子
2024-09-01 02:11:03
「国家集训队」小Z的袜子
传送门
莫队板子题。
注意计算答案的时候,由于分子分母都要除以2,所以可以直接约掉,这样在开桶算的时候也方便一些。
参考代码:
#include <algorithm>
#include <cstdio>
#include <cmath>
#define rg register
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
#define int long long
using namespace std;
template < class T > inline void read(T& s) {
s = 0; int f = 0; char c = getchar();
while ('0' > c || c > '9') f |= c == '-', c = getchar();
while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();
s = f ? -s : s;
}
const int _ = 50010;
int n, gap, m, c[_], pos[_], s[_], ans;
struct Ask { int l, r, id; } ask[_];
struct Ans { int a, b; } res[_];
inline bool cmp(const Ask& x, const Ask& y)
{ return pos[x.l] == pos[y.l] ? x.r < y.r : x.l < y.l; }
inline void update(int x, int v)
{ ans -= s[c[x]] * s[c[x]], s[c[x]] += v, ans += s[c[x]] * s[c[x]]; }
signed main() {
#ifndef ONLINE_JUDGE
file("cpp");
#endif
read(n), read(m), gap = sqrt(1.0 * n);
for (rg int i = 1; i <= n; ++i)
read(c[i]), pos[i] = (i - 1) / gap + 1;
for (rg int i = 1; i <= m; ++i)
read(ask[i].l), read(ask[i].r), ask[i].id = i;
sort(ask + 1, ask + 1 + m, cmp);
for (rg int i = 1, l = 1, r = 0; i <= m; ++i) {
while (l < ask[i].l) update(l++, -1);
while (l > ask[i].l) update(--l, 1);
while (r < ask[i].r) update(++r, 1);
while (r > ask[i].r) update(r--, -1);
int now = ask[i].id;
if (ask[i].l == ask[i].r) { res[now].a = 0, res[now].b = 1; continue; }
res[now].a = ans - (ask[i].r - ask[i].l + 1);
res[now].b = 1ll * (ask[i].r - ask[i].l + 1) * (ask[i].r - ask[i].l);
int g = __gcd(res[now].a, res[now].b);
res[now].a /= g, res[now].b /= g;
}
for (rg int i = 1; i <= m; ++i) printf("%lld/%lld\n", res[i].a, res[i].b);
return 0;
}
最新文章
- Base64编码
- SpringMVC后台接收list类型的数据的实现方式
- Xcode常用快捷键的使用
- mac iterm2快捷键
- SRF之权限控制
- IE中出现 ";Stack overflow at line"; 错误的解决方法
- 声明顺序 (Bootstrap 编码规范)
- Java Struts2 的请求处理流程详解
- Android端上传图片到后台,存储到数据库中 详细代码
- INNO setup 制作安装包
- XML学习教程
- centos7 安装远程桌面
- djongo:Django和MongoDB连接器
- webpack入门(二)what is webpack
- Java使用for循环输出菱形
- C++.sprintf
- (转) python学习笔记6--fraction
- java中string的replace和replace的区别
- python部分知识归纳
- 前端JS框架系列之requireJS基础学习
热门文章
- The Preliminary Contest for ICPC Asia Xuzhou 2019 K. Center
- qq音乐解析API
- FTD vs FMC
- Codeforces Round #601 (Div. 2)E(寻找质因子,DP)
- CDH搭建大数据集群(5.10.0)
- 移动端rem自适应方案
- python3+requests+BeautifulSoup+mysql爬取豆瓣电影top250
- Java日志介绍(1)-java.util.logging.Logger
- December 28th, Week 52nd Saturday, 2019
- git合并分支到master上面