首页 > 代码库 > 【分块】【哈希】bzoj3578 GTY的人类基因组计划2
【分块】【哈希】bzoj3578 GTY的人类基因组计划2
每个房间用一个集合来维护，具体来说，就是给1-n的数每个数一个long long的hash值，往集合S里insert(i)，就是S^=HASH[i]；erase(i)，也是S^=HASH[i]。
用map/set维护某个集合是否已经做过实验。
分块，对每个块维护一个maxv[i]，代表当前该块内的答案值，要注意，若某个房间的集合的vis[S[i]]==true，则它对其所在块没有贡献。
分块相对于线段树/平衡树/树套树的很大的好处，就是思路简单暴力，代码短，常数小，应对范围广，可以方便地扩张。
像这种区间修改的问题，可以类比线段树打懒标记的思路来进行，使得每次修改是O(sqrt(n))的。
Pushdown函数需要每次对块进行“零散地”操作的之前进行。
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<ctime> 6 #include<map> 7 using namespace std; 8 unsigned long long HASH[100001]; 9 struct SET 10 { 11 unsigned long long S;int size; 12 void insert(const int &v){S^=HASH[v];size++;} 13 void erase(const int &v){S^=HASH[v];size--;} 14 }; 15 int n,m,q,l[600],r[600],sumv[600],sum,sz,num[100001],x,y,pos[100001]; 16 bool delta[600]; 17 SET sets[100001]; 18 map<unsigned long long,bool>vis; 19 char op[1]; 20 int Res,Num;char C,CH[12]; 21 inline int G() 22 { 23 Res=0;C=‘*‘; 24 while(C<‘0‘||C>‘9‘)C=getchar(); 25 while(C>=‘0‘&&C<=‘9‘){Res=Res*10+(C-‘0‘);C=getchar();} 26 return Res; 27 } 28 inline void P(long long x) 29 { 30 Num=0;if(!x){putchar(‘0‘);puts("");return;} 31 while(x>0)CH[++Num]=x%10,x/=10; 32 while(Num)putchar(CH[Num--]+48); 33 puts(""); 34 } 35 void makeblock() 36 { 37 srand(233); 38 for(int i=1;i<=n;i++) HASH[i]=(unsigned long long)((unsigned long long)rand()<<48)|((unsigned long long)rand()<<32)|((unsigned long long)rand()<<16)|((unsigned long long)rand()); 39 sz=sqrt((double)m*0.3); 40 for(int i=1;i<=n;i++) {sets[1].insert(i); pos[i]=1;} 41 sumv[1]=n; 42 for(sum=1;sum*sz<m;sum++) 43 { 44 l[sum]=(sum-1)*sz+1; 45 r[sum]=sum*sz; 46 for(int i=l[sum];i<=r[sum];i++) num[i]=sum; 47 } 48 l[sum]=sz*(sum-1)+1; r[sum]=m; 49 for(int i=l[sum];i<=r[sum];i++) num[i]=sum; 50 } 51 inline void Pushdown(const int &p)//对块p下传标记,Pushdown操作需要每次对块进行零散操作之前进行 52 { 53 if(delta[p]) 54 { 55 for(int i=l[p];i<=r[p];i++) 56 if(sets[i].size) 57 vis[sets[i].S]=true; 58 delta[p]=false; 59 } 60 } 61 inline void Move() 62 { 63 Pushdown(num[pos[x]]); 64 bool flag1=vis[sets[pos[x]].S]; 65 sets[pos[x]].erase(x); 66 bool flag2=vis[sets[pos[x]].S]; 67 if(flag1&&!flag2) sumv[num[pos[x]]]+=sets[pos[x]].size; 68 else if(!flag1&&flag2) sumv[num[pos[x]]]-=(sets[pos[x]].size+1); 69 else if(!flag1&&!flag2) sumv[num[pos[x]]]--; 70 Pushdown(num[y]); 71 flag1=vis[sets[y].S]; 72 sets[y].insert(x); 73 flag2=vis[sets[y].S]; 74 if(flag1&&!flag2) sumv[num[y]]+=sets[y].size; 75 else if(!flag1&&flag2) sumv[num[y]]-=(sets[y].size-1); 76 else if(!flag1&&!flag2) sumv[num[y]]++; 77 pos[x]=y; 78 } 79 inline void Update_Query() 80 { 81 int ans=0; 82 Pushdown(num[x]); 83 Pushdown(num[y]); 84 if(num[x]+1>=num[y]) 85 { 86 for(int i=x;i<=y;i++) 87 if(sets[i].size) 88 if(!vis[sets[i].S]) 89 { 90 ans+=sets[i].size; 91 sumv[num[i]]-=sets[i].size; 92 vis[sets[i].S]=true; 93 } 94 } 95 else 96 { 97 for(int i=x;i<=r[num[x]];i++) 98 if(sets[i].size) 99 if(!vis[sets[i].S])100 {101 ans+=sets[i].size;102 sumv[num[x]]-=sets[i].size;103 vis[sets[i].S]=true;104 }105 for(int i=l[num[y]];i<=y;i++)106 if(sets[i].size)107 if(!vis[sets[i].S])108 {109 ans+=sets[i].size;110 sumv[num[y]]-=sets[i].size;111 vis[sets[i].S]=true;112 }113 for(int i=num[x]+1;i<num[y];i++)114 {115 if(!delta[i])116 ans+=sumv[i];117 delta[i]=true;118 sumv[i]=0;119 }120 }121 P(ans);122 }123 int main()124 {125 n=G();m=G();q=G();126 makeblock();127 for(;q>0;q--)128 {129 scanf("%s",op);x=G();y=G(); 130 if(op[0]==‘C‘) Move();131 else Update_Query();132 }133 return 0;134 }
【分块】【哈希】bzoj3578 GTY的人类基因组计划2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。