离线树状数组&&线段树 (对pre数组的利用）

124 阅读 0 评论 82 点赞

我是靠谱客的博主鳗鱼唇膏，这篇文章主要介绍离线树状数组&&线段树 (对pre数组的利用），现在分享给大家，希望可以做个参考。

https://ac.nowcoder.com/acm/problem/20325

题目大意：给定数组a, 每次询问【l,r】中有多少种不同的数。

思路：预处理出来每个数的位置pos[a[i]], 和上一次a[i] 出现的位置pre[i],对于每次询问，将其离线，也就是将询问先都储存先来，按照右端点进行排序，从前往后遍历，如果这个数是第一次出现，就将其加入树状数组中，如果不是第一次出现（其pre[i]不为0），则将其前一次出现的位置删去。

code：

复制代码

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

using namespace std;

const int N=2e6+10;

struct node{
	int l,r,id;
	bool operator< (const node &t) const
	{
		return r<t.r;
	}
}q[N];
int a[N],tr[N],ans[N];
int pre[N],pos[N]; 
int n,m;
int lowbit(int x)
{
	return x&-x;
}
int sum(int x)
{
	int ans=0;
	for(int i=x;i;i-=lowbit(i)) ans+=tr[i];
	return ans;
}
void add(int x,int c)
{
	for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		pre[i]=pos[a[i]];
		pos[a[i]]=i;
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		int l,r;
		cin>>l>>r;
		q[i]={l,r,i};
	}
	sort(q+1,q+1+m);
	int t=1;
	for(int i=1;i<=m;i++){
		while(t<=q[i].r)
		{
            if(pre[t]) add(pre[t],-1);//下标要为1
			add(t,1);
			t++;
		}
		ans[q[i].id]=sum(q[i].r)-sum(q[i].l-1);
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<endl;
	}
    
}

复制代码

https://ac.nowcoder.com/acm/problem/20545

本题与上一题几乎相同，唯一变的是本题要求的是出现两次及以上的数的种数，与上题类似，关键是预处理出pre数组。

思路：要求至少出现两次的数的个数，即pre[i]不为0，因此对于每个数，如果它的pre不为0，我们就将其加入到树状数组中，题目要求的是出现的种类数，显然大于2次的没有意义，那么关键是如何把这部分的贡献去掉呢？这里的思想很像KMP中的next数组，对于a[i], 其前一次出现位置为pre, 则其前两次出现的位置为pre[pre], 因此我们可以对于每个a[i], 如果前面出现了两次，就将其前两次出现的位置的贡献减去。

code:

复制代码

#include<bits/stdc++.h>

using namespace std;

const int N=4e6+10;

struct node{
	int l,r,id;
	bool operator< (const node &t) const
	{
		return r<t.r;
	}
}q[N];
int a[N],tr[N],ans[N];
int pre[N],pos[N]; 
int n,m,c;
int lowbit(int x)
{
	return x&-x;
}
int sum(int x)
{
	int ans=0;
	for(int i=x;i;i-=lowbit(i)) ans+=tr[i];
	return ans;
}
void add(int x,int c)
{
	for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}
signed main()
{
    
	//cin>>n>>c>>m;
    scanf("%d%d%d",&n,&c,&m);
	for(int i=1;i<=n;i++) {
		//cin>>a[i];
        scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++){
		pre[i]=pos[a[i]];
		pos[a[i]]=i;
	}
	
	for(int i=1;i<=m;i++){
		int l,r;
		//cin>>l>>r;
        scanf("%d%d",&l,&r);
		q[i]={l,r,i};
	}
	sort(q+1,q+1+m);
	int t=1;
	for(int i=1;i<=m;i++){
		while(t<=q[i].r)
		{   
            if(pre[pre[t]]) add(pre[pre[t]],-1);//下标要为1
			if(pre[t]) add(pre[t],1);
			t++;
		}
		ans[q[i].id]=sum(q[i].r)-sum(q[i].l-1);
	}
	for(int i=1;i<=m;i++){
		//cout<<ans[i]<<endl;
        printf("%dn",ans[i]);
	}
    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
#include<bits/stdc++.h>

using namespace std;

const int N=4e6+10;

struct node{
	int l,r,id;
	bool operator< (const node &t) const
	{
		return r<t.r;
	}
}q[N];
int a[N],tr[N],ans[N];
int pre[N],pos[N]; 
int n,m,c;
int lowbit(int x)
{
	return x&-x;
}
int sum(int x)
{
	int ans=0;
	for(int i=x;i;i-=lowbit(i)) ans+=tr[i];
	return ans;
}
void add(int x,int c)
{
	for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}
signed main()
{
    
	//cin>>n>>c>>m;
    scanf("%d%d%d",&n,&c,&m);
	for(int i=1;i<=n;i++) {
		//cin>>a[i];
        scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++){
		pre[i]=pos[a[i]];
		pos[a[i]]=i;
	}
	
	for(int i=1;i<=m;i++){
		int l,r;
		//cin>>l>>r;
        scanf("%d%d",&l,&r);
		q[i]={l,r,i};
	}
	sort(q+1,q+1+m);
	int t=1;
	for(int i=1;i<=m;i++){
		while(t<=q[i].r)
		{   
            if(pre[pre[t]]) add(pre[pre[t]],-1);//下标要为1
			if(pre[t]) add(pre[t],1);
			t++;
		}
		ans[q[i].id]=sum(q[i].r)-sum(q[i].l-1);
	}
	for(int i=1;i<=m;i++){
		//cout<<ans[i]<<endl;
        printf("%dn",ans[i]);
	}
    return 0;
}

https://ac.nowcoder.com/acm/problem/14601

这个题目的想法肯定是对于每一个右端点 r，去找对应的左端点 l, 但是这个l是很难找的。

换个角度思考，第i个位置来一个颜色C[i]。

我们采用区间更新+区间查询求max的方法。

如果这个颜色是第一次出现，那么对于其前面的所有节点都累加 W[C[i]], 价值最大的节点即为我们要找的l。

如果这个颜色不是第一次出现，那么记录其前一次出现的位置pre[C[i]]和前前一次出现的位置pre2[C[i]],

他对[pre2[C[i]]+1, pre[C[i]]]的贡献为 -C[i], 因为这段区间之前加过了C[i]，现在要减掉。

对 [pre[C[i]]+1, i] 的贡献为 C[i]，对这段区间进行更新即可。

最终只要对 1~i位置进行单点最大值查询即可找到 1~i 的最大贡献。

code:

复制代码

#include<bits/stdc++.h>

using namespace std;
#define int long long
const int N=1e5+10;

struct node{
	int l,r,v,add;
}tr[N<<2];
int c[N],w[N],pos[N],pre[N];

void pushup(int u)
{
	tr[u].v=max(tr[u<<1].v,tr[u<<1|1].v);
}

void pushdown(int u)
{
	if(tr[u].add)
	{
		int d=tr[u].add;
		tr[u<<1].add+=d; tr[u<<1].v+=d;
		tr[u<<1|1].add+=d; tr[u<<1|1].v+=d;
		tr[u].add=0;
	}
}
void build(int u,int l,int r)
{
	if(l==r){
		tr[u]={l,l,0,0};
	}
	else {
		tr[u]={l,r};
		int mid=l+r>>1;
		build(u<<1,l,mid); build(u<<1|1,mid+1,r);
		pushup(u);
	}
}
void modify(int u,int l,int r,int v)
{
	if(tr[u].l>=l&&tr[u].r<=r){
		tr[u].add+=v; tr[u].v+=v;
	}
	else {
		pushdown(u);
		int mid=tr[u].l+tr[u].r>>1;
		if(l<=mid) modify(u<<1,l,r,v);
		if(r>mid) modify(u<<1|1,l,r,v);
		pushup(u);
	}
}
signed main()
{
	int n,m;
	while(cin>>n>>m)
	{
		for(int i=1;i<=n;i++) cin>>c[i];
		for(int i=1;i<=m;i++) cin>>w[i];
		memset(pos,0,sizeof pos);
		memset(pre,0,sizeof pre);
		for(int i=1;i<=n;i++){
			pre[i]=pos[c[i]];
			pos[c[i]]=i;
		}
		build(1,1,n);
		int ans=0;
		for(int i=1;i<=n;i++){
			modify(1,pre[i]+1,i,w[c[i]]);
			if(pre[i]) modify(1,pre[pre[i]]+1,pre[i],-w[c[i]]);
            //注意不要越界
			ans=max(ans,tr[1].v);
		}
		cout<<ans<<endl;
	}
	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
#include<bits/stdc++.h>

using namespace std;
#define int long long
const int N=1e5+10;

struct node{
	int l,r,v,add;
}tr[N<<2];
int c[N],w[N],pos[N],pre[N];

void pushup(int u)
{
	tr[u].v=max(tr[u<<1].v,tr[u<<1|1].v);
}

void pushdown(int u)
{
	if(tr[u].add)
	{
		int d=tr[u].add;
		tr[u<<1].add+=d; tr[u<<1].v+=d;
		tr[u<<1|1].add+=d; tr[u<<1|1].v+=d;
		tr[u].add=0;
	}
}
void build(int u,int l,int r)
{
	if(l==r){
		tr[u]={l,l,0,0};
	}
	else {
		tr[u]={l,r};
		int mid=l+r>>1;
		build(u<<1,l,mid); build(u<<1|1,mid+1,r);
		pushup(u);
	}
}
void modify(int u,int l,int r,int v)
{
	if(tr[u].l>=l&&tr[u].r<=r){
		tr[u].add+=v; tr[u].v+=v;
	}
	else {
		pushdown(u);
		int mid=tr[u].l+tr[u].r>>1;
		if(l<=mid) modify(u<<1,l,r,v);
		if(r>mid) modify(u<<1|1,l,r,v);
		pushup(u);
	}
}
signed main()
{
	int n,m;
	while(cin>>n>>m)
	{
		for(int i=1;i<=n;i++) cin>>c[i];
		for(int i=1;i<=m;i++) cin>>w[i];
		memset(pos,0,sizeof pos);
		memset(pre,0,sizeof pre);
		for(int i=1;i<=n;i++){
			pre[i]=pos[c[i]];
			pos[c[i]]=i;
		}
		build(1,1,n);
		int ans=0;
		for(int i=1;i<=n;i++){
			modify(1,pre[i]+1,i,w[c[i]]);
			if(pre[i]) modify(1,pre[pre[i]]+1,pre[i],-w[c[i]]);
            //注意不要越界
			ans=max(ans,tr[1].v);
		}
		cout<<ans<<endl;
	}
	return 0;
}