牛客网多校第5场 H subseq 【树状数组+离散化】

学习博客：戳这里

题意：给n个数为a1~an，找到字典序第k小的序列，输出该序列所有数所在位置。

解题思路：先把所有序列预处理出来，方法是设一个数组为dp，dp[i]表示以i为开头的序列共有多少个。这样当k>dp[i]，则以i为开头的序列满足不了第k小，k-=dp[i]，继续往后找，知道找到k<=dp[i]，则把i记录在数组ans中，--k。--k的意思是去掉了我们所记录的ans这一条序列。此时若k==0，则说明已经找到答案，跳出循环输出即可，否则继续往下找，思路还算比较常规。

那么dp数组具体怎么预处理呢？因为是求以i为开头的序列，所以类似于求后缀和，比如此时我们已经有了2 3 4，此时要插入数字1，则对1的贡献有sum[2]+sum[3]+sum[4],即1分别可以接在2,3,4前面或者只有一个1，也就是树状数组中，1的贡献=getsum(1 + 1) + 1。（getsum()为后缀和）

这里注意两个坑点：一个是a1~an范围很大，必须要离散化。二是求和有可能会爆long long (这个是真的坑，所以当大于1e18的时候，令其等于1e18就行，因为k最大就是1e18嘛。

附本人ac代码：

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

 2 using namespace std;

 3 typedef long long ll;

 4 const ll maxn = 5e6 + 10;

 5 const ll inf = 1e18;

 6 ll a[maxn], c[maxn], dp[maxn], b[maxn], d[maxn];

 7 ll ans[maxn];

 8 ll n, k;

 9

10 ll lowbit(ll x)

11 {

12     return x&-x;

13 }

14 ll gsum(ll x)

15 {

16     ll ans = 0;

17     while(x <= n)

18     {

19         ans += c[x];

20         if(ans > inf) ans = inf;

21         x += lowbit(x);

22     }

23     return ans;

24 }

25 void updat(ll x, ll y)

26 {

27     while(x)

28     {

29         c[x] += y;

30         if(c[x] > inf) c[x] = inf;

31         x -= lowbit(x);

32     }

33 }

34 int main()

35 {

36

37     scanf("%lld %lld", &n, &k);

38     for(ll i = 1; i <= n; ++i)

39     {

40         scanf("%lld", &d[i]);

41         a[i] = d[i];

42     }

43     sort(a + 1, a + 1 + n);

44     for(ll i  = 1; i <= n; ++i)//离散化

45     {

46         b[i] = lower_bound(a + 1, a + 1 + n, d[i]) - a;

47     }

48     dp[n] = 1;

49     updat(b[n], 1);

50     for(ll u  = n - 1; u >= 1; --u)

51     {

52         dp[u] = gsum(b[u] + 1) + 1;//这一步容易写错，之前我没想到会有多个相同的数，所以一直写的是gsum(b[u])+1,wa到死。主要还是离散化用的生疏

53         updat(b[u], dp[u]);

54     }

55     int len = 0;

56     for(ll i = 1; i <= n; ++i)

57     {

58         if(b[i] > b[ans[len]])//这里同上，b[i]可能会等于b[ans[len]]，所以要判断一下

59         {

60             if(k > dp[i]) k -= dp[i];

61             else

62             {

63                 --k;

64                 ans[++len] = i;

65             }

66         }

67         if(!k) break;

68     }

69     if(len == 0 || k)

70     {

71         puts("-1");

72         return 0;

73     }

74     printf("%d\n", len);

75     for(int i = 1; i <= len; ++i)

76     {

77         if(i > 1)

78         printf(" ");

79         printf("%lld", ans[i]);

80     }

81     printf("\n");

82     return 0;

83 }

巴特西

牛客网多校第5场 H subseq 【树状数组+离散化】

最新文章

热门文章