题目链接
英文版
【ACM_前辍和|GTY's gay friends】
GTY's gay friends
Time Limit: 6000/3000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 816Accepted Submission(s): 184
Problem Description GTY hasn 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 valueai , 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. Theith numberai (1≤ai≤n ) indicates GTY'sith 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
Sample Output
YES NO YES YES YES YES NO 英语版 GTY's gay friends
Time Limit: 6000/3000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 264Accepted Submission(s): 57
问题描述
GTY有n个基友，出于某种恶趣味，GTY每天早上会让他的基友们排成一行，每个基友有一个特征值，表示基友有多雄壮或娘炮，你，作为GTY的助手，必须回答GTY的每个询问，GTY每次会问一个区间[l,r]是否为一个1到r?l+1的排列。
输入描述
多组数据（约3组），每组数据的第一行有两个数n,m(1≤n,m≤100000) 表示初始基友数量和询问个数，第二行包含n个数ai(1≤ai≤n)表示基友的特征值，接下来m行每行两个数l,r表示询问[l,r]是否为一个排列。
输出描述
对于每个询问，若它是一个排列，输出”YES”,否则输出”NO”
输入样例
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
输出样例
YES NO YES YES YES YES NO
/*
一个区间是排列只需要区间和为len(len+1)2(len为区间长度),
且互不相同,对于第一个问题我们用前缀和解决,
对于第二个问题,
预处理每个数的上次出现位置,记它为pre,
互不相同即区间中pre的最大值小于左端点,
使用线段树或Sparse Table.
即可在O(n)/O(nlogn)的预处理后 O(logn)/O(1)回答每个询问.
*/
#include
#include
#include
using namespace std;
const int maxn=1000000+10;
int n,m,x,y;
int sum[maxn<<2],t,pre[maxn],anx[maxn];
__int64 S[maxn];
void pushup(int rt) {
sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
}
void build(int l,int r,int rt) {
if(l==r) {
sum[rt]=pre[l];
// printf("[%d]\n",l);
return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt) {
if(L<=l&&r<=R) {
return sum[rt];
}
int mid=(l+r)>>1;
int ret=0;
if(L<=mid) {
ret=max(ret,query(L,R,l,mid,rt<<1));
}
if(R>mid) {
ret=max(ret,query(L,R,mid+1,r,rt<<1|1));
}
return ret;
}int main() {
//freopen("D://imput.txt","r",stdin);
while(~scanf("%d%d",&n,&m)) {
S[0]=0;
memset(anx,0,sizeof(anx));
for(int i=1;
i<=n;
i++) {
scanf("%d",&t);
pre[i]=anx[t];
anx[t]=i;
S[i]=S[i-1]+t;
}
build(1,n,1);
while(m--) {
scanf("%d%d",&x,&y);
int len = y-x+1;
__int64 res=(__int64)len*(len+1);
if(S[y]-S[x-1]!=res/2LL) {
printf("NO\n");
} else {
int t=query(x,y,1,n,1);
printf("%s\n",t 方法二：
/*
一个集合的hash值为元素的异或和,
预处理[1..n]的排列的hash和原序列的前缀hash异或和,
就可以做到线性预处理,O(1)回答询问.
*/
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1000000+5;
typedef __int64 LL;
int n,m,t,l,r;
LL Hash[maxn],xr[maxn],xt[maxn],Xor[maxn],Sxt[maxn];
int main() {
srand(time(0));
for(int i=1;
i 
