BZOJ4810: [Ynoi2017]由乃的玉米田(莫队+bitset)
2018-06-17 20:52:25来源:未知 阅读 ()
Submit: 911 Solved: 444
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
1 1 2 3 4
2 1 1 2
1 1 2 2
3 1 1 1
3 5 5 16
1 2 3 4
Sample Output
yumi
yuno
yuno
yumi
HINT
Source
By 佚名提供
#include<cstdio> #include<cstring> #include<bitset> #include<cmath> #include<algorithm> #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++) char buf[1<<23],*p1=buf,*p2=buf; using namespace std; const int MAXN=1e5+10; const int limit=100000; inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int N,M,block; int belong[MAXN],cnt[MAXN],out[MAXN]; bitset<100001>bit,bitinv; struct Qus { int l,r,val,opt,ID; }Q[MAXN]; int a[MAXN]; inline int comp(const Qus &a,const Qus &b) { return belong[a.l]==belong[b.l]?a.r<b.r:belong[a.l]<belong[b.l]; } inline void Delet(int x) { cnt[x]--; if(cnt[x]==0) bit[x]=0,bitinv[limit-x]=0; } inline void Add(int x) { cnt[x]++; if(cnt[x]==1) bit[x]=1,bitinv[limit-x]=1; } inline int Query(int opt,int x) { if(opt==1)//差 return ( ((bit>>x) & bit ).any() )?1:0; if(opt==2) return ( bit & (bitinv>>(limit-x)) ).any()?1:0; if(opt==3) { if(x==0&&bit[0]) return 1; for(int i=1;i*i<=x;i++) { if(x%i!=0) continue; if(bit[i]&&bit[x/i]) return 1; } return 0; } } inline void Modui() { sort(Q+1,Q+M+1,comp); cnt[0]=1; int l=0,r=0,tot=0; for(int i=1;i<=M;i++) { while(l<Q[i].l) Delet(a[l++]),tot++; while(l>Q[i].l) Add(a[--l]),tot++; while(r<Q[i].r) Add(a[++r]),tot++; while(r>Q[i].r) Delet(a[r--]),tot++; out[Q[i].ID]=Query(Q[i].opt,Q[i].val); } //printf("%d\n",tot); for(int i=1;i<=M;i++) puts(out[i]?"yuno":"yumi"); } int main() { //freopen("a.in","r",stdin); //freopen("b.out","w",stdout); N=read();M=read(); block=sqrt(N); for(int i=1;i<=N;i++) a[i]=read(),belong[i]=(i-1)/block+1; for(int i=1;i<=M;i++) { int how=read(),ll=read(),rr=read(),x=read(); Q[i].opt=how; Q[i].l=ll; Q[i].r=rr; Q[i].val=x; Q[i].ID=i; } Modui(); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
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