GTY's gay friends
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1379 Accepted Submission(s): 355
Problem Description
GTY has n
gay friends. To manage them conveniently, every morning he ordered all
his gay friends to stand in a line. Every gay friend has a
characteristic value ai
, to express how manly or how girlish he is. You, as GTY's assistant,
have to answer GTY's queries. In each of GTY's queries, GTY will give
you a range [l,r] . Because of GTY's strange hobbies, he wants there is a permutation [1..r−l+1] in [l,r]. You need to let him know if there is such a permutation or not.
gay friends. To manage them conveniently, every morning he ordered all
his gay friends to stand in a line. Every gay friend has a
characteristic value ai
, to express how manly or how girlish he is. You, as GTY's assistant,
have to answer GTY's queries. In each of GTY's queries, GTY will give
you a range [l,r] . Because of GTY's strange hobbies, he wants there is a permutation [1..r−l+1] in [l,r]. You need to let him know if there is such a permutation or not.
Input
Multi test cases (about 3) . The first line contains two integers n and m ( 1≤n,m≤1000000
), indicating the number of GTY's gay friends and the number of GTY's
queries. the second line contains n numbers seperated by spaces. The ith number ai ( 1≤ai≤n ) indicates GTY's ith
gay friend's characteristic value. The next m lines describe GTY's
queries. In each line there are two numbers l and r seperated by spaces (
1≤l≤r≤n ), indicating the query range.
), indicating the number of GTY's gay friends and the number of GTY's
queries. the second line contains n numbers seperated by spaces. The ith number ai ( 1≤ai≤n ) indicates GTY's ith
gay friend's characteristic value. The next m lines describe GTY's
queries. In each line there are two numbers l and r seperated by spaces (
1≤l≤r≤n ), indicating the query range.
Output
For each query, if there is a permutation [1..r−l+1] in [l,r], print 'YES', else print 'NO'.
Sample Input
8 5
2 1 3 4 5 2 3 1
1 3
1 1
2 2
4 8
1 5
3 2
1 1 1
1 1
1 2
2 1 3 4 5 2 3 1
1 3
1 1
2 2
4 8
1 5
3 2
1 1 1
1 1
1 2
Sample Output
YES NO YES YES YES YES NO
题意：
n个数m个询问，询问（l,r）中的数是否为1 ~ r-l+1的一个排列。
分析：
若（l,r）中的数为1 ~ r-l+1中的一个排列，则必须满足：
1、（l,r）中的数之和为len*(len+1)/2，其中len = r-l+1。
2、区间内的数字各不相同，即用线段树维护位置i上的数上次出现的位置的最大值。
只要区间内所有的数上次出现的位置last[i] < l，则区间内的数各不相同。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long LL;
const int N = ;
int pre[N],now[N];
LL sum[N];
struct Tree{
int MAX_ID;
}tree[N<<];
int MAX_ID;
void PushUp(int idx){
tree[idx].MAX_ID = max(tree[idx<<].MAX_ID,tree[idx<<|].MAX_ID);
}
void build(int l,int r,int idx){
if(l==r){
tree[idx].MAX_ID = pre[l];
return;
}
int mid = (l+r)>>;
build(l,mid,idx<<);
build(mid+,r,idx<<|);
PushUp(idx);
}
void query(int l,int r,int L,int R,int idx){
if(l >= L&& r <= R){
MAX_ID = max(MAX_ID,tree[idx].MAX_ID);
return;
}
int mid = (l+r)>>;
if(mid>=L) query(l,mid,L,R,idx<<);
if(mid<R) query(mid+,r,L,R,idx<<|);
}
int main()
{
int n,k;
while(scanf("%d%d",&n,&k)!=EOF){
memset(now,,sizeof(now));
sum[] = ;
for(int i=;i<=n;i++){
int x;
scanf("%d",&x);
sum[i] = sum[i-]+x;
pre[i] = now[x];
now[x] = i;
}
build(,n,);
while(k--){
int l,r;
scanf("%d%d",&l,&r);
LL len = r-l+;
LL S = (len+)*(len)/;
if(sum[r]-sum[l-]!=S){
printf("NO\n");
continue;
}
MAX_ID = -;
query(,n,l,r,);
if(MAX_ID<l) printf("YES\n");
else printf("NO\n");
}
}
return ;
}
不过我们还有更简单的hash做法,对于[1..n][1..n][1..n]中的每一个数随机一个64位无符号整型作为它的hash值,一个集合的hash值为元素的异或和,预处理[1..n]的排列的hash和原序列的前缀hash异或和,就可以做到线性预处理,O(1)O(1)O(1)回答询问.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<ctime>
#define eps (1e-8) using namespace std; typedef long long ll;
unsigned long long ra[],a[],ha[];
int n,m,t,p; //int main(int argc,char const *argv[])
int main()
{
srand(time(NULL));
a[] = ha[] = ;
for(int i=; i<=; i++)
{
ra[i] = rand()*rand();
ha[i] = ha[i-]^ra[i];
}
for(int i=; i<=; i++)
{
printf("%lld\n",ra[i]);
}
while(~scanf("%d%d",&n,&m))
{
for(int i=; i<=n; i++)
{
scanf("%d",&t);
a[i] = ra[t];
a[i]^=a[i-];
}
for(int i=; i<=m; i++)
{
scanf("%d%d",&t,&p);
puts((ha[p-t+]==(a[p]^a[t-])?"YES":"NO"));
}
}
return ;
}