這個題和千山鳥飛絕體現出了一種用平衡樹解決動態集合問題，主要套路就是蜜汁標記。

這個題我一開始用替罪羊樹搞了一下對了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; }

?

轉載于:https://www.cnblogs.com/TSHugh/p/7000379.html

總結

以上是生活随笔為你收集整理的[POI2008] Poc (原名 Trians) Treap+Hash的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。