BZOJ3207花神的嘲讽计划Ⅰ——主席树+hash
2018-07-11 03:30:44来源:博客园 阅读 ()
题目描述
输入
输出
样例输入
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
样例输出
Yes
Yes
Yes
No
提示
#include<map> #include<set> #include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define mid L+((R-L)>>1) using namespace std; const int base=13131; int n,m,k; int cnt; int tot; int x,y,z; int l[8000010]; int r[8000010]; int sum[8000010]; int root[200010]; unsigned long long h[200010]; unsigned long long s[200010]; int updata(int pre,unsigned long long L,unsigned long long R,unsigned long long x) { int rt=++cnt; l[rt]=l[pre]; r[rt]=r[pre]; sum[rt]=sum[pre]+1; if(L<R) { if(x<=mid) { l[rt]=updata(l[pre],L,mid,x); } else { r[rt]=updata(r[pre],mid+1,R,x); } } return rt; } bool query(int ll,int rr,unsigned long long L,unsigned long long R,unsigned long long k) { if(L>=R) { if(sum[rr]-sum[ll]!=0) { return true; } return false; } int x=sum[rr]-sum[ll]; if(x!=0) { if(k<=mid) { query(l[ll],l[rr],L,mid,k); } else { query(r[ll],r[rr],mid+1,R,k); } } else { return false; } } int main() { scanf("%d%d%d",&n,&m,&k); s[0]=1; for(int i=1;i<=n;i++) { scanf("%d",&x); h[i]=h[i-1]*base+x; s[i]=s[i-1]*base; } for(int i=k;i<=n;i++) { unsigned long long a=h[i]-h[i-k]*s[k]; root[i]=updata(root[i-1],0,18446744073709551615ull,a); } for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); unsigned long long a=0; for(int j=1;j<=k;j++) { scanf("%d",&z); a=a*base+z; } x+=k-1; if(x>y) { printf("Yes\n"); continue; } if(query(root[x-1],root[y],0,18446744073709551615ull,a)==true) { printf("No\n"); } else { printf("Yes\n"); } } }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- bzoj3209: 花神的数论题(数位DP) 2019-08-16
- bzoj3207--Hash+主席树 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash