zoto【来源：2021杭电多校第一场的第10题】
题目：
Problem DescriptionYou are given an array fx.
For each i(1<=i<=n) , we use a point (i,fx[i]) in XoY coordinate plane to described it.
You are asked to answer m queries, in each query there will be a rectangle and you need to count how many different y-cooordinate (of the points mentioned above) in the queried rectangle.InputThe first line contains an integer T(1<=T<=5) representing the number of test cases.
For each test case , there are two integers n,m(1<=n<=100000,1<=m<=100000) in the first line.
Then one line contains n integers fx[i](0<=fx[i]<=100000)
Each of the next m lines contain four integers x0,y0,x1,y1(1<=x0<=x1<=n,0<=y0<=y1<=100000) which means matrix's lower-leftmost cell is (x0,y0) and upper-rightest cell is (x1,y1).OutputFor each test case print a single integer in a new line.Sample Input1 4 2 1 0 3 1 1 0 4 3 1 0 4 2Sample Output3 2Source
分析：
> 题目：
> T组测试数据， T大小为5：
> 给定n个坐标，横坐标为从1到n，对应纵坐标为fx[i]，共有m此询问，其中n，m，fx大小都是1e5
> 每次询问，查询一个以(x0,y0)为左下角,以(x1,y1)为右上角的矩形面积内，有多少个不同的fx
> 解决：
> T是T，m是1e5,那么，我们每次的查询操作的时间复杂度需要降到O(logn)才能合法，而且，只有查询没有修改，基础莫队便可以解决次题。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, m, len;
int w[N], cnt[N], sum[N], ans[N];
struct Query{
int l, r, L, R, id;
}q[N];
int get(int x)
{
return x / len;
}
bool cmp(const Query& a, const Query& b)
{
int x = get(a.l), y = get(b.l);
if (x != y) return x < y;
return a.r < b.r;
// if (x == y) return a.r < b.r;
// return (x & 1) ? x > y : x < y;
}
void add(int x)
{
// printf("del: x = %d, cnt[x] = %d
", x, cnt[x]);
//sum计算块内的节点数量，我们对y轴分块，计算的是fx的分块内的值
if (!cnt[x]) sum[get(x)] ++;
cnt[x] ++;
}
void del(int x)
{
// printf("del: x = %d, cnt[x] = %d
", x, cnt[x]);
cnt[x] --;
if (!cnt[x]) sum[get(x)] --;
}
int calc(int y)
{
//计算y轴，从0到y的个数
int res = 0;
//sum代表y轴分块val的数量，res先求的是前缀和
for (int i = 0; i < get(y); i ++ ) res += sum[i];
//最上面的一点，这些不再整块内，暴力计算
for (int i = get(y) * len; i <= y; i ++ ) res += (cnt[i] >= 1);
return res;
}
void solve()
{
memset(cnt, 0, sizeof cnt);
memset(sum, 0, sizeof sum);
scanf("%d%d", &n, &m);
// len = sqrt(n);
len = 131;
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
for (int i = 0; i < m; i ++ )
{
int l, L, r, R; scanf("%d%d%d%d", &l, &L, &r, &R);
q[i] = {l, r, L, R, i};
}
sort(q, q + m, cmp);
for (int i = 0, l = 1, r = 0; i < m; i ++ )
{
// printf("q[i].l = %d, bottom = %d, q[i].r = %d, top = %d
", q[i].l, q[i].L, q[i].r, q[i].R);
// printf("del l ++
");
while (l < q[i].l) del(w[l ++ ]);
// printf("add -- l
");
while (l > q[i].l) add(w[-- l ]);
// printf("add ++ r
");
while (r < q[i].r) add(w[++ r ]);
// printf("del r --
");
while (r > q[i].r) del(w[r -- ]);
ans[q[i].id] = calc(q[i].R) - calc(q[i].L - 1);
}
for (int i = 0; i < m; i ++ ) printf("%d
", ans[i]);
}
int main()
{
int T = 1;
cin >> T;
while (T -- )
{
solve();
}
return 0;
}
题目：
HH 有一串由各种漂亮的贝壳组成的项链。
HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。
HH 不断地收集新的贝壳，因此他的项链变得越来越长。
有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？
这个问题很难回答，因为项链实在是太长了。
于是，他只好求助睿智的你，来解决这个问题。
输入格式
第一行：一个整数 NN，表示项链的长度。
第二行：NN 个整数，表示依次表示项链中贝壳的编号（编号为 00 到 10000001000000 之间的整数）。
第三行：一个整数 MM，表示 HH 询问的个数。
接下来 MM 行：每行两个整数，LL 和 RR，表示询问的区间。
输出格式
MM 行，每行一个整数，依次表示询问对应的答案。
数据范围
1≤N≤500001≤N≤50000,
1≤M≤2×1051≤M≤2×105,
1≤L≤R≤N1≤L≤R≤N输入样例：
6 1 2 3 4 3 5 3 1 2 3 5 2 6输出样例：
2 2 4
分析：
题目：
给定一个长度为n的序列w，n长度为5e4，w大小为5e4，对此序列进行m次查询，m大小为2e5，每次查询询问一个区间内有多少个不同的数字。
解决：
这时离线询问操作，可以使用基础莫队解决此题。时间复杂度为O(nsqrt(n))
莫队算法将
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 50005, M = 200005, S = 1000010;
int n, m, T, a[N];
struct Q{
int l, r, x, y, i;
inline Q() {}
inline Q(int l, int r, int i) : l(l), r(r), i(i) {x = l / T, y = r;}
inline friend bool operator< (const Q &a, const Q &b){
return a.x == b.x ? (a.x & 1) ? a.y < b.y : a.y > b.y : a.x < b.x;
}
}q[M];
int ans[M], cnt[S];
void add(int x, int& now)
{
if (!cnt[x]) now ++;
cnt[x] ++;
}
void del(int x, int& now)
{
cnt[x] --;
if (!cnt[x]) now --;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
scanf("%d", &m);
T = sqrt((double)n * n / m);
for (int i = 0; i < m; i ++ )
{
int l, r; scanf("%d%d", &l, &r);
q[i] = {l, r, i};
}
sort(q, q + m);
for (int i = 0; i < m; i ++ )
printf("[l = %d, r = %d]
", q[i].l, q[i].r);
for (int i = 0, l = 1, r = 0, now = 0; i < m; i ++ )
{
while (l > q[i].l) add(a[ -- l], now);
while (l < q[i].l) del(a[ l ++], now);
while (r > q[i].r) del(a[ r --], now);
while (r < q[i].r) add(a[ ++ i], now);
ans[q[i].i] = now;
}
for (int i = 0; i < m; i ++ ) printf("%d
", ans[i]);
return 0;
}
题目描述
upd on 2020.6.10 ：更新了时限。
作为一个生活散漫的人，小 Z 每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小 Z 再也无法忍受这恼人的找袜子过程，于是他决定听天由命……
具体来说，小 Z 把这 NN 只袜子从 11 到 NN 编号，然后从编号 LL 到 RR (LL 尽管小 Z 并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小 Z，他有多大的概率抽到两只颜色相同的袜子。当然，小 Z 希望这个概率尽量高，所以他可能会询问多个 (L,R)(L,R) 以方便自己选择。
然而数据中有 L=RL=R 的情况，请特判这种情况，输出
0/1。输入格式
输入文件第一行包含两个正整数 NN 和 MM。NN 为袜子的数量，MM 为小 Z 所提的询问的数量。接下来一行包含 NN 个正整数 C_iCi，其中 C_iCi 表示第 ii 只袜子的颜色，相同的颜色用相同的数字表示。再接下来 MM 行，每行两个正整数 L, RL,R 表示一个询问。
输出格式
包含 MM 行，对于每个询问在一行中输出分数 A/BA/B 表示从该询问的区间 [L,R][L,R] 中随机抽出两只袜子颜色相同的概率。若该概率为 00 则输出
0/1，否则输出的 A/BA/B 必须为最简分数。（详见样例）输入输出样例
输入 #16 4 1 2 3 3 3 2 2 6 1 3 3 5 1 6输出 #12/5 0/1 1/1 4/15说明/提示
30% 的数据中，N,M≤5000；
60% 的数据中，N,M≤25000；
100% 的数据中，N,M≤50000，1≤L<R≤N，Ci≤N。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 50005;
int n, m, len;
int w[N];
int cnt[N];
struct Query{
int l, r, id;
}q[N];
struct Answer{
int x, y;
}ans[N], res;
inline int rd()
{
int x = 0, f = 0; char c = getchar();
while (!isdigit(c)) if (c == '-') f = 1, c = getchar();
while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
inline int get(int x)
{
return x / len;
}
inline bool cmp(const Query& a, const Query& b)
{
int x = get(a.l), y = get(b.l);
if (x == y) return (x & 1) ? a.r < b.r : a.r > b.r;
return x < y;
}
inline void add(int x)
{
cnt[x] ++;
if (cnt[x] > 1) res.x += cnt[x] * (cnt[x] - 1) - (cnt[x] - 1) * (cnt[x] - 2);
}
inline void del(int x)
{
cnt[x] --;
if (cnt[x] > 0) res.x -= cnt[x] * (cnt[x] + 1) - cnt[x] * (cnt[x] - 1);
}
inline int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
signed main()
{
// n = rd(), m = rd();
scanf("%lld%lld", &n, &m);
len = sqrt(n);
for (int i = 1; i <= n; i ++ ) scanf("%lld", &w[i]);
// w[i] = rd();
for (int i = 0; i < m; i ++ )
{
int l, r;
scanf("%lld%lld", &l, &r);
// l = rd(), r = rd();
q[i] = {l, r, i};
}
sort(q, q + m, cmp);
// cout << "-------------" << endl;
for (int i = 0, l = 1, r = 0; i < m; i ++ )
{
if (q[i].l == q[i].r)
{
ans[q[i].id] = {0, 1};
continue;
}
while (l < q[i].l) del(w[l ++ ]);
while (l > q[i].l) add(w[-- l ]);
while (r < q[i].r) add(w[++ r ]);
while (r > q[i].r) del(w[r -- ]);
res.y = (q[i].r - q[i].l + 1) * (q[i].r - q[i].l);
// printf("%lld
", res.y);
int x = res.x, y = res.y;
int d = gcd(x, y);
ans[q[i].id] = {x / d, y / d};
// printf("x = %lld, y = %lld, gcd = %lld
", x, y, d);
}
for (int i = 0; i < m; i ++ ) printf("%lld/%lld
", ans[i].x, ans[i].y);
return 0;
}
题目：
题目描述
小B 有一个长为 nn 的整数序列 aa，值域为 [1,k]。
他一共有 m 个询问，每个询问给定一个区间 [l,r]，求：i=1∑kci2
其中 ci 表示数字 i在 [l,r] 中的出现次数。
小B请你帮助他回答询问。输入格式
第一行三个整数 n,m,k。
第二行 n 个整数，表示 小B 的序列。
接下来的 m 行，每行两个整数l,r。
输出格式
输出 m 行，每行一个整数，对应一个询问的答案。
输入输出样例
输入6 4 3 1 3 2 1 1 3 1 4 2 6 3 5 5 6输出 #16 9 5 2说明/提示
【数据范围】
对于100% 的数据，1≤n,m,k≤5×104。
分析：
基础莫队
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 50005;
int n, m, k, len;
int w[N];
int cnt[N], ans[N];
struct Query{
int l, r, id;
}q[N];
inline int rd()
{
int x = 0, f = 0; char c = getchar();
while (!isdigit(c)) if (c == '-') f = 1, c = getchar();
while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
int get(int x)
{
return x / len;
}
bool cmp(const Query& a, const Query& b)
{
int x = get(a.l), y = get(b.l);
if (x == y) return (x & 1) ? a.r < b.r : a.r > b.r;
return x < y;
}
void add(int x, int& res)
{
// if (!cnt[x]) res ++;
// else res += cnt[x] << 1 | 1;
res += cnt[x] << 1 | 1;
cnt[x] ++;
}
void del(int x, int& res)
{
// if (cnt[x]) res += 1 - 2 * cnt[x];
res -= 2 * cnt[x] - 1;
cnt[x] --;
}
int main()
{
n = rd(), m = rd(), k = rd();
len = sqrt(n);
for (int i = 1; i <= n; i ++ ) w[i] = rd();
for (int i = 0; i < m; i ++ )
{
int l, r;
l = rd(), r = rd();
// cout << l << " " << r << endl;
q[i] = {l, r, i};
}
sort(q, q + m, cmp);
// for (int i = 0; i < m; i ++ )
// printf("q[i].l = %d, q[i].r = %d
", q[i].l, q[i].r);
for (int i = 0, l = 1, r = 0, res = 0; i < m; i ++ )
{
while (l < q[i].l) del(w[l ++ ], res);
while (l > q[i].l) add(w[-- l ], res);
while (r < q[i].r) add(w[++ r ], res);
while (r > q[i].r) del(w[r -- ], res);
// printf("id = %d, L = %d, R = %d, res = %d
", q[i].id, q[i].l, q[i].r, res);
ans[q[i].id] = res;
}
for (int i = 0; i < m; i ++ ) printf("%d
", ans[i]);
return 0;
}