莫队算法
这个算法的思想比较简单,我们在做RMQ类问题时,有多次询问的那种,其实在这些询问中有很多都是问的同一段区间,即有的区间被询问的多次,所以我们对询问进行一个排序,假设上次询问我们得到了区间[l,r]
的值,那本次询问跟上次相比,多的我们加上即可,少的减掉即可。然后用到分块思想。
所以,比较重要的就是这个排序和每次询问与上次之间的转化。
排序:这里用到分块,根据区间左界所在的块的序号从小到大排,若在同一区间,则根据序号的奇偶性,奇则根据右边界从小到大,偶则根据右边界从大到小
与上次的转化:通过四个while来实现。
1 2 3 4
| while(l < ask[i].l) del(c[l++]); while(l > ask[i].l) add(c[--l]); while(r < ask[i].r) add(c[++r]); while(r > ask[i].r) del(c[r--]);
|
分析:
弄明白那个排列组合和概率就基本模板题惹
AC代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
| #include <bits/stdc++.h>
using namespace std; typedef long long ll;
int n, m, len; int ar[50050]; struct node { ll l, r, id; }ask[50050]; struct node1 { ll x, y; }ans[50050], now; int pos[50050]; ll cnt[50050];
bool cmp(node a, node b) { if(pos[a.l] == pos[b.l]) { if(pos[a.l] & 1) return a.r < b.r; else return a.r > b.r; } else return pos[a.l] < pos[b.l]; }
ll gcd(ll x, ll y) { return !y ? x : gcd(y, x % y); }
void add(int x) { ++cnt[x]; if(cnt[x] > 1) now.x = now.x + cnt[x] * (cnt[x] - 1) - (cnt[x] - 1) * (cnt[x] - 2); }
void del(int x) { --cnt[x]; if(cnt[x] > 0) now.x = now.x + cnt[x] * (cnt[x] - 1) - (cnt[x] + 1) * cnt[x]; }
void divgcd(ll x, ll y, int id) { if(!x) x = 0, y = 1; else { ll g = gcd(x, y); x /= g; y /= g; } ans[id].x = x; ans[id].y = y; }
int main() { scanf("%d%d", &n, &m); len = sqrt(n + 0.5); for(int i = 1; i <= n; ++i) { scanf("%d", &ar[i]); pos[i] = (i - 1) / len + 1; } for(int i = 1; i <= m; ++i) { scanf("%lld%lld", &ask[i].l, &ask[i].r); ask[i].id = i; } sort(ask + 1, ask + m + 1, cmp); for(int i = ask[1].l; i <= ask[1].r; ++i) add(ar[i]); now.y = (ask[1].r - ask[1].l + 1) * (ask[1].r - ask[1].l); divgcd(now.x, now.y, ask[1].id); int l = ask[1].l, r = ask[1].r; for(int i = 2; i <= m; ++i) { while(l < ask[i].l) del(ar[l++]); while(l > ask[i].l) add(ar[--l]); while(r > ask[i].r) del(ar[r--]); while(r < ask[i].r) add(ar[++r]); now.y = (ask[i].r - ask[i].l + 1) * (ask[i].r - ask[i].l); divgcd(now.x, now.y, ask[i].id); }
for(int i = 1; i <= m; ++i) printf("%lld/%lld\n", ans[i].x, ans[i].y); return 0; }
|
题目描述
墨墨购买了一套 $N$ 支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会向你发布如下指令:
$Q\ L\ R$ 代表询问你从第 $L$ 支画笔到第 $R$ 支画笔中共有几种不同颜色的画笔。
$R\ P\ C$ 把第 $P$ 支画笔替换为颜色 $C$。
为了满足墨墨的要求,你知道你需要干什么了吗?
输入格式
第 $1$ 行两个整数 $N$,$M$,分别代表初始画笔的数量以及墨墨会做的事情的个数。
第 $2$ 行 $N$ 个整数,分别代表初始画笔排中第 $i$ 支画笔的颜色。
第 $3$ 行到第 $2+M$ 行,每行分别代表墨墨会做的一件事情,格式见题干部分。
输出格式
对于每一个 Query 的询问,你需要在对应的行中给出一个数字,代表第 $L$ 支画笔到第 $R$ 支画笔中共有几种不同颜色的画笔。
样例输入 #1
1 2 3 4 5 6 7
| 6 5 1 2 3 4 5 5 Q 1 4 Q 2 6 R 1 2 Q 1 4 Q 2 6
|
样例输出 #1
提示
对于30%的数据,$n,m \leq 10000$
对于60%的数据,$n,m \leq 50000$
对于所有数据,$n,m \leq 133333$
所有的输入数据中出现的所有整数均大于等于 $1$ 且不超过 $10^6$。
本题可能轻微卡常数。
分析:
首先考虑普通的莫队,这个题带了修改,那么我们依旧按照莫队来做,我们需要记录一下当前这次询问经过了几次修改,然后跟上一次比较,那就跟普通莫队一样了,只是4个while要变成6个while了。这是大体方向,然后还有一点点细节。
1.分块大小:sz = pow(n, 0.666);
2.排序:第一关键字是区间左界所在的块的序号,第二关键字是区间右界所在的块的序号,第三关键字是这次询问经过了几次修改,均按照从小到大排。
3.对于修改,如果碰到某次修改需要操作,那么一定需要做一个交换swap(ar[qr[t].l], qr[t].r);
,交换完之后,ar数组得到了修改,然后这次修改指令也得到了修改,因为后面再操作这次修改的时候就是改回来了,所以一个交换解决。另外,需要判断这次修改是不是发生在查询的区间内,是则需要做一些add和del。
4.维护的容器,以及作用
cnt[i] : 数字i在当前区间出现的次数
ar[i]; 原数组在位置i应该是的值
qq[i] 表示第i次询问的左右边界已经发生在几次修改之后,id代表修改序号
qr[i] 表示第i次修改是将l位置的数字改成r
AC代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
| #include <bits/stdc++.h>
using namespace std;
int sum; int cnt[1000050]; int ar[10050]; int ans[10050]; int cntq, cntr; int n, m, sz; char op[5]; int l, r;
struct node { int l, r, t, id; }qq[10050], qr[10050];
inline bool cmp(const node &a, const node &b) { if(a.l / sz == b.l / sz) { if(a.r / sz == b.r / sz) return a.t < b.t; else return a.r < b.r; } else return a.l < b.l; }
inline void add(int x) { sum += !cnt[x]++; }
inline void del(int x) { sum -= !--cnt[x]; }
inline void upd(int x, int t) { if(qq[x].l <= qr[t].l && qr[t].l <= qq[x].r) { del(ar[qr[t].l]); add(qr[t].r); } swap(ar[qr[t].l], qr[t].r); }
int main() { scanf("%d%d", &n, &m); sz = pow(n, 0.666); for(int i = 1; i <= n; ++i) scanf("%d", &ar[i]); for(int i = 1; i <= m; ++i) { scanf("%s%d%d", op, &l, &r); if(op[0] == 'Q') { ++cntq; qq[cntq].id = cntq; qq[cntq].l = l; qq[cntq].r = r; qq[cntq].t = cntr; } else { ++cntr; qr[cntr].l = l; qr[cntr].r = r; } } sort(qq + 1, qq + cntq + 1, cmp); int lcur = 1, rcur = 0, tcur = 0; for(int i = 1; i <= cntq; ++i) { while(lcur > qq[i].l) add(ar[--lcur]); while(lcur < qq[i].l) del(ar[lcur++]); while(rcur > qq[i].r) del(ar[rcur--]); while(rcur < qq[i].r) add(ar[++rcur]); while(tcur < qq[i].t) upd(i, ++tcur); while(tcur > qq[i].t) upd(i, tcur--); ans[qq[i].id] = sum; } for(int i = 1; i <= cntq; ++i) printf("%d\n", ans[i]); return 0; }
|