220726 T2 Multisets （思维）

题目描述

我们说一个可重集ＡＡ比可重集 BB 小，当且仅当对于两个可重集中出现次数不同的最小元素 xx ，元素 xx 在 AA 中出现次数更多。

例如，可重集 {1,2,3}1,2,3 就比可重集 {1,3,3,5}1,3,3,5 小，类似的，{1,1,4,4}1,1,4,4 小于 {1,1,4}1,1,4 。

小 CC 给你了一个长度为 nn 的正整数序列 SS 。考虑 SS 的所有连续子序列，可以把它们分别看做一个可重集（也就是说，恰好存在着 \frac{n(n+1)}{2}2n(n+1) 个可重集）。

小ＣＣ想知道第 kk 小可重集，想请你帮她找到答案。

输入格式

输入共两行。

第一行包含两个整数 n，kn，k 。

接下来的一行包含序列 S_iSi 。

输出格式

输出共一行。

输出你找到的可重集，请输出可重集排序后的结果。

可以用类似整体二分的缩小答案集合的思想，对于每个数确定在答案中应该出现几次。使用set来存答案的集合。

  1 #include <bits/stdc++.h>

  2 #define N 100005

  3 //#define loveGsy

  4 using namespace std;

  5 int n, k, s[N], hv[N], ans[N];

  6 vector<int> pos[N];//存一个数出现在哪些位置

  7 struct node {

  8     int ll, lr, rl, rr;

  9     node() {}

 10     node(int a, int b, int c, int d) {ll = a, lr = b, rl = c, rr = d;}

 11     friend bool operator < (node a, node b) {

 12         return a.ll < b.ll;

 13     }

 14 };

 15 set<node> st, hc;

 16

 17 int query(int p, int num) {

 18     int l = 1, r = l + num - 1, js = 0, ll, lr, rl, rr, LL, LR, RL, RR;

 19     set<node>::iterator zz;

 20     while (r + 1 < pos[p].size()) {

 21         LL = pos[p][l - 1] + 1;

 22         LR = pos[p][l];

 23         RL = pos[p][r];

 24         RR = pos[p][r + 1] - 1;

 25         zz = st.upper_bound(node(LR, 0, 0, 0));

 26         while (zz != st.begin()) {

 27             --zz;

 28             if ((*zz).lr < LL) break;

 29             ll = max((*zz).ll, LL);

 30             lr = min((*zz).lr, LR);

 31             rl = max((*zz).rl, RL);

 32             rr = min((*zz).rr, RR);

 33             if (lr >= ll && rr >= rl)

 34                 js += (lr - ll + 1) * (rr - rl + 1);

 35         }

 36         ++l, ++r;

 37     }

 38     return js;

 39 }

 40

 41 void getnum(int p) {

 42     ans[p] = hv[p];

 43     while (ans[p]) {

 44         int hc = query(p, ans[p]);//查询st集合内有多少区间满足有ans[p]个p

 45         if (hc >= k) return ;

 46         --ans[p];

 47         k -= hc;//类似整体二分板题的答案分拆，缩小答案集合

 48     }

 49 }

 50

 51 void merge(int p, int num) {

 52     int l = 1, r = l + num - 1, js = 0, ll, lr, rl, rr, LL, LR, RL, RR;

 53     set<node>::iterator zz;

 54     while (r + 1 < pos[p].size()) {

 55         LL = pos[p][l-1] + 1;

 56         LR = pos[p][l];

 57         RL = pos[p][r];

 58         RR = pos[p][r + 1] - 1;

 59         zz = st.upper_bound(node(LR, 0, 0, 0));

 60         while (zz != st.begin()) {

 61             --zz;

 62             if((*zz).lr < LL) break;

 63             ll = max((*zz).ll, LL);

 64             lr = min((*zz).lr, LR);

 65             rl = max((*zz).rl, RL);

 66             rr = min((*zz).rr, RR);//取交集

 67             if(lr >= ll && rr >= rl)

 68                 hc.insert(node(ll,lr,rl,rr));

 69         }

 70         ++l,++r;

 71     }

 72     st.clear();//清空原来的集合

 73     zz = hc.begin();

 74     while (zz != hc.end()) {

 75         st.insert((*zz));

 76         ++zz;

 77     }

 78     hc.clear();

 79 }

 80

 81 int main() {

 82 #ifdef loveGsy

 83     freopen("tree.in", "r", stdin);

 84     freopen("tree.out", "w", stdout);

 85 #endif

 86     scanf("%d %d", &n, &k);

 87     for (int i = 1; i <= n; i++) pos[i].push_back(0);//存边界条件

 88     for (int i = 1; i <= n; i++) {

 89         scanf("%d", &s[i]);

 90         ++hv[s[i]];

 91         pos[s[i]].push_back(i);

 92     }

 93     for (int i = 1; i <= n; i++) pos[i].push_back(n + 1);

 94     st.insert(node(1, n, 1, n));//插入初始答案集合

 95     for (int i = 1; i <= n; i++) {//确定答案中每个数字应该出现几次

 96         if (hv[i]) {

 97             getnum(i);//确定答案中应该有ans[i]个i

 98             merge(i, ans[i]);//从st集合中筛选出含有ans[i]个i的集合

 99         }

100     }

101     for (int i = 1; i <= n; i++) {

102         for (int j = 1; j <= ans[i]; j++)

103         printf("%d ", i);

104     }

105     return 0;

106 }

巴特西

220726 T2 Multisets （思维）

题目描述

输入格式

输出格式

最新文章

热门文章