【BZOJ 1507】【NOI 2003】&【Tyvj P2388】Editor 块状链表模板题

2016-06-18 当时关于块状链表的想法是错误的，之前维护的是一个动态的$\sqrt{n}$，所以常数巨大，今天才知道原因TwT，请不要参照这个程序为模板！！！

模板题水啊水~~~

第一次写块状链表，先写一个模板题(⊙o⊙)

块状链表虽然效率大概在O(n√n)，但它几乎没有常数，相比较理论上复杂度较快的O(nlogn)的Splay还是要快，因为Splay常数太大啦！感觉比较笨重。也许这就是许多OIer热衷分块的原因吧。

BZOJ 1507(因为O2优化，没有内存池)

#include<cmath>

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

using namespace std;

int now=0,min_tot=0,max_tot=0,tot=0,sq;

struct BLOCK{

    BLOCK();

    BLOCK *next;

    char c[100003];

    int size;

}*head,*null;

BLOCK::BLOCK(){next=null;size=0;}

inline void build(){

    null=new BLOCK;

    *null=BLOCK();

    head=new BLOCK;

}

inline BLOCK *find(int &k){

    BLOCK *r=head;

    while (k-r->size>0&&r->next!=null) k-=r->size,r=r->next;

    return r;

}

inline void cut(BLOCK *r,int pos){

    BLOCK *k=new BLOCK;

    k->size=r->size-pos;

    for1(i,pos+1,r->size) k->c[i-pos]=r->c[i];

    r->size=pos;

    k->next=r->next;

    r->next=k;

}

inline void merge(BLOCK *r){

    if (r->next==null) return;

    BLOCK *k=r->next;

    for1(i,1,k->size) r->c[r->size+i]=k->c[i];

    r->size+=k->size;

    r->next=k->next;

    delete k;

}

inline void balance(){

    BLOCK *r=head;

    sq=floor(sqrt(tot)); min_tot=sq/2; max_tot=sq*2;

    while (r!=null){

        if (r->size<min_tot) if (r->next==null) return; else {merge(r); continue;}

        else if (r->size>max_tot) {cut(r,r->size/2); continue;}

        r=r->next;

    }

}

inline void work1(int x){

    int pnow=now; BLOCK *r=find(pnow),*k=new BLOCK,*sta=k;

    cut(r,pnow);

    for1(i,1,x){

        char cs=getchar();

        while (cs=='\n') cs=getchar();

        k->size++; k->c[k->size]=cs;

        if (k->size>=sq){

            k->next=new BLOCK;

            k=k->next;

        }

    }k->next=r->next;r->next=sta;

}

inline void work2(int x){

    int pnow=now; BLOCK *r=find(pnow);

    if (x<=r->size-pnow){

        cut(r,pnow); cut(r->next,x);

        BLOCK *xx=r->next;

        r->next=r->next->next;

        delete xx;

        return;

    }

    x-=r->size-pnow;

    cut(r,pnow);

    BLOCK *xy=r->next;

    r->next=r->next->next;

    delete xy;

    while (x-r->next->size>0&&r->next!=null){

        x-=r->next->size;

        BLOCK *xx=r->next;

        r->next=r->next->next;

        delete xx;

    }cut(r->next,x);

    BLOCK *xx=r->next;

    r->next=r->next->next;

    delete xx;

}

inline void work3(int x){

    int pnow=now; BLOCK *r=find(pnow);

    if (x<=r->size-pnow){for1(i,pnow+1,pnow+x) putchar(r->c[i]); return;}

    for1(i,pnow+1,r->size) putchar(r->c[i]);

    x-=r->size-pnow; r=r->next;

    while (x-r->size>0&&r!=null){

        for1(i,1,r->size) putchar(r->c[i]);

        x-=r->size; r=r->next;

    }for1(i,1,x)putchar(r->c[i]);

}

int main(){

    build();

    int n;scanf("%d\n",&n);

    while (n--){

        char str=getchar(),st=getchar();

        int x;

        switch(str){

            case 'I':

                while (st!=' ') st=getchar();

                scanf("%d",&x); tot+=x; sq=floor(sqrt(tot)); min_tot=sq/2; max_tot=sq*2;

                work1(x);

                balance();

                scanf("\n");

            break;

            case 'M':

                while (st!=' ') st=getchar();

                scanf("%d\n",&now);

            break;

            case 'D':

                while (st!=' ') st=getchar();

                scanf("%d\n",&x); work2(x);

                tot-=x; balance();

            break;

            case 'G':

                while (st!=' ') st=getchar();

                scanf("%d\n",&x); work3(x); printf("\n");

            break;

            case 'P':

                now--;st=getchar();st=getchar();st=getchar();

            break;

            case 'N':

                now++;st=getchar();st=getchar();st=getchar();

            break;

        }

    }

    return 0;

}

