首页 > 代码库 > [POI2008] Poc (原名 Trians) Treap+Hash
[POI2008] Poc (原名 Trians) Treap+Hash
这个题和千山鸟飞绝体现出了一种用平衡树解决动态集合问题,主要套路就是蜜汁标记。
这个题我一开始用替罪羊树搞了一下对了28个点,后来我换成了Treap一搞对了14个点,再后来发现被卡了Hash我竟然在自然溢出中用了256....
上代码
#include<cstdio> #include<cstring> #include<map> #include<cstdlib> #define N 1010 #define L 110 #define M 100010 using namespace std; typedef unsigned long long ULL; const ULL base=131; ULL tool[L]; ULL hash[N]; char s[N][L]; int size[N],n,l,m; map<ULL,int>Hash; inline int Max(int x,int y){ return x>y?x:y; } inline void swap(char &a,char &b){char c=a;a=b;b=c;} struct Treap { Treap *ch[2]; int size,Max,i,r; Treap(){ch[1]=ch[0]=NULL;size=Max=i=r=0;} }node[(N+M)<<4],*null,*root[(N+M)<<4]; int sz,tp; inline void Init() { null=node; null->size=null->Max=null->i=null->r=0; null->ch[1]=null->ch[0]=null; for(int i=0;i<((N+M)<<2);i++)root[i]=null; } inline Treap *New(int i) { Treap *p=&node[++sz]; p->ch[1]=p->ch[0]=null; p->Max=0; p->i=i; p->size=1; p->r=rand()+1; return p; } inline void pushup(Treap *p) { if(p==null)return; p->size=p->ch[0]->size+p->ch[1]->size+1; } inline void down(Treap *p,int x) { size[p->i]=Max(size[p->i],x); p->Max=Max(p->Max,x); } inline void pushdown(Treap *p) { if(p->Max==0)return; if(p->ch[0]!=null) down(p->ch[0],p->Max); if(p->ch[1]!=null) down(p->ch[1],p->Max); p->Max=0; } inline void rotate(Treap *&p) { int wh=p->ch[1]->r>p->ch[0]->r; Treap *ch=p->ch[wh]; pushdown(p); pushdown(ch); p->ch[wh]=ch->ch[wh^1]; ch->ch[wh^1]=p; pushup(p); pushup(ch); p=ch; } void insert(Treap *&p,int i) { if(p==null) { p=New(i); return; } pushdown(p); insert(p->ch[p->i<i],i); if(p->r<p->ch[p->i<i]->r)rotate(p); pushup(p); } void del(Treap *&p,int i) { pushdown(p); if(p->i==i) { if(p->ch[0]==null||p->ch[1]==null) { p=p->ch[0]==null?p->ch[1]:p->ch[0]; pushup(p); return; } rotate(p); del(p->ch[p->ch[1]->i==i],i); pushup(p); return; } del(p->ch[p->i<i],i); pushup(p); return; } inline void Insert(int i) { insert(root[Hash[hash[i]]],i); down(root[Hash[hash[i]]],root[Hash[hash[i]]]->size); } inline void Del(int i) { del(root[Hash[hash[i]]],i); } int main() { Init(); scanf("%d%d%d",&n,&l,&m); tool[0]=1; for(int i=1;i<=l;i++) tool[i]=tool[i-1]*base; for(int i=1;i<=n;i++) { scanf("%s",s[i]+1); for(int j=1;j<=l;j++)hash[i]=hash[i]*base+s[i][j]; if(Hash[hash[i]]==0)Hash[hash[i]]=++tp; Insert(i); } for(int i=1;i<=m;i++) { int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); Del(a); if(a!=c)Del(c); hash[a]-=s[a][b]*tool[l-b]; hash[c]-=s[c][d]*tool[l-d]; swap(s[a][b],s[c][d]); hash[a]+=s[a][b]*tool[l-b]; hash[c]+=s[c][d]*tool[l-d]; if(Hash[hash[a]]==0)Hash[hash[a]]=++tp; Insert(a); if(a!=c){if(Hash[hash[c]]==0)Hash[hash[c]]=++tp;Insert(c);} } for(int i=1;i<=n;i++)Del(i); for(int i=1;i<=n;i++)printf("%d\n",size[i]); return 0; }
[POI2008] Poc (原名 Trians) Treap+Hash
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。