[bzoj3207]花神的嘲讽计划Ⅰ[可持久化线段树,hash]
2024-08-29 07:39:45
将每k个数字求一个哈希值,存入可持久化线段树,直接查询即可
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime> using namespace std; #define INF 0xffffffffU int n,m,k,tot;
unsigned int Sum[]={};
int val[],Left[],Right[],a[],root[]; void Insert(const unsigned int l,const unsigned int r,const int root_l,int & root_r,const unsigned int d)
{
val[root_r=++tot]=val[root_l]+;
if(l==r)return ;
unsigned int mid=l+((r-l)>>);
if(d<=mid)
{
Right[root_r]=Right[root_l];
Insert(l,mid,Left[root_l],Left[root_r],d);
}
else
{
Left[root_r]=Left[root_l];
Insert(mid+,r,Right[root_l],Right[root_r],d);
}
return ;
} int Query(const unsigned int l,const unsigned int r,const int root_l,const int root_r,const unsigned int d)
{
if(l==r)return val[root_r]-val[root_l];
unsigned int mid=l+((r-l)>>);
if(d<=mid)return Query(l,mid,Left[root_l],Left[root_r],d);
return Query(mid+,r,Right[root_l],Right[root_r],d);
} int main()
{
int i,j;
unsigned int t=; scanf("%d%d%d",&n,&m,&k);
for(i=;i<=k;++i)t=t*;
for(i=;i<=n;++i)
{
scanf("%d",&a[i]);
Sum[i]=Sum[i-]*+a[i];
} for(i=k;i<=n;++i)
{
Insert(,INF,root[i-],root[i],Sum[i]-Sum[i-k]*t);
} for(i=;i<=m;++i)
{
int l,r,b;
unsigned int temp=0U;
scanf("%d%d",&l,&r);
for(j=;j<=k;++j)scanf("%d",&b),temp=temp*+b;
printf("%s\n",Query(,INF,root[l+k-],root[r],temp)?"No":"Yes");
} return ;
}
最新文章
- 删除ibus之后导致系统设置进不了
- hnu10104
- php获取当前毫秒时间戳
- 关于GrideView Item点击后出现错乱重叠的情况
- PE制作实录 —— 补充说明
- vim emmet配置
- 插入标记 方法 insertAdjacentHTML
- linux下搭建SVN服务器完全手册-很强大!!!!!
- JavaI/O体系详解
- 急急如律令!火速搭建一个C#即时通信系统!(附源码分享——高度可移植!)
- WPF自定义控件(五)の用户控件(完结)
- electron入门
- Centos + docker,Ubuntu + docker介绍安装及详细使用
- Xilinx 7 series FPGA multiboot技术的使用
- PHP常见的一些问题总结(收藏)
- 21天打造分布式爬虫-Crawl类爬取小程序社区(八)
- EventBus使用详解
- ubuntu 中 mongodb 数据读写权限配置
- 同一个IP不同端口号使用session失效
- grep 中的正则表达式【转】