首页 > 代码库 > 校内训练0602 阿狸的统计学count
校内训练0602 阿狸的统计学count
【题目大意】
一个数列a[]有n个数，m次操作：
1 l r x：将a[l...r]都改成x
2 l r：求a[l...r]中数在当前区间出现率>=p%的数，为了方便做题，你可以输出k个数，满足k*p<=100，如果k个数中完全包含了答案，那么就判为正确。
1<=n,m,a[i],x<=150000, 20<=p<=100
【题解】
考虑之前做过的一个题：有一个数在区间中出现了>50%，求这个数：做法是我随便找出2个不同的数消去，到不能消的时候，最后剩下的那个数就是答案。
考虑出现了>=50%，这时候就不能按照上面那么做了，因为=50%的时候消去可能会全消完？那怎么做？随便找3个不同的数消去，等到消不动的时候，要么是还剩一个数，就是答案了，要么是还剩两个数，可能2个数都是答案（都出现了50%），或者其中1个数是答案。
下面的记号：[x]表示x的整数部分。
考虑推广？有一个数在区间中出现了>=p%，我随便找[100/p]+1个不同的数消去，最后剩下[100/p]个数，满足题目要求，且这一定包含答案集合。
考虑用线段树来维护这个序列：
这棵线段树的每个节点存着小于等于[100/p]个数及他们出现次数，代表我这个区间消剩下的数。
考虑合并两个区间，设节点为a和b，可以暴力合并。
假装a的答案就是答案，考虑用b的每一个答案来更新：
如果a没有[100/p]个数那么直接把b的这个答案装进去；
如果a有这个数，显然可以把答案合并。
否则，找出a中出现次数最小的数，设其出现次数为times，b的这个答案的出现次数times‘。
如果times<times‘，显然把b的这个答案替换a中出现次数最小的数，然后就可以把a中的所有数的出现次数减去times（同时消去times次[100/p]+1个数）
否则，显然保留a中的那个数更优，a中的所有数的出现次数减去times‘（同时消去times‘次[100/p]+1个数）
很明显上述过程不可能造成某个数出现次数变为负数，所以均合法。
然后就支持区间合并了，用线段树来维护即可。
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 150000 + 10, N = 7; const int mod = 1e9+7; # define RG register # define ST static int n, m, p, A[M], Max; struct node { int p[N], t[N], n; friend node operator + (node a, node b) { node ret; ret.n = a.n; for (int i=1; i<=ret.n; ++i) ret.p[i] = a.p[i], ret.t[i] = a.t[i]; for (int i=1; i<=b.n; ++i) { bool ok = 0; for (int j=1; j<=ret.n; ++j) { if(ret.p[j] == b.p[i]) { ret.t[j] += b.t[i]; ok = 1; break; } } if(ok) continue; if(ret.n < Max) { ++ret.n; ret.p[ret.n] = b.p[i], ret.t[ret.n] = b.t[i]; continue; } int pos = 1; for (int j=2; j<=ret.n; ++j) if(ret.t[j] < ret.t[pos]) pos = j; if(ret.t[pos] >= b.t[i]) { for (int j=1; j<=ret.n; ++j) ret.t[j] -= b.t[i]; } else { int times = ret.t[pos]; ret.p[pos] = b.p[i]; ret.t[pos] = b.t[i]; for (int j=1; j<=ret.n; ++j) ret.t[j] -= times; } } return ret; } }; struct SMT { node w[M * 4]; int tag[M * 4]; # define ls (x<<1) # define rs (x<<1|1) inline void pushtag(int x, int d, int l, int r) { if(!x) return; w[x].n = 1; w[x].p[1] = d; w[x].t[1] = r-l+1; tag[x] = d; } inline void down(int x, int l, int r) { if(!x) return ; if(tag[x] == 0) return; int mid = l+r>>1; pushtag(ls, tag[x], l, mid); pushtag(rs, tag[x], mid+1, r); tag[x] = 0; } inline void edt(int x, int l, int r, int L, int R, int d) { if(L <= l && r <= R) { pushtag(x, d, l, r); return ; } down(x, l, r); int mid = l+r>>1; if(L <= mid) edt(ls, l, mid, L, R, d); if(R > mid) edt(rs, mid+1, r, L, R, d); w[x] = w[ls] + w[rs]; } inline node query(int x, int l, int r, int L, int R) { if(L <= l && r <= R) return w[x]; down(x, l, r); int mid = l+r>>1; if(R <= mid) return query(ls, l, mid, L, R); else if(L > mid) return query(rs, mid+1, r, L, R); else return query(ls, l, mid, L, mid) + query(rs, mid+1, r, mid+1, R); } }T; int main() { freopen("count.in", "r", stdin); freopen("count.out", "w", stdout); cin >> n >> m >> p; Max = 100/p; for (int i=1; i<=n; ++i) { scanf("%d", &A[i]); T.edt(1, 1, n, i, i, A[i]); } int op, l, r, x; node t; while(m--) { scanf("%d%d%d", &op, &l, &r); if(op == 1) { scanf("%d", &x); T.edt(1, 1, n, l, r, x); } else { t = T.query(1, 1, n, l, r); printf("%d", t.n); for (int i=1; i<=t.n; ++i) printf(" %d", t.p[i]); puts(""); } } return 0; }
校内训练0602 阿狸的统计学count