隐藏
「AHOI2013」作业 - 莫队+值域分块 / 线段树分治 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「AHOI2013」作业 - 莫队+值域分块 / 线段树分治

题目大意

    给定了一个长度为$n$的数列和若干个询问,每个询问是关于数列的区间$[L,r]$(表示数列的第$L$个数到第$r$个数),首先你要统计该区间内大于等于$a$,小于等于$b$的数的个数,其次是所有大于等于$a$,小于等于$b$的,且在该区间中出现过的数值的个数。
    小A望着那数万的数据规模几乎绝望,只能向大神您求救,请您帮帮他吧。


题目分析

这道题可以用莫队很简单粗暴地水过去,跑得很快。

毕竟这是论文题,我们还是按照徐寅展的原文方法讲一讲。(徐寅展似乎没说清)

这道题我们需要维护两个区间,一个维护区间,一个维护值域,不难想到用树套树解决问题,但是要求不统计重复的就很困难了。

为了方便计算重复元素,我们对值域建立线段树,线段树的结点存储值域在区间范围内的所有点坐标(从小到大排序),这样不同的值域区间显然不会有坐标相同的。

那么如何维护这样的一个不重复数值个数呢?对于当前一段连续值域区间,对于所有包含这个值域区间的询问,均需要统计这样的答案,故我们暂时先考虑在一个线段树完整区间内统计答案。
我们可以采用左端点移动,右端点数据结构维护的方法。
将所有这个区间包含的询问提取出来并按询问的$l$从小到大排序,将所有的值第一次出现的点加入树状数组。
考虑对应的区间内的最靠左结点$p$,若$p$的坐标在$l$右边,显然这样的区间是可以统计答案的,用二分和树状数组分别统计出两个问的答案。
若$p$的左边在$l$左边,说明这样的点$p$不会再对任何区间作出贡献,我们将$p$删掉,并将下一个相同颜色的点加入树状数组。

计算下一个相同颜色的点可以用链表统计。

要实现这样一个过程,我们可以采用线段树分治的过程,进入时将第一次出现的点加入树状数组,递归前清空树状数组,再递归访问子区间。


代码

莫队+值域分块

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

void Put_Int(int x) {
if(x<0)putchar('-'),x=abs(x);
if(x>9)Put_Int(x/10);
putchar(x%10+'0');
}

const int maxn=100005;

int n,m,Belong[maxn],Beauty[maxn],L[maxn],R[maxn],Hash[maxn],BlockAns[maxn],BlockAns2[maxn],ans1[1000005],ans2[1000005];

struct Question {
int left,right;
int a,b,id;
bool operator < (const Question& b) const { //核心排序
return Belong[left]<Belong[b.left]||(Belong[left]==Belong[b.left]&&right<b.right);
}
} q[1000005];

int query1(int Down,int Up) {
int ans=0,Left=Belong[Down],Right=Belong[Up];
for(int i=Left+1; i<=Right-1; i++)ans+=BlockAns[i];
if(Left==Right) {
for(int i=Down; i<=Up; i++)if(Hash[i])ans++;
} else {
for(int i=Down; i<=R[Left]; i++)if(Hash[i])ans++;
for(int i=L[Right]; i<=Up; i++)if(Hash[i])ans++;
}
return ans;
}

int query2(int Down,int Up) {
int ans=0,Left=Belong[Down],Right=Belong[Up];
for(int i=Left+1; i<=Right-1; i++)ans+=BlockAns2[i];
if(Left==Right) {
for(int i=Down; i<=Up; i++)ans+=Hash[i];
} else {
for(int i=Down; i<=R[Left]; i++)ans+=Hash[i];
for(int i=L[Right]; i<=Up; i++)ans+=Hash[i];
}
return ans;
}

void update(int val,int delta) {
if(Hash[val]==0&&delta==1)BlockAns[Belong[val]]++;
if(Hash[val]==1&&delta==-1)BlockAns[Belong[val]]--;
BlockAns2[Belong[val]]+=delta;
Hash[val]+=delta;
}

