【BZOJ 3524】【Poi2014】Couriers 可持久化线段树

为什么这个主席树叫可持久化线段树，我不知道，具体得问达神。我无限T，然后DaD3zZ一针见血地指出了我的N*50爆内存导致无限编译超时O)ZO)ZO)Z真是太神啦。以图为鉴：

达神题解传送门：http://blog.csdn.net/dad3zz/article/details/50644748

然后是我根本没法跟DaD3zZ相比的拙劣的代码：

#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 read(x) x=getint()

using namespace std;

const int N=500010;

inline int max(const int &a,const int &b){return a>b?a:b;}

inline int min(const int &a,const int &b){return a<b?a:b;}

inline void swapp(int &a,int &b){int c=a;a=b;b=c;}

inline int getint(){char c;int ret=0,k=1;for(c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')k=-1;for(;c>='0'&&c<='9';c=getchar())ret=ret*10+c-'0';return ret*k;}

int key,a[N],n,m,root[N],cnt=0;

struct node{int l,r,s;}T[N*20];

inline void update(int l,int r,int &pos){

	T[++cnt]=T[pos]; pos=cnt; T[pos].s++;

	if (l==r) return;

	int mid=(l+r)>>1;

	if (key<=mid) update(l,mid,T[pos].l); else update(mid+1,r,T[pos].r);

}

inline int query(int L,int R){

	int l=1,r=n,x=L,y=R,mid,s;

	while (l<r){

		if (T[y].s-T[x].s<=key) return 0;

		mid=(l+r)>>1;

		if (T[T[y].l].s-T[T[x].l].s>key) r=mid,x=T[x].l,y=T[y].l;

		else if (T[T[y].r].s-T[T[x].r].s>key) l=mid+1,x=T[x].r,y=T[y].r;

			 else return 0;

	}return l;

}

int main(){

	read(n); read(m);

	for1(i,1,n) read(a[i]);

	for1(i,1,n){

		root[i]=root[i-1]; key=a[i];

		update(1,n,root[i]);

	}int x,y;

	while (m--){

		read(x); read(y); key=(y-x+1)/2;

		printf("%d\n",query(root[x-1],root[y]));

	}return 0;

}

　　然后就可以了