HDU_5172

描述

给了你一个数字串，问你[l,r]之间有没有数字[1,r-l+1]的一个排列。

思路

hash 随机数法
这个办法是看题解得来的，思考了很长时间，才大致弄明白。
以下几点需要特别注意

  • srand(time(NULL))时间作为随机数的种子
  • rand()返回0-32767之间的一个数，这个32767是16bit即两个字节的，无符号int类型的最大值，那么可以理解RANDuLL()函数。
  • 用亦或表示区间很方便
  • XOR[i]中表示[1~i]的亦或值，sum[i]表示a[1]~a[i]的亦或值。这个是想类似于前缀求法

AC代码

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
#include <time.h>  
#include <cstdio>  
#include <cstdlib>  
#include <cstring>  
#include <iostream>  
#include <algorithm>  
using namespace std;  
#define maxn 1000010  
#define uLL unsigned long long 
uLL XOR[maxn],a[maxn],sum[maxn];  
inline uLL RANDuLL()  
{  
    uLL tmp=(rand()+rand())*((uLL)1<<47)+(rand()+rand())*((uLL)1<<31)+(rand()+rand())*((uLL)1<<15)+(rand()+rand());  
    return tmp;  
}  
  
int main()  
{  
    srand(time(NULL));  
    XOR[0]=0;  sum[0]=0;
    for(int i=1; i<maxn; i++){  
        a[i]=RANDuLL();  
        XOR[i]=XOR[i-1]^a[i];  
    }  
    int n,m,l,r,tmp; 
    while(scanf("%d%d",&n,&m)!=EOF){  
        for(int i=1; i<=n; i++){  
            scanf("%d",&tmp);  
            sum[i]=a[tmp]^sum[i-1];  
        }  
        while(m--){  
            scanf("%d%d",&l,&r);  
            if(XOR[r-l+1]==(sum[r]^sum[l-1])) puts("YES");  
            else puts("NO");  
        }  
    }  
}