Tyvj P2388(Windows下评测的new和delete慢得飞起，所以写了个内存池)

#include<cmath>

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

using namespace std;

int now=0,min_tot=0,max_tot=0,tot=0,sq;

struct BLOCK{

	BLOCK();

	BLOCK *next;

	char c[10003];

	int size;

}*head,*null,pool[10003];

int top=0;

BLOCK::BLOCK(){next=null;size=0;}

inline BLOCK *newBLOCK(){

	BLOCK *t=&pool[top++];

	t->next=null; t->size=0;

	return t;

}

inline void build(){

	null=newBLOCK();

	null->next=null; null->size=0;

	head=newBLOCK();

}

inline BLOCK *find(int &k){

	BLOCK *r=head;

	while (k-r->size>0&&r->next!=null) k-=r->size,r=r->next;

	return r;

}

inline void cut(BLOCK *r,int pos){

	BLOCK *k=newBLOCK();

	k->size=r->size-pos;

	for1(i,pos+1,r->size) k->c[i-pos]=r->c[i];

	r->size=pos;

	k->next=r->next;

	r->next=k;

}

inline void merge(BLOCK *r){

	if (r->next==null) return;

	BLOCK *k=r->next;

	for1(i,1,k->size) r->c[r->size+i]=k->c[i];

	r->size+=k->size;

	r->next=k->next;

	//delete k;

}

inline void balance(){

	BLOCK *r=head;

	sq=floor(sqrt(tot)); min_tot=sq/2; max_tot=sq*2;

	while (r!=null){

		if (r->size<min_tot) if (r->next==null) return; else {merge(r); continue;}

		else if (r->size>max_tot) {cut(r,r->size/2); continue;}

		r=r->next;

	}

}

inline void work1(int x){

	int pnow=now; BLOCK *r=find(pnow),*k=newBLOCK(),*sta=k;

	cut(r,pnow);

	for1(i,1,x){

		char cs=getchar();

		while (cs=='\n') cs=getchar();

		k->size++; k->c[k->size]=cs;

		if (k->size>=sq){

			k->next=newBLOCK();

			k=k->next;

		}

	}k->next=r->next;r->next=sta;

}

inline void work2(int x){

	int pnow=now; BLOCK *r=find(pnow);

	if (x<=r->size-pnow){

		cut(r,pnow); cut(r->next,x);

		BLOCK *xx=r->next;

		r->next=r->next->next;

		//delete xx;

		return;

	}

	x-=r->size-pnow;

	cut(r,pnow);

	BLOCK *xy=r->next;

	r->next=r->next->next;

	//delete xy;

	while (x-r->next->size>0&&r->next!=null){

		x-=r->next->size;

		BLOCK *xx=r->next;

		r->next=r->next->next;

		//delete xx;

	}cut(r->next,x);

	BLOCK *xx=r->next;

	r->next=r->next->next;

	//delete xx;

}

inline void work3(int x){

	int pnow=now; BLOCK *r=find(pnow);

	if (x<=r->size-pnow){for1(i,pnow+1,pnow+x) putchar(r->c[i]); return;}

	for1(i,pnow+1,r->size) putchar(r->c[i]);

	x-=r->size-pnow; r=r->next;

	while (x-r->size>0&&r!=null){

		for1(i,1,r->size) putchar(r->c[i]);

		x-=r->size; r=r->next;

	}for1(i,1,x)putchar(r->c[i]);

}

int main(){

	build();

	int n;scanf("%d\n",&n);

	while (n--){

		char str=getchar(),st=getchar();

		int x;

		switch(str){

			case 'I':

				while (st!=' ') st=getchar();

				scanf("%d",&x); tot+=x; sq=floor(sqrt(tot)); min_tot=sq/2; max_tot=sq*2;

				work1(x);

				balance();

				scanf("\n");

			break;

			case 'M':

				while (st!=' ') st=getchar();

				scanf("%d\n",&now);

			break;

			case 'D':

				while (st!=' ') st=getchar();

				scanf("%d\n",&x); work2(x);

				tot-=x;	balance();

			break;

			case 'G':

				while (st!=' ') st=getchar();

				scanf("%d\n",&x); work3(x); printf("\n");

			break;

			case 'P':

				now--;st=getchar();st=getchar();st=getchar();

			break;

			case 'N':

				now++;st=getchar();st=getchar();st=getchar();

			break;

		}

	}

	return 0;

}

分块真心强大，，，