hdu5172 树状数组+预处理

题意:

给一个长为n的序列,在给出m个l和r,问【l,r】能否形成一个【1,r-l+1】的全排列

思路:

一开始想这是莫队,maxn=100w,sqrt(n)n的复杂度无法接受……
【1,r-l+1】的和是确定的,为(r-l+2)
(r-l+1)/2,如果元素是不重复的,那么其和是不可能为(r-l+2)*(r-l+1)/2,前缀和处理,下面的问题就是判重
last【a】表是从左往右扫,a这个数最后出现的位置,初始化为0,对于第i个 数a,他的前一个a,就是last【a】,然后更新last【a】=i
现在可以知道每一个位置的数前一次出现的位置,如果【l,r】中 所有数前一次出现的位置都小于l,则【l,r】没有重复的元素
上面的问题可以转化为求区间最大值,若【l,r】的前一个数的位置的最大值小于l,则没有重复
区间求最大值,可rmq(不熟),可线段树(代码长)

考虑这题特殊性,可用树状数组,想想树状数组的区间求和,我们一般是用sum(r)-sum(r-l),最大值则不能这么搞,但是这题可以,因为每个数的前一个位置j一定小于当前位置i,则max【1,l-1】=l,则有重复,也就是max【1,r】>=l
对于任意【l,r】,有max【l,r】==max【1,r】,这样就可以用树状数组了

代码:

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
using namespace std;
typedef long long ll;
const int maxn=1000005;
ll sum[maxn];
int n,m;
int a;
int last[maxn];
int c[maxn];
struct BIT{
void init(){
cl(c,0);
}
int lowbit(int x){
return x&-x;
}
void add(int x,int v){
while(x<maxn){
c[x]=max(c[x],v);
x+=lowbit(x);
}
}
int Max(int x){
int ret=0;
while(x>0){
ret=max(ret,c[x]);
x-=lowbit(x);
}
return ret;
}
}bit;
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
sum[0]=0;
bit.init();
memset(last,0,sizeof(last));
for(int i=1;i<=n;i++){
scanf("%d",&a);
bit.add(i,last[a]);
last[a]=i;
sum[i]=sum[i-1]+(ll)a;
}
int l,r;
for(int i=0;i<m;i++){
scanf("%d%d",&l,&r);
ll temp=(ll)(r-l+2)*(ll)(r-l+1)/2;
if(sum[r]-sum[l-1]==temp&&bit.Max(r)<l){
printf("YES\n");
}else printf("NO\n");
}
}
return 0;
}