Codeforces 1181 D Irrigation 题解（树状数组+倍增）

81 阅读 0 评论 54 点赞

我是靠谱客的博主动人高山，这篇文章主要介绍Codeforces 1181 D Irrigation 题解（树状数组+倍增），现在分享给大家，希望可以做个参考。

题目：CF1181D.
题目大意：有一个长度为 $m$ 的计数数组 $a$ ，初始均为 $0$ ，并给定 $n$ 个操作 $x$ 表示让 $a [x]$ 加 $1$ .现在还有一些操作，一个操作是在 $a [i]$ 中找一个最小的位置 $p$ （有多个则去最小的满足条件的 $p$ ），使得 $a [p]$ 加 $1$ .现在有 $q$ 个询问，问第 $k$ 个操作（前 $n$ 个操作也算入）时的 $p$ .
$5*10^5,n<kleq 10^{18}$ .

考虑把 $n$ 个操作后的 $a$ 数组按照从小到大排个序（当然如果大小相等编号小的在前），然后我们可以想一下接下来的操作是怎么样的.

考虑每一个操作，当最低点有 $k$ 个的时候，必然是每 $k$ 个操作一个循环节，并且会循环总共 $a [k + 1] - a [k]$ 次之后最低点多增加了一个.

有了这个性质之后，就可以把它分成 $m$ 部分分别求解，其中第 $i$ 部分是把前 $i$ 小的数填到第 $i + 1$ 小的数的过程.可以考虑依次枚举每一部分，然后求解这一部分内的询问，并且维护每一部分开始时的操作次数，用当前询问的 $k$ 减掉当前这个操作次数之后我们就得到了它是这个部分操作时的第几个操作，由于每一个部分内的操作是循环的，我们就可以通过取模得到它是这个操作可以影响到的数中第几小的.

然后问题转化为了如何动态维护第 $k$ 小，可以直接通过值域树状数组上倍增来处理.

时间复杂度 $O (n lo g n)$ .

代码如下：

复制代码

#include<bits/stdc++.h>
  using namespace std;

#define Abigail inline void
typedef long long LL;

const int N=500000,C=20;

int n,m,sk;
struct cont{
  LL cnt;
  int id;
}a[N+9];

bool cmp1(const cont &a,const cont &b){return a.cnt<b.cnt||a.cnt==b.cnt&&a.id<b.id;}

struct question{
  LL k;
  int id;
}q[N+9];
int ans[N+9];

bool cmp2(const question &a,const question &b){return a.k<b.k;}

int c[N+9];

void Add(int p,int v){for (;p<=m;p+=p&-p) c[p]+=v;}

int Query_kth(int p){
  int res=0;
  for (int i=C-1;i>=0;--i)
    if (res+(1<<i)<=m&&p>c[res+(1<<i)]) p-=c[res+=1<<i];
  return res+1;
}

Abigail into(){
  scanf("%d%d%d",&n,&m,&sk);
  int x;
  for (int i=1;i<=n;++i){
  	scanf("%d",&x);
  	++a[x].cnt;
  }
  for (int i=1;i<=sk;++i){
  	scanf("%I64d",&q[i].k);
  	q[i].id=i;q[i].k-=(LL)n;
  }
}

Abigail work(){
  for (int i=1;i<=m;++i) a[i].id=i;
  sort(a+1,a+m+1,cmp1);
  sort(q+1,q+sk+1,cmp2);
  int j=1;
  LL now=0;
  for (int i=1;i<m;++i){
    Add(a[i].id,1);
  	for (;j<=sk&&q[j].k<=now+(a[i+1].cnt-a[i].cnt)*i;++j){
  	  int t=(q[j].k-now)%i;
  	  ans[q[j].id]=Query_kth(t==0?i:t);
  	}
  	now+=(a[i+1].cnt-a[i].cnt)*i;
  }
  Add(a[m].id,1);
  for (;j<=sk;++j){
  	int t=(q[j].k-now)%m;
  	ans[q[j].id]=Query_kth(t==0?m:t);
  }
}

Abigail outo(){
  for (int i=1;i<=sk;++i)
    printf("%dn",ans[i]);
}

int main(){
  into();
  work();
  outo();
  return 0;
}

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
#include<bits/stdc++.h>
  using namespace std;

#define Abigail inline void
typedef long long LL;

const int N=500000,C=20;

int n,m,sk;
struct cont{
  LL cnt;
  int id;
}a[N+9];

bool cmp1(const cont &a,const cont &b){return a.cnt<b.cnt||a.cnt==b.cnt&&a.id<b.id;}

struct question{
  LL k;
  int id;
}q[N+9];
int ans[N+9];

bool cmp2(const question &a,const question &b){return a.k<b.k;}

int c[N+9];

void Add(int p,int v){for (;p<=m;p+=p&-p) c[p]+=v;}

int Query_kth(int p){
  int res=0;
  for (int i=C-1;i>=0;--i)
    if (res+(1<<i)<=m&&p>c[res+(1<<i)]) p-=c[res+=1<<i];
  return res+1;
} 

Abigail into(){
  scanf("%d%d%d",&n,&m,&sk);
  int x;
  for (int i=1;i<=n;++i){
  	scanf("%d",&x);
  	++a[x].cnt;
  }
  for (int i=1;i<=sk;++i){
  	scanf("%I64d",&q[i].k);
  	q[i].id=i;q[i].k-=(LL)n;
  }
}

Abigail work(){
  for (int i=1;i<=m;++i) a[i].id=i;
  sort(a+1,a+m+1,cmp1);
  sort(q+1,q+sk+1,cmp2);
  int j=1;
  LL now=0;
  for (int i=1;i<m;++i){
    Add(a[i].id,1);
  	for (;j<=sk&&q[j].k<=now+(a[i+1].cnt-a[i].cnt)*i;++j){
  	  int t=(q[j].k-now)%i;
  	  ans[q[j].id]=Query_kth(t==0?i:t);
  	}
  	now+=(a[i+1].cnt-a[i].cnt)*i;
  }
  Add(a[m].id,1);
  for (;j<=sk;++j){
  	int t=(q[j].k-now)%m;
  	ans[q[j].id]=Query_kth(t==0?m:t);
  }
}

Abigail outo(){
  for (int i=1;i<=sk;++i)
    printf("%dn",ans[i]);
}

int main(){
  into();
  work();
  outo();
  return 0;
}