题目大意：给定n个长度为l的字符串，，m次交换两个字符，问每个字符串任意时刻最多与多少个相同
把字符串Hash一下 然后就是千山鸟飞绝了。。。
BZ挂了交不了题真闹心QAQ
#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 1010#define BASE 131using namespace std;int ans[M];struct Treap{static queue<Treap*> bin;Treap *ls,*rs;int val,key,size,mark;void* operator new (size_t,int _){Treap *re;if(bin.size())re=bin.front(),bin.pop();else{static Treap mempool[M],*C=mempool;re=C++;}re->ls=re->rs=0x0;re->val=_;re->key=rand();re->size=1;re->mark=0;return re;}void operator delete (void *p){bin.push((Treap*)p);}void Get_Mark(int x){ans[val]=max(ans[val],x);mark=max(mark,x);}void Push_Up(){size=1;if(ls) size+=ls->size;if(rs) size+=rs->size;}void Push_Down(){if(!mark) return ;if(ls) ls->Get_Mark(mark);if(rs) rs->Get_Mark(mark);mark=0;}friend void Zig(Treap *&x){Treap *y=x->ls;x->Push_Down();y->Push_Down();x->ls=y->rs;y->rs=x;x=y;x->Push_Up();x->rs->Push_Up();}friend void Zag(Treap *&x){Treap *y=x->rs;x->Push_Down();y->Push_Down();x->rs=y->ls;y->ls=x;x=y;x->Push_Up();x->ls->Push_Up();}friend void Insert(Treap *&x,int y){if(!x){x=new (y)Treap;return ;}x->Push_Down();if(y<x->val){Insert(x->ls,y);if( x->ls->key > x->key )Zig(x);}else{Insert(x->rs,y);if( x->rs->key > x->key )Zag(x);}x->Push_Up();}friend void Delete(Treap *&x,int y){x->Push_Down();if(y<x->val)Delete(x->ls,y);else if(y>x->val)Delete(x->rs,y);else{if(!x->ls){Treap *temp=x;x=x->rs;delete temp;}else if(!x->rs){Treap *temp=x;x=x->ls;delete temp;}else{Zag(x);Delete(x->ls,y);if( x->ls && x->ls->key > x->key )Zig(x);}}if(x) x->Push_Up();}};queue<Treap*> Treap :: bin;int n,m,l;char s[M][110];unsigned long long power[110],hash[M];namespace Hash_Set{struct List{unsigned long long hash;Treap *pointer;List *next;List(unsigned long long _,List *__):hash(_),pointer(0x0),next(__) {}}*head[10301];Treap*& Hash(unsigned long long hash){int pos=hash%10301;List *temp;for(temp=head[pos];temp;temp=temp->next)if(temp->hash==hash)return temp->pointer;return (head[pos]=new List(hash,head[pos]))->pointer;}}void Insert(int x){using namespace Hash_Set;Treap *&root=Hash(hash[x]);Insert(root,x);root->Get_Mark(root->size);}void Delete(int x){using namespace Hash_Set;Treap *&root=Hash(hash[x]);Delete(root,x);}int main(){srand(19980402);int i,j,x1,y1,x2,y2;cin>>n>>l>>m;for(power[0]=1,i=1;i<=l;i++)power[i]=power[i-1]*BASE;for(i=1;i<=n;i++){scanf("%s",s[i]+1);for(j=1;j<=l;j++)(hash[i]*=BASE)+=s[i][j];Insert(i);}for(i=1;i<=m;i++){scanf("%d%d%d%d",&x1,&y1,&x2,&y2);Delete(x1);if(x1!=x2) Delete(x2);hash[x1]-=s[x1][y1]*power[l-y1];hash[x2]-=s[x2][y2]*power[l-y2];swap(s[x1][y1],s[x2][y2]);hash[x1]+=s[x1][y1]*power[l-y1];hash[x2]+=s[x2][y2]*power[l-y2];Insert(x1);if(x1!=x2) Insert(x2);}for(i=1;i<=n;i++)Delete(i);for(i=1;i<=n;i++)printf("%d\n",ans[i]);return 0;}
勇于接受自己的不完美，认清自己不足的地方，
