@OceanEye7年前
04/27
09:59
题目 链接 ：http://www.lydsy.com/JudgeOnline/problem.php?id=4810
kry大爷的代码好短……可以看看orz
这题目测只要是根号+压位就能过得去的了……所以不要太在意细节
[然后就被细节骗走了五次wa]
如果我们压了位……
减法就可以直接右移解决 b-c=a
加法的话把它反过来右移解决 大概是变成 a+b=c -> b-c=-a
乘法很simple，直接暴力就好了，根号可是比n/64要小的
而且时限30s，跑起来好像还挺稳的？
代码：
|
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 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <cstdlib> #include <iostream> #include <bitset> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; #define N 100010 #define SIZ 400 bitset <N> Appear,Rev,____; int a[N],cnt[N],n,m; int l[SIZ],r[SIZ],belong[N],SQR,CNT; struct rec { int l,r,c,type; int id; }pool[N]; bool comp(const rec &x,const rec&y ) { if(belong[x.l]==belong[y.l]) return x.r<y.r; return x.l<y.l; } void pre() { read(n); read(m); for(int i=1;i<=n;i++) read(a[i]); SQR=sqrt(n); CNT=(n-1)/SQR+1; for(int i=1;i<=CNT;i++) { l[i]=(CNT-1)*SQR+1; r[i]=CNT*SQR; } r[CNT]=n; for(int i=1;i<=n;i++) belong[i]=(i-1)/SQR+1; for(int i=1;i<=m;i++) { read(pool[i].type); read(pool[i].l); read(pool[i].r); read(pool[i].c); pool[i].id=i; } sort(pool+1,pool+1+m,comp); } int ans[N]; void solve(int i) { if(pool[i].type==1) { ____=Appear; ____>>=pool[i].c; ____&=Appear; if(____.any()) ans[pool[i].id]=1; else ans[pool[i].id]=0; return; } if(pool[i].type==2) { ____=Rev; ____>>=(100000-pool[i].c); ____&=Appear; if(____.any()) ans[pool[i].id]=1; else ans[pool[i].id]=0; return; } if(pool[i].type==3) { for(int j=1;j*j<=pool[i].c;j++) if(cnt[j]&&cnt[pool[i].c/j]) { if(pool[i].c%j==0) { ans[pool[i].id]=1; return; } } ans[pool[i].id]=0; return; } } int main() { pre(); int nodeR,nodeL; nodeR=0;nodeL=1; for(int i=1;i<=m;i++) { while(nodeR<pool[i].r) { nodeR++; cnt[a[nodeR]]++; if(cnt[a[nodeR]]==1) Appear[a[nodeR]]=1,Rev[100000-a[nodeR]]=1; } while(nodeL>pool[i].l) { nodeL--; cnt[a[nodeL]]++; if(cnt[a[nodeL]]==1) Appear[a[nodeL]]=1,Rev[100000-a[nodeL]]=1; } while(nodeL<pool[i].l) { cnt[a[nodeL]]--; if(!cnt[a[nodeL]]) Appear[a[nodeL]]=0,Rev[100000-a[nodeL]]=0; nodeL++; } while(nodeR>pool[i].r) { cnt[a[nodeR]]--; if(!cnt[a[nodeR]]) Appear[a[nodeR]]=0,Rev[100000-a[nodeR]]=0; nodeR--; } solve(i); } for(int i=1;i<=m;i++) ans[i]?puts("yuno"):puts("yumi"); return 0; } |