…<\/p>\n
<\/p>\n
…<\/p>\n
\r\n\/*\r\n\tResult: 10201418\t11996\tJewel Magic\tAccepted\tC++\t4.968\t2012-06-07 17:24:29\r\n\tAlgorithm: Splay+Hash+Bianry Search.\r\n*\/\r\n\r\n#include <iostream>\r\n#include <cstdio>\r\n#include <cstring>\r\nusing namespace std ;\r\n\r\ntypedef long long LL ;\r\n\r\n#define fo(i,a,b) for(int i=a;i<=b;i++)\r\n#define fi(i,a,b) for(int i=a;i>=b;i--)\r\n\r\nconst int MaxN = 200009 ;\r\nconst int MOD = 3214567 ;\r\nLL Pow[MaxN] ;\r\n\r\nstruct Tnode; \/\/ Splay\u4e2d\u7684\u4e00\u4e2a\u7ed3\u70b9\r\ntypedef Tnode *Tsplay; \/\/ \u5730\u5740(\u6807\u8bb0\u9884\u7559\u5185\u5b58\u4f7f\u7528\u60c5\u51b5)\r\nTsplay null; \/\/ \u7a7a\u7ed3\u70b9\u6807\u8bb0\r\nstruct Tnode{\r\n\tTnode *l, *r;\r\n\tint size, key;\r\n\tbool flip ;\r\n\tLL h1, h2 ;\r\n\tTnode() {};\r\n\tTnode(int value): l(null), r(null), size(1), h1(value), h2(value), key(value), flip(false) {};\r\n};\r\nTnode seg[MaxN*4]; \/\/ \u5f00\u53cc\u500d\u5185\u5b58\u9884\u7559\r\nTsplay newTnode; \/\/ \u6807\u8bb0\u9884\u7559\u5185\u5b58\u4f7f\u7528\u5230\u7684\u4f4d\u7f6e\r\n\/*Renew t's inf from t->l and t->r*\/\r\nvoid Up (Tsplay t){\r\n\tt->size = (t->l->size)+(t->r->size)+1 ;\r\n\tt->h1 = ((((t->l->h1) * Pow[1] + (t->key)) % MOD) * Pow[t->r->size] + (t->r->h1)) % MOD ;\r\n\tt->h2 = ((((t->r->h2) * Pow[1] + (t->key)) % MOD) * Pow[t->l->size] + (t->l->h2)) % MOD ;\r\n\t\/\/ For ex: size, min, max...\r\n}\r\n\/*Renew (t->l and t->r)'s inf from t*\/\r\nvoid Down(Tsplay t){\r\n\t\/\/ For ex: add, flip\r\n\tif ( t->l != null ) {\r\n\t\tif ( t->flip ) { swap(t->l->h1,t->l->h2); swap(t->l->l,t->l->r); t->l->flip^=1; }\r\n\t}\r\n\tif ( t->r != null ) {\r\n\t\tif ( t->flip ) { swap(t->r->h1,t->r->h2); swap(t->r->l,t->r->r); t->r->flip^=1; }\r\n\t}\r\n\tt->flip = 0;\r\n}\r\nvoid RL(Tsplay &t) { Tsplay s=t->r; t->r=s->l; s->l=t; Up(t); Up(s); t=s; }\r\nvoid RR(Tsplay &t) { Tsplay s=t->l; t->l=s->r; s->r=t; Up(t); Up(s); t=s; }\r\nvoid Splay(Tsplay &root, int k) {\r\n\tif (root == null) return;\r\n\tDown(root);\r\n\tif (k-1==root->l->size); \/\/ Here it is!\r\n\telse if (k <=root->l->size){ \/\/ On the left sub_tree.\r\n\t\tSplay(root->l,k);\r\n\t\tRR(root);\r\n\t} else { \/\/ On the right.\r\n\t\tSplay(root->r,k-root->l->size-1);\r\n\t\tRL(root);\r\n\t}\r\n}\r\n\/*operate in segment [p1,p2]*\/\r\nvoid Reverse(Tsplay &root, int p1, int p2) {\r\n\tSplay(root,p1-1); Splay(root, p2+1);\r\n\tswap(root->l->r->h1 , root->l->r->h2);\r\n\tswap(root->l->r->l , root->l->r->r);\r\n\troot->l->r->flip ^= 1;\r\n\t\/\/ Do some change and mark.\r\n}\r\n\/*Insert a new element with key(k) after the p_th element*\/\r\nvoid Insert(Tsplay &root, int p, int k) {\r\n\tTsplay t=++newTnode; *t=Tnode(k);\r\n\tSplay(root, p); t->r=root->r; root->r=t;\r\n\tUp(t); Up(root);\r\n}\r\n\/*Delete the p_th element in the seq.*\/\r\nvoid Delete(Tsplay &root, int p) {\r\n\tSplay(root,p); Splay(root->r,1);\r\n\troot->r->l=root->l; root=root->r;\r\n\tUp(root);\r\n}\r\nLL Hash(Tsplay &root, int p1, int p2) {\r\n\tSplay(root,p1-1); Splay(root, p2+1);\r\n\treturn root->l->r->h1;\r\n}\r\n\/*************************************************\/\r\nTsplay root;\r\n\/*Init Splay: Insert TWO node with key=INF*\/\r\nvoid InitSplay(Tsplay &root) {\r\n\tnewTnode=seg; null=seg;\r\n\t*null=Tnode(-1); null->size=0;\r\n\troot=++newTnode;\r\n\tTsplay tmp=++newTnode;\r\n\t*root=Tnode(-1); *tmp=Tnode(-1);\r\n\troot->r=tmp; root->size=2;\r\n}\r\n\r\nint N , M ;\r\nint main() {\r\n\tPow[0] = 1LL ;\r\n\tfo(i,1,200000) Pow[i]=(Pow[i-1]*13) % MOD;\r\n\twhile (scanf("%d %d", &N, &M) != EOF) {\r\n\t\tInitSplay(root) ;\r\n\t\tgetchar(); char r ; fo(i,1,N) {\r\n\t\t\tr = getchar() ; Insert(root,i,r-'0') ;\r\n\t\t}\r\n\t\twhile ( M -- ) {\r\n\t\t\tint o , p1 , p2 , c ; scanf("%d", &o) ;\r\n\t\t\tif ( o == 1 ) { scanf("%d%d", &p1, &c); Insert(root,p1+1,c) ; N ++ ; }\r\n\t\t\tif ( o == 2 ) { scanf("%d", &p1) ; Delete(root,p1+1) ; N -- ; }\r\n\t\t\tif ( o == 3 ) { scanf("%d%d", &p1, &p2) ; Reverse(root,p1+1,p2+1) ; }\r\n\t\t\tif ( o == 4 ) {\r\n\t\t\t\tscanf("%d%d", &p1, &p2);\r\n\t\t\t\tint k = 1 ; while ( p1 + k*2 - 1 <= N && p2 + k*2 - 1 <= N ) k *= 2 ;\r\n\t\t\t\tint ans = 0 ;\r\n\t\t\t\twhile ( k > 0 ) {\r\n\t\t\t\t\tif ( p1+k-1 > N || p2+k-1 > N ) { k \/= 2 ; continue ; }\r\n\t\t\t\t\tif ( Hash(root,p1+1,p1+k-1+1) == Hash(root,p2+1,p2+k-1+1) ) {\r\n\t\t\t\t\t\tans += k ;\r\n\t\t\t\t\t\tp1 += k , p2 += k ;\r\n\t\t\t\t\t}\r\n\t\t\t\t\tk \/= 2 ;\r\n\t\t\t\t}\r\n\t\t\t\tprintf("%d\\n", ans);\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n}\r\n\r\n<\/pre>\nExternal link: <\/h3>\n