Brief description:

…

Analysis:

…

/*
	Result: 10201418	11996	Jewel Magic	Accepted	C++	4.968	2012-06-07 17:24:29
	Algorithm: Splay+Hash+Bianry Search.
*/

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std ;

typedef long long LL ;

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fi(i,a,b) for(int i=a;i>=b;i--)

const int MaxN = 200009 ;
const int MOD = 3214567 ;
LL Pow[MaxN] ;

struct Tnode;          // Splay中的一个结点
typedef Tnode *Tsplay; // 地址(标记预留内存使用情况)
Tsplay null;           // 空结点标记
struct Tnode{
	Tnode *l, *r;
	int size, key;
	bool flip ;
	LL h1, h2 ;
	Tnode() {};
	Tnode(int value): l(null), r(null), size(1), h1(value), h2(value), key(value), flip(false) {};
};
Tnode seg[MaxN*4]; // 开双倍内存预留
Tsplay newTnode;   // 标记预留内存使用到的位置
/*Renew t's inf from t->l and t->r*/
void Up  (Tsplay t){
	t->size = (t->l->size)+(t->r->size)+1 ;
	t->h1 = ((((t->l->h1) * Pow[1] + (t->key)) % MOD) * Pow[t->r->size] + (t->r->h1)) % MOD ;
	t->h2 = ((((t->r->h2) * Pow[1] + (t->key)) % MOD) * Pow[t->l->size] + (t->l->h2)) % MOD ;
	// For ex: size, min, max...
}
/*Renew (t->l and t->r)'s inf from t*/
void Down(Tsplay t){
	// For ex: add, flip
	if ( t->l != null ) {
		if ( t->flip ) { swap(t->l->h1,t->l->h2); swap(t->l->l,t->l->r); t->l->flip^=1; }
	}
	if ( t->r != null ) {
		if ( t->flip ) { swap(t->r->h1,t->r->h2); swap(t->r->l,t->r->r); t->r->flip^=1; }
	}
	t->flip = 0;
}
void RL(Tsplay &t) { Tsplay s=t->r; t->r=s->l; s->l=t; Up(t); Up(s); t=s; }
void RR(Tsplay &t) { Tsplay s=t->l; t->l=s->r; s->r=t; Up(t); Up(s); t=s; }
void Splay(Tsplay &root, int k) {
	if (root == null) return;
	Down(root);
	if      (k-1==root->l->size);     // Here it is!
	else if (k  <=root->l->size){     // On the left sub_tree.
		Splay(root->l,k);
		RR(root);
	} else {                          // On the right.
		Splay(root->r,k-root->l->size-1);
		RL(root);
	}
}
/*operate in segment [p1,p2]*/
void Reverse(Tsplay &root, int p1, int p2) {
	Splay(root,p1-1); Splay(root, p2+1);
	swap(root->l->r->h1 , root->l->r->h2);
	swap(root->l->r->l , root->l->r->r);
	root->l->r->flip ^= 1;
	// Do some change and mark.
}
/*Insert a new element with key(k) after the p_th element*/
void Insert(Tsplay &root, int p, int k) {
	Tsplay t=++newTnode; *t=Tnode(k);
	Splay(root, p); t->r=root->r; root->r=t;
	Up(t); Up(root);
}
/*Delete the p_th element in the seq.*/
void Delete(Tsplay &root, int p) {
	Splay(root,p); Splay(root->r,1);
	root->r->l=root->l; root=root->r;
	Up(root);
}
LL Hash(Tsplay &root, int p1, int p2) {
	Splay(root,p1-1); Splay(root, p2+1);
	return root->l->r->h1;
}
/*************************************************/
Tsplay root;
/*Init Splay: Insert TWO node with key=INF*/
void InitSplay(Tsplay &root) {
	newTnode=seg; null=seg;
	*null=Tnode(-1); null->size=0;
	root=++newTnode;
	Tsplay tmp=++newTnode;
	*root=Tnode(-1); *tmp=Tnode(-1);
	root->r=tmp; root->size=2;
}

int N , M ;
int main() {
	Pow[0] = 1LL ;
	fo(i,1,200000) Pow[i]=(Pow[i-1]*13) % MOD;
	while (scanf("%d %d", &N, &M) != EOF) {
		InitSplay(root) ;
		getchar(); char r ; fo(i,1,N) {
			r = getchar() ; Insert(root,i,r-'0') ;
		}
		while ( M -- ) {
			int o , p1 , p2 , c ; scanf("%d", &o) ;
			if ( o == 1 ) { scanf("%d%d", &p1, &c); Insert(root,p1+1,c) ; N ++ ; }
			if ( o == 2 ) { scanf("%d", &p1) ; Delete(root,p1+1) ; N -- ; }
			if ( o == 3 ) { scanf("%d%d", &p1, &p2) ; Reverse(root,p1+1,p2+1) ; }
			if ( o == 4 ) {
				scanf("%d%d", &p1, &p2);
				int k = 1 ; while ( p1 + k*2 - 1 <= N && p2 + k*2 - 1 <= N ) k *= 2 ;
				int ans = 0 ;
				while ( k > 0 ) {
					if ( p1+k-1 > N || p2+k-1 > N ) { k /= 2 ; continue ; }
					if ( Hash(root,p1+1,p1+k-1+1) == Hash(root,p2+1,p2+k-1+1) ) {
						ans += k ;
						p1 += k , p2 += k ;
					}
					k /= 2 ;
				}
				printf("%d\n", ans);
			}
		}
	}
}

External link:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3147

Posted by xiaodao
Category: UVa
Tags: 施工中