「BZOJ3207」花神的嘲讽计划Ⅰ
Description
背景
花神是神，一大癖好就是嘲讽大J，举例如下：
“哎你傻不傻的！「hqz：大笨J」”
“这道题又被J屎过了！！”
“J这程序怎么跑这么快！J要逆袭了！”
……
描述
这一天DJ在给吾等众蒟蒻讲题，花神在一边做题无聊，就跑到了一边跟吾等众蒟蒻一起听。以下是部分摘录：
1.
“J你在讲什么！”
“我在讲XXX！”
“哎你傻不傻的！这么麻烦，直接XXX再XXX就好了！”
“……”
2.
“J你XXX讲过了没？”
“……”
“那个都不讲你就讲这个了？哎你傻不傻的！”
“……”
DJ对这种情景表示非常无语，每每出现这种情况，DJ都是非常尴尬的。
经过众蒟蒻研究，DJ在讲课之前会有一个长度为N方案，我们可以把它看作一个数列；
同样，花神在听课之前也会有一个嘲讽方案，有M个，每次会在x到y的这段时间开始嘲讽，为了减少题目难度，每次嘲讽方案的长度是一定的，为K。
花神嘲讽DJ让DJ尴尬需要的条件：
在x~y的时间内DJ没有讲到花神的嘲讽方案，即J的讲课方案中的x~y没有花神的嘲讽方案「这样花神会嘲讽J不会所以不讲」。
经过众蒟蒻努力，在一次讲课之前得到了花神嘲讽的各次方案，DJ得知了这个消息以后欣喜不已，DJ想知道花神的每次嘲讽是否会让DJ尴尬「说不出话来」。
Input
第1行3个数N，M，K；
第2行N个数，意义如上；
第3行到第3+M-1行，每行K+2个数，前两个数为x,y,然后K个数，意义如上；
Output
对于每一个嘲讽做出一个回答会尴尬输出‘Yes’，否则输出‘No’
Sample Input
8 5 3
1 2 3 4 5 6 7 8
2 5 2 3 4
1 8 3 2 1
5 7 4 5 6
2 5 1 2 3
1 7 3 4 5
1 2 3 4 5 6 7 8
2 5 2 3 4
1 8 3 2 1
5 7 4 5 6
2 5 1 2 3
1 7 3 4 5
Sample Output
No
Yes
Yes
Yes
No
Yes
Yes
Yes
No
HINT
· 题中所有数据不超过2*10^9;保证方案序列的每个数字<=N
2~5中有2 3 4的方案，输出No，表示DJ不会尴尬
1~8中没有3 2 1的方案，输出Yes，表示DJ会尴尬
5~7中没有4 5 6的方案，输出Yes，表示DJ会尴尬
2~5中没有1 2 3的方案，输出Yes，表示DJ会尴尬
1~7中有3 4 5的方案，输出No，表示DJ不会尴尬
题解
此题的数据范围呢。。。
把每K个数字hash存起来，然后扔进可持久化线段树
再把询问的hash值在权值线段树中查询
|
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 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 18446744073709551615UL using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,K,cnt; int val[200005],b[200005],rt[200005]; int sum[8000005],a[8000005][2]; unsigned ll H[200005]; void insert(int x,int &y,unsigned ll val) { y=++cnt;int tmp=y; sum[y]=sum[x]+1; unsigned ll l=0,r=inf,mid; while(l!=r) { mid=l/2+r/2; if((l&1)&&(r&1))mid++; int t=0; if(val>mid)t=1,l=mid+1; else r=mid-1; a[y][t]=++cnt; a[y][t^1]=a[x][t^1]; x=a[x][t];y=a[y][t];sum[y]=sum[x]+1; } y=tmp; } bool query(int x,int y,unsigned ll val) { unsigned ll l=0,r=inf,mid; while(l!=r) { mid=l/2+r/2; if((l&1)&&(r&1))mid++; int t=0; if(val>mid)t=1,l=mid+1; else r=mid-1; x=a[x][t];y=a[y][t]; } return (sum[y]-sum[x])!=0; } int main() { n=read();m=read();K=read(); for(int i=1;i<=n;i++)val[i]=read(); for(int i=1;i<=n;i++)H[i]=H[i-1]*107+val[i]; unsigned ll M=1;for(int i=1;i<=K;i++)M*=107; for(int i=K;i<=n;i++) insert(rt[i-1],rt[i],H[i]-H[i-K]*M); while(m--) { int x=read(),y=read(); for(int i=1;i<=K;i++)b[i]=read(); unsigned ll now=0; for(int i=1;i<=K;i++)now=now*107+b[i]; if(query(rt[x+K-2],rt[y],now))puts("No"); else puts("Yes"); } return 0; } |
计数器 9304365
OI 课件=>
OI 课件=>
黄学长，这个程序好像有点问题呀… /05
这组数据输出应该是Yes，您输出了No..
2 1 2
5 4
1 2 5 3
谢谢！