int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)Beauty[i]=Get_Int();
for(int i=1; i<=m; i++) {
q[i].left=Get_Int();
q[i].right=Get_Int();
q[i].a=Get_Int();
q[i].b=Get_Int();
q[i].id=i;
}
int size=sqrt(n);
for(int i=1; i<=n; i++) {
Belong[i]=(i-1)/size+1;
if(!L[Belong[i]])L[Belong[i]]=i;
R[Belong[i]]=i;
}
sort(q+1,q+m+1);
int Left=1,Right=1;
Hash[Beauty[1]]=BlockAns[Belong[Beauty[1]]]=BlockAns2[Belong[Beauty[1]]]=1;
for(int i=1; i<=m; i++) {
while(Left>q[i].left)update(Beauty[--Left],1);
while(Left<q[i].left)update(Beauty[Left++],-1);
while(Right<q[i].right)update(Beauty[++Right],1);
while(Right>q[i].right)update(Beauty[Right--],-1);
ans1[q[i].id]=query1(q[i].a,q[i].b);
ans2[q[i].id]=query2(q[i].a,q[i].b);
}
for(int i=1; i<=m; i++)Put_Int(ans2[i]),putchar(' '),Put_Int(ans1[i]),putchar('\n');
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=100005;

vector<int>pos[maxn];

int n,m,a[maxn],ans1[maxn*10],ans2[maxn*10],Hash[maxn],Next[maxn];
bool vst[maxn];

struct BIT {
int c[maxn];
#define lowbit(x) x&(-x)
void add(int x,int v) {
for(int i=x; i<=n; i+=lowbit(i))c[i]+=v;
}
void clear(int x) {
for(int i=x; i<=n; i+=lowbit(i))c[i]=0;
}
int sum(int x) {
int sum=0;
for(int i=x; i>=1; i-=lowbit(i))sum+=c[i];
return sum;
}
} bit;

struct node {
int l,r,id;
node(int _l=0,int _r=0,int _id=0):l(_l),r(_r),id(_id) {}
bool operator < (const node& b) const {
return l<b.l;
}
};

struct Tree {
int left,right;
vector<int>point;
vector<node>interval;
Tree(int l=0,int r=0):left(l),right(r),interval(vector<node>()),point(vector<int>()) {}
};

struct Segment_Tree {
Tree tree[maxn*4];
#define ls index<<1
#define rs index<<1|1
void build(int index,int Left,int Right) {
tree[index]=Tree(Left,Right);
if(Left==Right)return;
int mid=(Left+Right)>>1;
build(ls,Left,mid);
build(rs,mid+1,Right);
}
void insert_point(int index,int target,int pos) {
if(tree[index].right<target||tree[index].left>target)return;
tree[index].point.push_back(pos);
if(tree[index].left==tree[index].right)return;
insert_point(ls,target,pos);
insert_point(rs,target,pos);
}
void insert_interval(int index,int Left,int Right,int l,int r,int id) {
if(tree[index].right<Left||tree[index].left>Right)return;
if(Left<=tree[index].left&&Right>=tree[index].right) {
tree[index].interval.push_back(node(l,r,id));
return;
}
insert_interval(ls,Left,Right,l,r,id);
insert_interval(rs,Left,Right,l,r,id);
}
void binary(int index) {
sort(tree[index].interval.begin(),tree[index].interval.end());
for(int pos:tree[index].point)
if(!vst[a[pos]]) {
bit.add(pos,1);
vst[a[pos]]=1;
}
auto now=tree[index].interval.begin();
for(int i=0; i<tree[index].point.size(); i++) {
int pos=tree[index].point[i];
while(now!=tree[index].interval.end()) {
node tmp=*now;
if(tmp.l>pos)break;
ans1[tmp.id]+=bit.sum(tmp.r);
ans2[tmp.id]+=upper_bound(tree[index].point.begin(),tree[index].point.end(),tmp.r)-tree[index].point.begin()-i;
now++;
}
bit.add(pos,-1);
if(Next[pos])bit.add(Next[pos],1);
}
for(int pos:tree[index].point) {
bit.clear(pos);
vst[a[pos]]=0;
}
if(tree[index].left==tree[index].right)return;
binary(ls);
binary(rs);
}
} st;

int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
for(int i=n; i>=1; i--) {
Next[i]=Hash[a[i]];
Hash[a[i]]=i;
}
st.build(1,1,n);
for(int i=1; i<=n; i++)st.insert_point(1,a[i],i);
for(int i=1; i<=m; i++) {
int l=Get_Int(),r=Get_Int(),a=Get_Int(),b=Get_Int();
st.insert_interval(1,a,b,l,r,i);
}
st.binary(1);
for(int i=1; i<=m; i++)printf("%d %d\n",ans2[i],ans1[i]);
return 0;
}

姥爷们赏瓶冰阔落吧~